文章目录

• 1、vector的基本介绍
• 2、vector的常用接口
• 3、vector部分模拟实现
• 4、vector迭代器失效问题

1、vector的基本介绍

1. vector是表示可变大小数组的序列容器
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长
6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好

2、vector的常用接口

• vector构造函数

• vector iterator 的使用

• vector空间增长问题

1. capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
2. reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题
3. resize在开空间的同时还会进行初始化，影响size

• vector 增删查改

3、vector部分模拟实现

namespace fl{//自己定义命名空间，防止命名污染template<class T>class vector{public: //vector的迭代器是一个原生指针typedef T* iterator;//普通迭代器typedef const T* const_iterator;//const修饰的迭代器template<class InputIterator>//函数模板，通过两个迭代器构造vector// 若使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器 // 重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);//插入数据first++;}}  //用来交换vector中的变量，也就是交换3个迭代器所指向的位置，相当于交换了空间void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);} //无参构造vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}//v2(v1)//传统写法//vector(const vector& v)//{//_start = new T[v.capacity()];//_finish = _start + v.size();//_endofstorage = _start + v.capacity();////memccpy(_start, v._start, sizeof(T)*v.size());//// 这里也要一个个赋值跟reserve中一样//for (int i = 0; i < v.size(); i++)//{//_strat[i] = v._start[i];//}//}//v2(v1)//现代写法//vector(const vector& v)vector(const vector<T>& v)//这里不能写成 vector(vector v)，因为v1传给v时，会发生拷贝构造，相当于自己调用自己:_start(nullptr), _finish(nullptr), _endofstorage(nullptr){vector<T> tmp(v.begin(), v.end());////相当于this->swap(tmp);swap(tmp);}//v2 = v1//现代写法//vector& operator=(vector v)vector<T>& operator=(vector<T> v){swap(v);return *this;}//析构~vector(){if (_start)//如果_start为nullptr，则不做处理{delete[] _start;_start = _finish = _endofstorage = nullptr;}} iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}  //[]重载，可读不可写，const对象调用const T& operator[](size_t i) const{assert(i < size());return _start[i];} //[]重载，可读可写，const对象调用T& operator[](size_t i){assert(i < size());return _start[i];} //返回有效数据的个数size_t size() const{return _finish - _start;} //返回空间大小size_t capacity() const{return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){// memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中//如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，//并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝//所以不能使用memcpy//memcpy(tmp, _start, sizeof(T)*sz());for (size_t i = 0; i < sz; i++){//如果T是int，没问题//如果T是string，也没问题，因为STL中string的赋值是深拷贝tmp[i] = _start[i];}delete[] _start;}_start = tmp;// _finish = _start + size(); size()有问题，因为_start已经被更新，但_finish没有被更新，所以需要提前算出sz_finish = _start + sz;//更新_finsh_endofstorage = _start + n;//更新_endofstorage}} //如果没有传val，则会使用缺省值，然后调用T(T是模板参数)的构造函数void resize(size_t n, const T& val = T()){if (n < size())//相当于缩容，但实际的空间不变，只是改变_finish，就能达到缩容的效果{_finish = _start + n;}else{if (n > capacity())//空间不够就需要扩容{reserve(n);}while (_finish != _start + n)//将_finish后面的空间都赋值val{*_finish = val;++_finish;}}}void push_back(const T& val){if (_finish == _endofstorage)//空间不够就扩容{reserve(capacity() == 0 ? 4 : capacity() * 2);//防止对nullptr扩容}*_finish = val;++_finish;}void pop_back(){assert(_finish > _start);--_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);//确保pos位置合法//满了就扩容if (_finish == _endofstorage){//扩容会导致pos失效，所以扩容前先保存一下size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;//挪动数据，从后往前挪，挪动完成后，pos的位置已经被空出来了while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(size() > 0 && pos >= _start && pos < _finish);//确保pos位置合法iterator begin = pos + 1;     //挪动数据，从前往后挪while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}private:iterator _start;//第一个位置iterator _finish;//有效数据后一个元素iterator _endofstorage;//有效空间的后一个位置};}

关于memcpy的建议：
如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃

4、vector迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)

对于vector可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back

v.resize(100, 8)： 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
v.reserve(100)： reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
v.insert(v.begin(), 0)：插入元素期间，可能会引起扩容，而导致原空间被释放
v.assign(100, 8)： 给vector重新赋值，可能会引起底层容量改变

出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
空间，而引起代码运行时崩溃

2. 指定位置元素的删除操作–erase

先看以下代码：

#include using namespace std;#include int main(){ int a[] = { 1, 2, 3, 4 }; vector<int> v(a, a + sizeof(a) / sizeof(int)); // 使用find查找3所在位置的iterator vector<int>::iterator pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据，导致pos迭代器失效。 v.erase(pos); cout << *pos << endl; // 此处会导致非法访问 return 0; }

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效
了

void test_vector(){// 三种场景去测试//导致这这三种问题的本质是eraser(it)以后，it的意义变了，再去++it是不对的// 例1: 1 2 3 4 5 -> 正常(纯属巧合)// 例2: 1 2 3 4   -> 崩溃// 例3: 1 2 4 5   -> 没删除完vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);// 要求删除v1所有的偶数vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);//如果是vs中的erase，会报错，因为vs会对it进行强制检查，不能再使用已经使用过的迭代器}++it;}

例1结果：

例2结果：

例3结果：

如果使用vs库中的vector，用上述例子测试，这都会报错，原因是vs会对it进行强制检查，不能使用已经被使用过的迭代器

迭代器失效解决办法：在使用前，对迭代器重新赋值即可