前言：
在之前，我们已经对 string类进行了基本的概述，并且手动的实现了string类中常用的接口函数。本期，我将带领大家学习的是STL库中的一个容器 -- vector 的学习。相比于之前的string类，本期的 vector 相对来说实现起来略微难一点，难点就在于要考虑关于 “迭代器失效”方面和“深浅拷贝”的问题。
前言
在正式的学习之前，我们先来看看STL库中的容器有哪些，让大家先混个脸熟，在接下来，对于其他的容器我也会给大家进行相关的讲解。
- STL库中的容器如下（勾画的接下来我都会给大家讲解）：
💨 而对于 map、set等则是要等到之后在给大家讲解，因为要涉及关于 红黑树的相关知识；
💨 而对于像第一个【arry】这个我们十分的熟悉了，就没有必要在进行讲解了，而【deque】和【queue】二者之间也有很多的不同之处；
💨 而对于【bitset】（位集），我们只需简单的了解即可，它主要的功能是提供一些成员函数，使程序员不必通过位运算就能很方便地访问、修改其中的任意一位。
（一）基本介绍
1、相关定义
既然要学习vector，那么首先就需要知道到底什么是vector，定义如下：
- vector是STL库中的一种序列式容器，事实上和数组差不多（但它比数组更优越），由于其大小(size)可变，常用于数组大小不可知的情况下来替代数组。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。
2、vector的引入
- 一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界；
- 而 vector 正好弥补了这个缺陷，它不像数组那样，它的大小是可以动态改变的，相当于可拓展的数组（动态数组），它的随机访问快，在中间插入和删除慢，但在末端插入和删除快，而且它的大小会被容器自动处理。
3、vector的优点
- 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效；
- 对于其它不在末尾的删除和插入操作，效率更低；
- 比起list 和 forward_list 统一的迭代器和引用更好。
4、vector使用本质
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。
其做法是：分配一个新的数组，然后将全部元素移到这个数组。
就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
（二）vector的使用
vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。
1、vector的定义
2、vector iterator 的使用
3、vector的空间增长
4、vector的增删查改
大家通过文档不难发现，vector容器跟之前学习的string类的接口很相似。因此，通过之前对string的学习，并且掌握的话对于本次学习的vector学习到掌握是很容易的！！！
（三）接口函数的介绍
接下来，我就将为大家介绍常用的接口以及实现的过程！！！
1、Member functions
对于构造，我们通过阅读文档可以发现，文档给出的构造有四种，分别是：
- 默认构造
- n个val构造
- 迭代区间构造
- 拷贝构造
接下来，我直接给大家展示相关方法是如何进行函数构造的。
1️⃣n个val构造
- 代码如下：
void test1() { //n个val构造 vector<int>arr(10,1); //ten ints with value 1 for (int i = 0; i < arr.size(); ++i) { cout << arr[i] << " "; } cout << endl; } int main() { test1(); return 0; }
- 解释说明：
上述代码我们构造包含 10个元素的容器。每个元素都是 1 的副本。
2️⃣迭代区间构造
- 代码如下：
void test() { vector<int>arr(10,1); //迭代区间构造 vector<int>tmp(arr.begin(), arr.end()); for (int i = 0; i < tmp.size(); ++i) { cout << tmp[i] << " "; } cout << endl; } int main() { test(); return 0; }
- 解释说明：
上述通过构造一个容器，其中包含与范围 [first、last）（特别注意迭代区间的范围是左闭右开） 一样多的元素，每个元素都以相同的顺序从该区域中的相应元素构造。
拓展说明：
对于迭代器构造，不知道大家有没有发现文档中给出的描述：
迭代器不应该叫做【iterator】吗，这里怎么叫做【inputiterator】呢？
- 这就要说到一个问题了，那就是迭代器是分类型的（说起来很复杂，我简单讲一下）。
- 不同的迭代器除了之前说过的正向、反向 这样的使用属性之外，还有相关的特性属性，比如双向、单向等；
- 因此在这里就表示你使用时即可传单向，也可以传双向，以及随机等（即可以传任意类型）
例如以下：
string str("have a good day"); vector<int>vv(str.begin(), str.end()); for (int i = 0; i < vv.size(); ++i) { cout << vv[i] << " "; } cout << endl;
输出的即是对应的 ASCll 码值。除此之外，还可以进行【++】或【--】操作。
3️⃣拷贝构造
- 代码如下：
void test() { vector<int>arr; //默认构造 arr.push_back(1); arr.push_back(2); arr.push_back(3); arr.push_back(4); arr.push_back(5); //拷贝构造 vector<int> tmp(arr); for (auto e : tmp) { cout << e << " "; } cout << endl; }
- 解释说明：
复制构造函数，以相同的顺序构造一个容器，其中包含 arr 中每个元素的副本。
2、Iterators
接下来就是关于正向迭代器和反向迭代器的介绍，这个我相信大家在之前的学习中都有了解，我就不过多阐述。
1️⃣begin()和end()
- 代码如下：
void test() { vector<int>arr; arr.push_back(1); arr.push_back(2); arr.push_back(3); arr.push_back(4); arr.push_back(5); vector<int>::iterator it = arr.begin(); while (it != arr.end()) { cout << *it << " "; it++; } cout << endl; }
2️⃣rbegin()和rend()
- 代码如下：
void test() { vector<int>arr; arr.push_back(1); arr.push_back(2); arr.push_back(3); arr.push_back(4); arr.push_back(5); vector<int>::reverse_iterator rit = arr.rbegin(); //auto rit = arr.rbegin(); while (rit != arr.rend()) { cout << *rit << " "; rit++; } cout << endl; }
3、Capacity
对于容量的相关接口，跟之前学的string是类似的。
这里需要讲明的一点是关于 【capacity】扩容的问题，capacity的代码在 vs 和 g++ 下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。 这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义 的。vs是PJ版本STL，g++是SGI版本STL。
- 用以下测试代码分别在两种环境下运行后：
// 测试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下的结果：
- 在g++下的结果：
接下来，对于reserve 和 resize，我们在后面的接口函数模拟实现上具体的讲解，以及带大家来理解迭代器失效的问题！！
（四）vector模拟实现
1、成员变量
我这里的实现风格整体来说是按照库里面的实现方式来进行操作的（如果大家有兴趣，可以去库里面看下源码）
- 首先，我们这里实现的vector是 typedef出来的，具体如下（分为普通版本和const版本）：
typedef T* iterator; typedef const T* const_iterator;
- 而对于类的成员变量如下：
private: iterator _start; iterator _end; iterator _end_of_storage;
- 解释说明：
⚔️ _start：表示指向数据的开始位置；
⚔️ _end：表示指向数据的结尾位置的下一个位置；
⚔️ _end_of_storage：表示的是整个空间的大小。
2、成员函数
1️⃣构造函数
这些都跟之前是一样的，在这里就不多说了，具体如下：
vector() : _start(nullptr) , _end(nullptr) , _end_of_storage(nullptr) {}
2️⃣析构函数
~vector() { if (_start) { delete[] _start; _end = _end_of_storage = _start = nullptr; } }
3️⃣拷贝构造
- 现代写法：
//现代写法 vector(const vector<T>& arr) { vector<int> tmp(arr.begin().arr.end()); swap(tmp); }
- 传统写法：
vector(const vector<T>& arr) { _start = new T[arr.capacity()]; for (size_t i = 0; i < arr.size(); ++i) { _start[i] = arr._start[i]; } _end = _start + arr.size(); _end_of_storage = _start + arr.capacity(); }
3、迭代器
1️⃣begin() 和 end()
这里我提供了两个版本的，分别是普通版本和const版本的实现。
- 具体如下：
iterator begin() { return _start; } iterator end() { return _end; } const_iterator begin()const { return _start; } const_iterator end()const { return _end; }
对于反向迭代器，我放在之后的学习中再去讲解，因为将会涉及一些其他的东西在里面。
4、容量
1️⃣size()
理解：这应该很容易理解，对于有效位数据位的大小，就为【_end】位置与【_start】位置的距离为多少。
- 具体如下：
//长度大小 size_t size()const { return _end - _start; }
2️⃣capacity()
理解：对于数据所占空间的大小，就为首元素位置与整体空间大小的差值。
- 具体如下：
//空间大小 size_t capacity()const { return _end_of_storage - _start; }
3️⃣empty()
- 具体如下：
bool empty() { return _start == _end; }
4️⃣reserve()
特点：reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
- 代码展示：
void reserve(size_t n) { //首先先判断是否需要开辟新空间 if (n > capacity()) { //开新空间 T* tmp = new T[n]; if (_start) { //元素拷贝到新空间 memcpy(tmp, _start, sizeof(T)*size()); //释放旧空间 delete[] _start; } _start = tmp; _end = tmp + size(); _end_of_storage = tmp + n; } }
上述模拟实现的vector中的reserve接口中，会使用 memcpy 进行的拷贝，但是大家通过代码有没有发现什么问题呢？
- 当我们用测试用例去打印结果的时候，会发生程序挂掉了：
- 我们通过调试去观察是什么原因导致的问题，具体如下：
现象解释：
- 首先，我们知道size() = _end - _start;
- 按理说释放之后应该为0，因为 tmp=_start，因此我们可以把上述带入公式带入代码中换掉，我们就不难得出一点，此时代码就为 【tmp + _end - _start(tmp) 】，所以此时最终为0了；
- 相当于_start 是一个地址，而最终却是 0 减 一个地址。即_end 还是之前的，而_start 却不是之前的_start 了；
- 因此，最好的解决办法就是在事先保留一份最初的 size() 即可。
- 代码如下：
void reserve(size_t n) { //首先先判断是否需要开辟新空间 if (n > capacity()) { size_t num = size(); //开新空间 T* tmp = new T[n]; if (_start) { //元素拷贝到新空间 memcpy(tmp, _start, sizeof(T)*size()); //释放旧空间 delete[] _start; } _start = tmp; _end = _start + num; _end_of_storage = _start + n; } }
最终通过上诉我们得出一点：
- 如果拷贝的是 自定义类型的元素，memcpy既高效又不会出错；
- 但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是 浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
5️⃣resize()
resize在开空间的同时还会进行初始化，影响size。
- 代码展示：
void resize(size_t n, const T& val = T()) { if (n < size()) { _end = _start + n; } else { if(n > capacity()) reserve(n); while (_end != _start + n) { _end = val; ++_end; } } }
- 注意这里的val初始化时初始化为 T()；
- 当单独使用T()时，当前行结束就会自动调用销毁，而当时用 const T& val =T() 就可以延长生命周期。
5、元素访问
1️⃣operator[]
- 代码展示：
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; }
6、修改
1️⃣push_back()
//尾插 void push_back(const T& X) { //先判断空间 if (_end == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } //移动元素 *_end = X; ++_end; }
2️⃣pop_back()
void pop_back() { assert(!empty()); //注意判空 --_end; }
3️⃣insert()
意思很简单，即在 pos 位置出插入 val 元素即可。但是这里却有一个很坑的点，那就是不小心写出来的代码就会引起迭代器失效的问题。
- 大家先看以下代码：
void insert(iterator pos, const T& val) { assert(pos >= _start); assert(pos <= _end); if (_end == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } iterator finish = _end - 1; while (finish >= pos) { *(finish + 1) = *finish; --finish; } *pos = val; ++_end; }
此时，数组中只有4个元素（即数组中有四个元素），当我们想在第三个位置处插入元素0时，我们打印对应的结果，就会发现结果报错:
但是，当我们提前先把 5 也放入数组（即数组中有5个元素），此时再去进行插入操作时，结果又是正确的：
那么上述是什么问题导致的呢？我们先调试看看：
解释说明：
- 通过上述我们不难看出一个问题，程序只走了一步扩容操作，pos 位置此时没有发生变化，而 _start 和 _end 已经发送改变了。
- 此时这种情况就是一种经典的迭代器失效现象
解决方法：
- 我们需要更新 pos位置 ，根据相对位置来判断扩容之后处于新空间的位置是多少。
- 纠正写法：
void insert(iterator pos, const T& val) { assert(pos >= _start); assert(pos <= _end); if (_end == _end_of_storage) { size_t len = pos - _start; //迭代器失效问题（野指针） reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } iterator finish = _end - 1; while (finish >= pos) { *(finish + 1) = *finish; --finish; } *pos = val; ++_end; }
但是上述改了之后是不是就 ok l呢？其实并不是的，程序其实还有 bug。
此时，很多小伙伴就会说我都已经更新了pos呀，但是我们经过调试之后发现没有起作用在这里：
解释说明：
- 最主要的原因就是这里是值传递，形参的改变是不会改变实参的，所以说外面的pos依旧没有实现更新操作，依旧会失效。
💨 正确写法是通过返回值去解决问题的，返回的是迭代器，即新插入元素的位置
- 正确代码：
iterator insert(iterator pos, const T& val) { assert(pos >= _start); assert(pos <= _end); if (_end == _end_of_storage) { size_t len = pos - _start; //迭代器失效问题（野指针） reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } iterator finish = _end - 1; while (finish >= pos) { *(finish + 1) = *finish; --finish; } *pos = val; ++_end; return pos; }
4️⃣erase()
这里主要的就是从后往前删除的，这点需要大家注意一下。
- 代码如下：
void erase(iterator pos) { assert(pos >= _start); assert(pos < _end); iterator start = pos + 1; while (start != _end) { *(start - 1) = *start; ++start; } --_end; }
此时问题又来了，上述这样写会不会也有迭代器失效的问题呢？
💨 首先，我们简单的测试一下：
- 从上述结果我们不难发现，经过验证程序是没有问题的。
💨 接下来，我们在去看看在库中表现如何：
解释说明：
- erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代 器不应该会失效;
- 但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是 没有元素的，那么pos就失效了.因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效 了。
- 如果大家下去验证，发现不管是不是在结束的位置，编译器都会默认程序崩溃。
我们通过调试可以发现，库中默认的检查手段直接就是使得程序发送崩溃了：
注意：
- 说明一点的是代码的结果还跟环境有关，大家可以去linux下进行测试看看结果是怎么样的
💨 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效：
void TestString() { string s("hello"); auto it = s.begin(); // 放开之后代码会崩溃，因为resize到20会string会进行扩容 // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了 // 后序打印时，再访问it指向的空间程序就会崩溃 //s.resize(20, '!'); while (it != s.end()) { cout << *it; ++it; } cout << endl; it = s.begin(); while (it != s.end()) { it = s.erase(it); // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后 // it位置的迭代器就失效了 // s.erase(it); ++it; } }
终上所述，我们认为在erase之后，pos是会发生失效的，因此建议不要访问，行为结果未定义（具体跟编译器有关系）
5️⃣swap()
void swap(vector<T>&arr) { swap(_start, arr.start); swap(_end, arr.end); swap(_end_of_storage, arr._end_of_storage); }
总结
到此，关于vector的全部内容便讲解完毕了，接下来我们简单的总结一下本文都学了什么
- 首先，在开头我先给大家介绍了关于 STL库中的容器有哪些，让大家初步的认识了各个容器，对其有个基本的印象；
- 其次，先给出了关于vector的基本概念介绍，让大家知道vector的作用以及优势；
- 接下来，我们通过结合文档内容，带大家去认识了vector中最常用的接口并模拟实现了各个函数接口；
- 最后，关于vector最重要的便是关于迭代器失效的问题以及解决方法（重点）需要大家掌握。
以上全是全文的基本内容了。感谢大家的阅读与支持！！！
