详细解析"/>
STL中vector的详细解析
vector简单的来说就是可变大小数组的可变容器。它的一些常用接口在：vector的相关文档中。它接口的使用和string类似，所以重点不在接口的使用上而是在不熟悉的接口以及接口使用的时候需要注意些什么，话不多说我们就直接开始。
测试vector的扩容机制
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}
vs下的编译结果：
由此可以知道它大概是1.5倍的大小增长。
但是在gcc下编译的结果和vs完全不同：
g++运行结果：linux下使用的STL基本是按照2倍方式扩容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128总结：1.当我们已经提前预知vector中需要存储的数据个数，我们可以用reserve提前预留空间，这样就避免了因为扩容而发生效率低下的问题。
2.一次性扩容2倍左右的空间大小比较合适。如果每次扩容扩少了，会导致频繁的扩容。扩多了，空间用不完，会导致空间的浪费。
接口使用需要注意的几项：
判断成员函数是否需要加const：
一个const对象在调用operator[]函数的时候，只能进行读操作，不能进行写操作。如果是一个普通对象调用的话就可以进行读写操作。而size()接口只能读不能写。由此为我们可以总结一下几点：
只读接口用const。(size)
只写接口用非const。(push_back)
可读可写接口用const+非const。(operator[])
vector与string的一个区别：
那请问一下一下程序为什么会报错呢？？
答案：虽然已经提前为v开辟好了十个数据的空间，但是它的size的大小却只有零，在使用opreator[]函数的时候函数本身会进行检查是否存在越界访问，条件是访问的空间位置必须小于size。（断言错误）
解决方法：1.不用operator[]进行访问，使用push_back进行数据的写入。
2.使用resize（），因为不仅会开空间也还会初始化，一句话来说就是非常好用！
注：如果用at（）函数进行写入也不行，会出现抛异常的情况。
从上面这个图我们可以知道vector中没有实现find的接口，在我们后面的学习中list、dequeue等等容器它们都没有find接口，因为这种统一的接口在每个容器都实现就显得非常麻烦，所以std：中有一个统一的find为我们提供。
注意：
1.迭代器区间是左闭右开！！！另外要记得包含头文件喔！！
2.使用的是类模板算法--复用，所有容器都可以使用！
#include <algorithm> 这样设计的原因：
1.string设计的早（历史原因）
2.string有时候需要找子串（功能原因）
vecotor接口总结：
增：push_back 不直接头插（需要挪动数据，效率低，建议少用）偶尔头插用insert(v.begin(),val)
删：ppop_back 不直接头删（需要挪动数据，效率低，建议少用）偶尔头删（erase(v.begin())
查：用算法库find
改：迭代器+operator[]
vector的底层实现：
我们实现的是sgi版本的，虽然会简化源代码，但是该实现的功能我们都可以实现。
首先是vector的大框架：
#pragma oncenamespace myvector
{template<class T>class vector{public:typedef T* iterator;iterator begin(){return _start;}iterator end(){return _finish;}T& operator[](size_t pos){assert(pos < size());return _start[pos];//return *(_start + pos);}vector():_start(nullptr),_finish(nullptr),_endofstorge(nullptr){}void reserve(size_t n){//它不缩容if (n > capacity()){//先扩容T* tmp = new T[n];//将原先的数据拷贝到新空间,如果没有数据则不需要拷贝if (_start != nullptr){memcpy(tmp, _start, sizeof(T) * size());//拷贝完释放旧空间delete[] _start;}_start = tmp;_finish = _start +size() ;_endofstorge = _start + n;}}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorge - _start;}void push_back(const T& x){if (_finish == _endofstorge){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}private:iterator _start;iterator _finish;iterator _endofstorge;};void test_vector1(){vector<int> vv;vv.push_back(1);vv.push_back(2);vv.push_back(3);vv.push_back(4);for (size_t i = 0; i < vv.size(); ++i){cout << vv[i] << " ";}cout << endl;vector<int>::iterator it = vv.begin();while (it != vv.end()){cout << *it << " ";++it;}cout << endl;}}在代码运行的过程中我们发现程序崩溃了原因出现在push_back()函数：
此时的_finish是nullptr不能进行解引用，那归很结底原因出现在了reserve中。
因为size()接口代表的是_finish-_start，由于_start在上一行代码被更新成了一个新的地址，所以在调用size()的时候正好把_start新地址给删除了，所以_finish找不到新的地址，所以它为nullptr。
解决办法：
优先更新_finish的地址
_finish = tmp + size();_start = tmp;_endofstorge = _start + n;保存旧的size的大小
void reserve(size_t n){//它不缩容if (n > capacity()){size_t oldsize = size();//先扩容T* tmp = new T[n];//将原先的数据拷贝到新空间,如果没有数据则不需要拷贝if (_start != nullptr){memcpy(tmp, _start, sizeof(T) * oldsize);//拷贝完释放旧空间delete[] _start;}//_finish = tmp + size();_start = tmp;_finish = tmp + oldsize;_endofstorge = _start + n;}}实现resize函数的接口我们要分三种情况：
当n>capacity()时，我们需要扩容。
当n>=size() &&n<=capacity()时，我们需要填充数据。
当n<size()时，我们需要删除数据。
void resize(size_t n,T val =T()){if (n > capacity()){reserve(n);}else if (n < size()){_finish = _start + n;}else{while (size() < n){*_finish = val;++_finish;}}}insert导致的迭代器失效问题：
void insert(iterator pos, const T& val){if (_finish == _endofstorge){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;}void test_vector2(){vector<int> vv;vv.push_back(1);vv.push_back(2);vv.push_back(3);vv.push_back(4);vv.insert(vv.begin(), 0);for (size_t i = 0; i < vv.size(); ++i){cout << vv[i] << " ";}cout << endl;}当我们运行test_vector2的时候结果出现了随机值：
这是什么原因呢？（野指针问题）
解决方法的代码：
if (_finish == _endofstorge){int len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}现在让我们看一下下面的代码：
请问it迭代器失效了吗？？？
让我们看结果：
很显然失效了，失效的原因就是野指针的问题。由于插入数据导致异地扩容，迭代器失效。虽然我们之前在insert内部解决了迭代器失效的问题，为什么这边it还是会失效呢？？
void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);if (_finish == _endofstorge){int len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}虽然我们在代码中修改了pos的值，但是我们传入的是形参，形参的改变不会影响实参。所以即使我们在内部解决了迭代器失效的问题，但是在外部问题根本没有被解决。
总结：当我们使用迭代器某个位置进行插入时，不管原来的空间有没有发生异地扩容出现野指针的问题，我们统一的认为在插入操作过后迭代器位置失效！！！所以说迭代器失效后能不使用则不使用！！!
erase导致的迭代器失效的问题：
void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish; }在vs2013下面会报断言错误(其他编译器可能不会报错)，在g++下面编译正常运行。
那么到底迭代器是失效还是不失效呢？？接下来我们采取一个极端情况：删除最后一个数据
这时我们发现pos位置指向了_finish的位置，该位置处在失效的位置。
我们再举一个例子例子：
void test_vector3(){std::vector<int> vv;vv.push_back(1);vv.push_back(2);vv.push_back(3);vv.push_back(4);//删除所有的偶数std::vector<int>::iterator it = vv.begin();while (it != vv.end()){if (*it % 2 == 0){vv.erase(it);}++it;}for (auto e : vv){cout << e << " ";}cout << endl;}程序报错，原因：运行++it的时候会有assert检查，程序报错。
在g++下面运行的结果是这样的：
三种不同的数据对应着三种不同的结果，运行可能不报错但是结果不对。
第一个发生段错误的原因：挪动数据的原因，导致it不能等于end使循环终止，造成越界访问。
第二个结果正确的原因是凑巧，it刚好都指向偶数，正好删除正确。
第三个结果错误的原因是挪动数据再加上++it正好跳过了一个2，所以结果不对。
解决方案：在g++上我们可以这样修改：
while (it != vv.end()){if (*it % 2 == 0){vv.erase(it);}else{++it;}}
这样确实解决了因挪动数据且++it的操作错过了删除数据或者是越界访问，但此代码虽然在g++上得到解决，那么在vs上能够得到完美的解决吗？？看vs的结果：
为什么会出现这种情况？？因为在vs库里的vector的迭代器不像我们模拟实现的那样是个原生指针，它的迭代器使用类封装起来的，检查要求也更加的严格。我们模拟实现的和g++底层的vector差不多，都是sgi版本的，而vs底层用的是pj版本的，所以g++不报错，vs会报错。
erase迭代器失效真正的解决办法：
我们从这张图就可以知道erase返回了一个迭代器！！！！
所以我们可以通过接收返回值解决问题：
std::vector<int>::iterator it = vv.begin();while (it != vv.end()){if (*it % 2 == 0){it=vv.erase(it);}else{++it;}}以上的解决方案都可以在vs和g++都可以跑，所以我们认为erase(it)失效了，更新他以后再去访问。
总结：
迭代器失效的原因：
挪动数据再++it迭代器使原来迭代器的位置不正确了。
极端情况下删除最后一个位置的时候，迭代器不再是有效数据的迭代器位置了。
总之无论在什么平台什么代码下，erase之后迭代器失效！！！！！！！！！！
vector中深拷贝：
拷贝构造的传统写法：
//拷贝构造的传统写法vector(vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorge(nullptr){reserve(v.capacity());for (auto& e : v){push_back(e);}}拷贝构造的现代写法：
首先我们需要抓一个壮丁：
template <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorge(nullptr){while (first != last){push_back(*first);++first;}}然后我们再和壮丁交换空间：
//拷贝构造的现代写法vector(vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorge(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}赋值重载：
当拷贝构造写好的时候我们就可以直接写出赋值重载，当我们传入形参的时候，形参会调用一次拷贝构造创建出新的空间，然后我们就可以直接交换空间了。（现代写法）
vector<T>& opreator = ( vector<T> v){swap(v);return *this;}模板匹配问题：
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):_start(nullptr), _finish(nullptr), _endofstorge(nullptr){while (first != last){push_back(*first);++first;}}
当我们运行test_vector5时报了个间接寻址的错误，主要原因是因为当我们使用vector<int>vv(5,1)初始化的时候想调用的是第一个构造函数，但是默认匹配给我们的是第二个构造函数。
原因：5和1是int类型，第一个默认构造的n是size_t的类型，如果要匹配我们需要隐式类型的转换。
第二个的构造函数的参数都是InputInterator类型，不需要转换直接默认InputInterato就是int。编译器就默认调用的是第二个构造函数，当调用第二个构造函数的时候会进行整型的解引用，所以会导致非法的间接寻址。
解决办法：
我们可以将第一个构造函数n的类型改成int，这样就保证了参数类型传的一样，编译器直接默认调用，但是库里面参数类型就是size_t，所以我们不建议这样修改。
我们传参数的时候可以进行强制类型转换，这样对于用户不方便。
使用库里面的方法:函数重载
vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}vector(int n, const T& val=T()){reserve(n);for (int i = 0; i < n; ++i){push_back(val);}}深拷贝中存在的问题：
void test_vector6(){vector<string>v;v.push_back("1111111111111111111");v.push_back("1111111111111111111");v.push_back("1111111111111111111");v.push_back("1111111111111111111");v.push_back("1111111111111111111");for (auto e : v){cout << e << " ";}cout << endl;}当我们运行以上代码的时候，我们模拟实现的vector程序结果错误，这是为什么呢？？
这是因为当我们插入第五个数据的时候要进行扩容，如果vector涉及深拷贝的话，我们之前实现的代码就有问题了，现在我们通过画图来解释说明一下：
当我们用reserve开辟好一段新空间后，我们将旧数据拷贝到新空间使用的是memcpy函数，此函数是一个浅拷贝，使我们新空间的各个_start指向了旧空间中_start指向的一段空间。当我们使用memcpy结束后使用了delete函数，调用delete不仅会释放原本的旧空间，还会释放旧空间中指向的空间(调用各个部分的析构函数），所以我们新空间中各个部分的_start指向的空间也就被释放了，这样也就造成野指针的问题，打印出来的也就是混乱的数据了。
由此我们也会知道为什么c++更支持用new和delete而不用malloc，calloc和free，原因就是new出来的对象会调用它的构造函数，delete会调用对象的析构函数。虽然此情况delete是程序崩溃，但我们new出来的新空间里面的数据都是被初始化好的不是吗？？
那么该如何解决这种问题呢？
其实也很简单，就是将旧空间的数据拷贝到新空间使之成为一个深拷贝，让新空间的各个_start分别指向独立的空间，我们以用用我们之前的赋值重载来解决这个问题：
void reserve(size_t n){//它不缩容if (n > capacity()){size_t oldsize = size();//先扩容T* tmp = new T[n];//将原先的数据拷贝到新空间,如果没有数据则不需要拷贝if (_start ){//memcpy(tmp, _start, sizeof(T) * oldsize);//拷贝完释放旧空间for (int i = 0; i < oldsize; ++i){tmp[i] = _start[i];}delete[] _start;}//_finish = tmp + size();_start = tmp;_finish = tmp + oldsize;_endofstorge = _start + n;}}讲到这vector就已经全部结束了，创作不易请多多支持!
更多推荐
STL中vector的详细解析
发布评论