C++：一次性搞定vector模拟实现中必须关注的细节

本文主要是介绍C++：一次性搞定vector模拟实现中必须关注的细节，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. vector的模拟实现源码

vector本质是顺序表，因此其迭代器可以理解为原生指针。
我们通过原生指针来模拟实现vector.

namespace B
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//Iteratorsiterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//constructor and destructorvector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){ }vector(initializer_list<T> il){//const T* it = il.begin();//while (it != il.end())//{//push_back(*it);//it++;//}//il本质是一个类，有begin()和end()，因此也可以使用迭代器reserve(il.size());for (auto& e : il){push_back(e);}}vector(size_t n, const T& val = T()){//_start = new T[n];//_finish = _endofstorage = _start + n;//复用reservereserve(n);for (size_t i = 0; i < n; i++)push_back(val);}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++)push_back(val);}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){*_finish = e;_finish++;}}//现代写法vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}//capacitybool empty() const{return _finish == _start;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void resize(size_t n , const T& val = T()){if (n > size()){reserve(n);for (size_t i = size(); i < n; i++)push_back(val);}else{//for (int i = size(); i > n; i--)//	pop_back();//我们可以直接改变指针_finish = _start + n;}}void reserve(size_t n){//不会缩容//错误写法//错因：我们的_start改变了 但是我们的_finsh和_endofstorage还没有改变//在调用size()时会出错 因为我们size()函数求大小时使用了_finish//if (n > capacity)//{//	T* tmp = new T[n];//	memcpy(tmp, _start, sizeof(T) * size());//	delete[] _start;//	_start = tmp;//	_finish = _start + size();//	_endofstorage = _start + n;//}//正确if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());//如果使用memcpy，对于类似vector<string>这样的类，就会出现浅拷贝的现象从而报错for (size_t i = 0; i < oldSize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}}//Element accessT& operator[](size_t pos){return *(_start + pos);}const T& operator[](size_t pos) const{return *(_start + pos);}//Modifyvoid push_back(const T& x){//扩容//if (_finish == _endofstorage)//{//	size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//	reserve(newcapacity);//}//*_finish = x;//_finish++;//复用insert()insert(end(), x);}void pop_back(){assert(!empty());//_finish--;//复用erase()erase(end() - 1);}void swap(vector<T>& v){//注意：不能直接写成swap(_start,v._start);//swap(_start, v._start);std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}iterator insert(iterator pos, const T& x){assert(pos >= begin() && pos <= end());size_t ret = pos - _start;if (_finish == _endofstorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//必须要更新pos--->迭代器失效pos = _start + len;}iterator cur = _finish;//移动数据// _start         pos                 _finish(tmp)//    1      2     3     4      5while (cur > pos){*cur = *(cur - 1);cur--;}*cur = x;_finish++;return _start + ret;}iterator erase(iterator pos){assert(pos >= begin() && pos < end());//移动数据// _start         pos                 _finish//    1      2     3     4      5size_t len = pos - _start;iterator cur = pos;while (cur < _finish - 1){*cur = *(cur + 1);cur++;}_finish--;return pos;}void PrintVector(){for (auto& e : *this){cout << e << " ";}cout << endl;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}

2. 重要接口注意事项

2.1 const修饰

对于不修改成员变量的函数，如size(),capacity()，需要加上const，否则非const成员不能使用。

2.2 begin()和end()

注意对于常量型也必须写成begin()和end()，不能写成cbegin()和cend()，因为它们是C++11之后为了完整性新增加的，但是范围for迭代器只能替换begin()和end()。

实现代码：

		//Iteratorsiterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

2.3 构造函数

（1）迭代器区间初始化

迭代器区间初始化，使用模板的目的是为了不只是vector类的迭代器区间可以使用，string等其他容器的迭代器区间也可以使用。通过模板，无论我们传入的是哪一个容器的迭代器，都可以进行初始化，比如使用库中的list等。

示例：
我们使用string的迭代器来对vector进行初始化。

实现代码：

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

（2）构造函数冲突问题

发现​问题

我们在使用如下代码想要初始化时，编译器报错。

void testvector4()
{//会报错vector<int> v(10, 1);v.PrintVector();//不会报错//vector<int> v(10u, 1);//v.PrintVector();
}

