一、STL
1.1 什么是STL?
STL(standard template libaray-标准模板库)：是C++标准库的一部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。
1.2 STL的版本
- 原始版本：Alexander Stepanov、Meng Lee在惠普实验室完成的版本，本着开源精神，它们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码，无需付费。唯一的条件就是也需要像原始版本一样做开源使用。HP版本是所有STL的祖先。
- P.J版本：由P. J. Plauger开发，继承自HP版本，被微软（Windows Visual C++）采用，不能公开或修改，缺陷：可读性比较低，符号命名比较怪异。
- RW版本：由Rouge Wage公司开发，继承自HP版本。被C++Builder采用，不能公开或修改，可读性一般。
- SGI版本：由Silicon Graphics Computer Systems，Inc公司开发，继承自HP版本。被GCC（Linux）采用，可移植性好，可公开、修改甚至贩卖，从命名风格和编程风格上看，阅读性非常高。建议大家在学习STL的过程中，可以参考这个版本的源代码。
1.3 STL的六大组件
二、vector的介绍及使用
2.1 vector的介绍
- vector 是表示可变大小数组序列容器。
- 就像数组一样，vector 也采用连续的存储空间来存储元素。也就意味着可以采用小标对 vector 的元素进行访问，和数组处理一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 本质讲，vector 使用动态分配数组来存储它的元素。当新元素插入时，为了增加存储空间，这个数组需要被重新分配大小。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价较高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
- vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因此存储空间（容量）比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候实在常数时间复杂度完成的。
- 因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
- 与其它的动态序列容器相比（如：deque、list、forward_list），vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率会比较低。
2.2 vector的使用
vector 学习时一定要学会查看文档：vector的文档介绍，vector 在实际中非常重要，在实际中我们熟悉常用的接口就可以，下面列出了需要我们重点掌握的接口。
2.2.1 vector的定义
| 构造函数声明 | 接口说明 |
| vector() | 无参构造 |
| vector(size_type n, const value_type& val = value_type()) | 构造并初始化 n 个 val |
| vector(const vector& x) | 拷贝构造 |
| vector(Inputlterator first, Inputiterator last) | 使用迭代器区间进行初始化构造 |
小Tips：size_type 表示一个无符号整数类型，value_type 是第一个模板参数，也就是要存储的数据类型。使用迭代器区间的构造函数是函数模板，只要是满足 Input 类型的迭代器都可以使用该构造函数。
int TestVector1() { vector<int> first; vector<int> second(4, 100); vector<int> third(second.begin(), second.end()); vector<int> fourth(third); int myints[] = { 16,2,77,29 }; vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int)); cout << "The contents of fifth are:"; for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) cout << ' ' << *it; cout << '\n'; return 0; }
2.2.2 vector iterator
| iterator的使用 | 接口说明 |
| begin + end | 获取第一个数据位置的 iterator / const_iterator，获取最后一个数据下一个位置的iterator / const_iterator |
| rbegin + rend | 获取最后一个数据位置的 reverse_iterator，获取第一个数据前一个位置的 reverse_iterator |
void PrintVector(const vector<int>& v) { // const对象使用const迭代器进行遍历打印 vector<int>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; }
2.2.3 vector空间增长问题
| 容量空间 | 接口说明 |
| size() | 获取数据个数 |
| capacity() | 获取容量大小 |
| empty() | 判断是否为空 |
| resize(size_type n); resize (size_type n, const value_type& val) | 改变 vector 的 size |
| reserve(size_type n) | 改变 vector 的 capacity |
- vs 和 g++ 的扩容机制有所不同，vs 下 capacity 是按照 1.5 倍增长的，g++ 是按照 2 倍增长的。vs 是 PJ 版本 STL，g++ 是 SGI 版本 STL。
- reserve 只负责开辟空间，如果确定知道需要多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。
- resize 在开空间的同时还会进行初始化，影响 成员变量 _size。
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 下的结果：
Linux 下的结果：
小Tips：如果已经确定 vector 中要存储元素的大概个数，可以提前将空间设置足够，就可以避免边插入边扩容导致效率低下的问题。
void TestVectorExpandOP() { vector<int> v; size_t sz = v.capacity(); v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容 cout << "making bar 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'; } } }
2.2.4 vector增删查改
| vector 增删查改 | 接口说明 |
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找（这个是算法模块实现，不是 vector 的成员接口） |
| insert | 在 position 之前插入 val |
| erase | 删除 position 位置的数据 |
| swap | 交换两个 vector 的数据空间 |
| operator[ ] | 像数组一样访问，通过断言来检查，而 at 是通过抛异常 |
//经典的错误 void Testerro() { vector<int> v1; v1.reserve(10); for (size_t i = 0; i < 10; i++) { v1[i] = i; } }
注意：上面的代码虽然给 v1 提前开了 10 个空间，但是 v1 中的有效元素个数还是 0，即 v1.size() 的返回值是0，这样一来我们就不能直接通过下标去访问 vector 对象中的每一个元素，因为 operator[ ] 实现中的第一步就是检查下标的合理性，防止越界访问，执行 assert(pos < _size)，而此时 _size 是 0，就会出错。上面的代码只需要把 reserve 改成 resize 就可以正常运行，因为 resize 会改变 _size 的大小。如果硬要使用 reserve 提前开空间，那么接下来要使用 push_back 来插入数据。
2.3 vector<char> 可以替代 string 嘛？
答案是不可以，虽然他们俩的底层本质上都是动态增长的数组，但是 string 字符串的结尾默认有 \0，可以更好的兼容 C 接口，而 vector<char> 的结尾默认是没有 \0 的，需要我们自己插入。
三、vector模拟实现
3.1 成员变量
public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; iterator _finish; iterator _end_of_storage;
3.2 成员函数
3.2.1 构造函数
vector() :_start(nullptr) , _finish(nullptr) ,_end_of_storage(nullptr) {} vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { resize(n, val); } vector(int n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { resize(n, val); } //迭代器区间初始化 template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); first++; } }
小Tips：迭代器区间初始化采用的是函数模板，因为它可能使用不同类型的迭代器。其次需要单独提供一个 vector(int n, const T& val = T())，因为迭代器区间初始化采用的是函数模板，如果不单独提供这种构造函数的话，vector<int> v1(10, 1) 这种情况会去走最匹配的，即和迭代器区间初始化函数匹配，而我们希望它走 vector(size_t n, const T& val = T()) 构造函数，但是 10 会被当做 int 型，和 size_t 匹配不上，因此就会去和迭代器区间初始化函数进行匹配，InputIterator 就会被实例化成 int 型，函数中会对 int 型解引用，就会报错，其次逻辑也不符。因此需要针对 int 单独提供一个构造函数。
3.2.2 拷贝构造
//方案一 vector(const vector<T>& V) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { iterator tmp = new T[V.capacity()]; //memcpy(tmp, V._start, sizeof(T) * V.size()); for (size_t i = 0; i < V.size(); i++) { tmp[i] = V._start[i]; } _start = tmp; _finish = _start + V.size(); _end_of_storage = _start + V.capacity(); } //方案二 vector(const vector<T>& V) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(V.capacity()); for (auto e : V) { push_back(e); } }
小Tips：这里设计深拷贝问题，在下文的 reserve 中会提到。
3.2.3 operator=
void swap(vector<T> v) { std::swap(v._start, _start); std::swap(v._finish, _finish); std::swap(v._end_of_storage, _end_of_storage); } vector<T>& operator=(vector<T> v)//调用拷贝构造函数 { swap(v); return *this; }
3.2.4 size
size_t size() const { return _finish - _start; }
3.2.5 capacity
size_t capacity() const { return _end_of_storage - _start; }
3.3.6 迭代器相关
iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
3.2.7 reserve（深拷贝问题）
void reserve(size_t new_capacity) { if (new_capacity > capacity()) { iterator tmp = new T[new_capacity]; if (_start)//如果原来的_start申请过空间，要先将源空间中的内容拷贝过来 { memcpy(tmp, _start, sizeof(T)*size()); delete[] _start; } size_t vsize = size(); _start = tmp; _finish = tmp + vsize;//记得更新_finish _end_of_storage = _start + new_capacity; } }
注意：这里需要更新 _finish 和 _end_ofstorage，因为他俩表示的是位置。要更新 _finish，首先要将 size() 保存一下，因为更新 _start 后，_start 指向新空间的开头，而 _finish 指向旧空间的结尾，此时去调用 size()，计算出来的个数是有问题的，因此需要再更新 _start 之前就将原来的元素个数，即 size() 保存一份。
小Tips：上面这种扩容逻辑，当 T 是内置类或者是无需进行深拷贝的自定义类型来说，是完全满足的。但是当 T 是需要进行深拷贝的内置类型时，上面这种扩容方式就会出现大问题。以 vector<string> 为例，即当 T 是 string 的时候。
如上图所示，如果简单的用 memcpy 将旧空间的数据拷贝到新空间，那么新旧空间中存储的 string 对象指向同一个堆区上的字符串，接着在执行 delete[] _start; 销毁旧空间的时候，由于该 _start 是一个 string* 的指针，所以会先调用 string 的析构函数，将对象中申请的空间释放，即释放 _str 指向的空间，接着再去调用 operator delete 函数释放 string 对象的空间。这样一来，新空间中存储的 string 对象就有问题了，它们的成员变量 _str 指向的空间已经被释放了。这里的问题就出在 memcpy 执行的是浅拷贝。我们可以对上述代码稍作修改即可：
void reserve(size_t new_capacity) { if (new_capacity > capacity()) { iterator tmp = new T[new_capacity]; if (_start)//如果原来的_start申请过空间，要先将源空间中的内容拷贝过来 { //memcpy(tmp, _start, sizeof(T)*size()); for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } size_t vsize = size(); _start = tmp; _finish = tmp + vsize;//记得更新_finish _end_of_storage = _start + new_capacity; } }
修改后执行tmp[i] = _start[i]; 会去调用 string 对象的赋值运算重载，进行深拷贝。
3.2.8 resize
void resize(size_t n, const T& val = T())//缺省参数给的是一个匿名对象 { if (n > size()) { //检查容量，扩容 if (n > capacity()) { reserve(n); } //开始填数 iterator it = end(); while (it < _start + n) { *it = val; it++; } } _finish = _start + n; }
3.2.9 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]; }
3.2.10 insert（迭代器失效问题）
iterator insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); size_t rpos = pos - _start;//保存一下pos的相对位置 //检查容量 if (_finish + 1 >= _end_of_storage) { size_t old_capacity = capacity(); reserve(old_capacity == 0 ? 4 : old_capacity * 2); } pos = _start + rpos;//更新pos //插入数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } *pos = val; _finish++; return pos; }
注意：在进行 insert 的时候，会引发一个著名的问题——迭代器失效。我们希望在 pos 位置插入一个数据，pos 是一个迭代器。在插入数据之前要先检查容量，进行扩容，如果执行了扩容逻辑，_start、_finish、_end_of_storage 都指向了新空间，旧空间已经被释放了，而 pos 指向的还是原来空间中的某个位置，此时 pos 就变成了野指针，再去 pos 指向的位置填入数据，就会造成非法访问。为了避免这个问题，我们可以先保存一下 pos 的相对位置，扩完容之后再去更新 pos。
小Tips：保存相对位置更新 pos，是 insert 函数内部的解决方式，由于是传值传参，形参的 pos 更新，并不会改变实参的 pos，因此为了解决外部的迭代器失效问题，这里采用返回值的方式，将更新后的 pos 返回。可能会有小伙伴觉得，直接把形参的 pos 变成引用不香嘛？这样对形参的更新就相当于是对实参的更新。想法很好，但是不现实，因为实参很有可能具有常性，例如实参如果用 begin()、end()，他俩都是传值返回，会产生一个临时变量，该临时变量具有常性，如果形参 pos 用引用的话，就需要加 const 进行修饰，但是！但是！！如果用 const 进行修饰，那在函数内部就不能对 pos 进行更新。因此形参 pos 不能用引用。
总结：会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、
push_back等。
3.2.11 erase（迭代器失效问题）
iterator erase(iterator pos) { assert(pos >= _start && pos <= _finish); iterator cur = pos + 1; while (cur != _finish) { *(cur - 1) = *cur; cur++; } _finish--; return pos; }
注意：erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 _finish 的位置，而 _finish 位置是没有元素的，那么 pos 就失效了。因此，删除 vector 中任意位置上的元素时，VS 就认为该迭代器失效了（VS 是通过自己重写的 iterator 进行强制检查）。Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。为了解决外部的迭代器失效问题，这里还是采用返回值的方式，返回 pos 下一个位置元素的迭代器。
3.2.12 pop_back
//直接复用即可 void pop_back() { erase(--end()); }
四、结语
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！