分析问题

我们想要调用的是第一个构造函数，但是编译器调用了第二个，调用到了我们所写的模板函数中去，由于int是内置类型，push_back时无法进行解引用，因此报错。

如果我们在10后面加上u，仅仅是传参的类型改变，但是却不会报错，程序正确执行，那么因此我们可以确定是类型引发的问题。

10和1这种内置类型如果我们没有额外说明，那么默认都为int类型，因此两个int类型，符合模板构造函数，而我们想要调用的构造函数由于n的类型为size_t，虽然两个int类型也可以调用，但是需要类型提升，比较麻烦，因此编译器在有两个函数参数类型相同的情况下，选择了调用函数模板实例化的函数。

​解决问题

==​因为编译器对于同名函数且参数类型相同的函数调用的规则是：有现有的函数调用现有的，没有现有的函数调用函数模板实例化出来的函数。==因此我们可以进行函数重载，重载一份n为int类型的函数，这样的话编译器就会先调用已经实现的函数啦。

实现代码：

vector(int n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++)push_back(val);}vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++)push_back(val);
}template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

（3）特殊的构造函数的实现

​我们在OJ中经常能看到这种用法：

​ vector<int> v = { 1, 2, 3, 4 ,5};

而我们自己模拟实现的vector则不支持，会报错。

通过查阅文档，了解到这种用法是在C++11以后新增加的用法。
其中initializer list是一个类模板。



通过该构造函数进行初始化，在内部使用其迭代器进行初始化。

实现代码：

vector(initializer_list<T> il)
{//方法一：//const T* it = il.begin();//while (it != il.end())//{//push_back(*it);//it++;//}//方法二：//il本质是一个类，有begin()和end()，因此也可以使用迭代器reserve(il.size());for (auto& e : il){push_back(e);}
}

2.4 insert

注意点

如果扩容，不更新pos的位置，会造成内部的迭代器失效问题。

分析原因

如果空间容量不足，那么会进行扩容，而扩容之后由于reserve内部实现了_start 和 _finish的更新，但是pos的迭代器位置错误造成迭代器失效仍然是一个问题。

图解

代码实现：

iterator insert(iterator pos, const T& x)
{assert(pos >= begin() && pos <= end());size_t ret = pos - _start;if (_finish == _endofstorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//必须要更新pos--->迭代器失效pos = _start + len;}iterator cur = _finish;//移动数据// _start         pos                 _finish(tmp)//    1      2     3     4      5while (cur > pos){*cur = *(cur - 1);cur--;}*cur = x;_finish++;return _start + ret;
}

2.5 push_back

​
注意点：

函数参数要加const，否则会因为权限放大而报错。

​vector<int> v;
​v.push_back(1);
​//1为常量，具有const属性，如果参数不加const则无法使用，会报错

实现代码：

void push_back(const T& x)
{//原始写法//扩容//if (_finish == _endofstorage)//{//	size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//	reserve(newcapacity);//}//*_finish = x;//_finish++;//复用insert()insert(end(), x);
}

2.6 reserve

注意事项：

1.memcpy是按照字节数量进行拷贝的---->在使用时会出现问题 如果是有深拷贝的类 会出错
2.扩容的时候提前保留size--->如果后面_finish直接使用_start + size()，size()在计算时使用的是已经释放空间的_finish，而_start指向的是新空间的开始，因此会报错。
3._endofStorge改变时，不能直接让其等于n，因为类型不同

发现问题

如果对于vector< string >这样的容器，由于string类内部也有申请空间，如果还是使用memcpy就会报错。

分析问题

我们在reserve()的时候重新new空间只是对于vector进行了深拷贝，但是由于string也是一个需要深拷贝的类，我们直接使用memcpy拷贝的是字节，属于浅拷贝，即新旧空间中的str指向同一块地址，而旧空间free之后会把那里的空间释放掉，因此程序会出错。

解决问题

直接使用循坏，对于每一个值都采取赋值构造，因为string的赋值构造内部是已经写好的深拷贝，我们不需要关心其内部是如何实现的。在采取赋值构造时它会自己进行深拷贝。

图解

实现代码：

void reserve(size_t n)
{//不会缩容//错误写法//错因：我们的_start改变了 但是我们的_finsh和_endofstorage还没有改变//在调用size()时会出错 因为我们size()函数求大小时使用了_finish//if (n > capacity)//{//	T* tmp = new T[n];//	memcpy(tmp, _start, sizeof(T) * size());//	delete[] _start;//	_start = tmp;//	_finish = _start + size();//	_endofstorage = _start + n;//}//正确if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());//如果使用memcpy，对于类似vector<string>这样的类，就会出现浅拷贝的现象从而报错for (size_t i = 0; i < oldSize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}
}

2.7 resize

注意事项：

1.分情况
（1）n < size()时由于底层是原生指针因此我们可以直接改变指针的值，不需要循环pop_back()函数，可以直接_start + n
（2）n > size()时复用reserve，因为reserve内部对于空间足够的情况不会处理，只有空间不足时reserve内部才会重新分配空间
2.参数类型的缺省值如何给：匿名对象

实现代码：

void resize(size_t n , const T& val = T())
{if (n > size()){reserve(n);for (size_t i = size(); i < n; i++)push_back(val);}else{//删除//for (int i = size(); i > n; i--)//	pop_back();//我们可以直接改变指针_finish = _start + n;}
}

2.8 swap

​注意：

1.我们想要调用库的swap函数，因此必须指明std命名空间来调用。

因为编译器在搜索时会先搜索到我们实现的vector类中的swap，然后编译器会报错参数不匹配。

调用代码：

void swap(vector<T>& v)
{//错误写法swap(_start, v._start);swap(_finish, v._finish);swap(_endofstorage, v._endofstorage);
}
void testvector4()
{vector<int> v(10, 1);v.PrintVector();vector<int> v1(20, 2);v1.swap(v);
}

程序报错：

实现代码：

void swap(vector<T>& v)
{//注意：不能直接写成swap(_start,v._start);//swap(_start, v._start);std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}

3. vector的迭代器失效

3.1 insert造成的迭代器失效

在vector中insert导致的迭代器失效多为扩容导致的问题。

案例：往容量已满的vector容器中插入值（实现时默认为4个空间）

void testvector6()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator it = v.begin();cout << *it << endl;v.insert(it, 40);cout << *it << endl;
}

输出结果：

分析问题

造成这种问题的原因是因为在insert函数执行时进行了扩容操作，原有的空间被释放，但是it仍然指向被释放的空间，因此打印出来为随机值。

解决方案

错误思路：

可能会有人说，在函数参数部分传引用，这样就可以让迭代器自动更新，但是如果传引用的话，则无法将begin()，end()直接作为参数传递，因为它们的返回值是临时变量，具有常性，如果需要接收则需要在参数部分增加const来修饰，但是增加const之后就不能修改。

正确思路：

​stl库在设计insert函数时增加返回值，从而便于使用返回值来更新迭代器。更新迭代器

3.2 erase造成的迭代器失效

案例：删除值为偶数的位置

场景一：

//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);vector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)v.erase(it);it++;
}
v.PrintVector();

输出结果：正确

场景二：

//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);vector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)v.erase(it);it++;
}
v.PrintVector();

输出结果：结果不符合预期，有跳过

场景三：

//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);vector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)v.erase(it);it++;
}
v.PrintVector();

输出结果：编译器报错

我们从画图的过程来理解为什么相似的几段代码但是结果却不相同。

图解

场景一：

场景二：

场景三：

分析问题

出现上面的原因就是因为迭代器it没有及时更新还在使用所导致的。

解决问题

stl库在设计时erase是有返回值的，其返回值为正确的迭代器，因此每次使用后可以通过接收返回值来更新迭代器。

修改后代码：

//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
v.push_back(6);vector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)it = v.erase(it);elseit++;
}
v.PrintVector();

总结

vector的insert和erase操作都可能使迭代器失效。
迭代器失效以后，不要直接使用，如果需要使用应该按照规则重新更新后使用。

以上是本次所有内容，如有可以提升的地方，希望各位佬可以指点，谢谢观看。

这篇关于C++：一次性搞定vector模拟实现中必须关注的细节的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---