STL
什么是STL？
STL(standard template libaray-标准模板库)：是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。
STL的六大组件
vector的使用
vector就是我们经常说的顺序表，它是库里面已经实现好的，我们可以直接使用，但是需要包一个vector的头文件。它和string有很大的相似性，所以简单的就不说了。
构造函数
从构造函数我们可以看到，我们可以用n个val来初始化，或者一段迭代器区间，或者一个vector，都是可以的。
void test() { vector<int> v(10, 1); vector<int> v1(v); vector<int> v2(v1.begin(),v.end()); }
迭代器（iterator）
我们遍历vector可以用迭代器遍历。如果要倒着遍历的话，就需要用rbegin和rend，下面带c的都是const版本的，不可修改。
void test() { vector<int> v; vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; }
它也实现了[]的运算符重载，也可以用for循环像数组一样访问。
void test() { vector<int> v; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } }
resize和reserve
resize还是改变size的大小，reserve还是改变capacity的大小。
resize的n如果比size要小的话，就是充当删除的功能。
void test() { vector<int> v; v.reserve(400); v.resize(10, 2); v.resize(5); }
插入删除数据
- push_back
尾插一个数据
void test() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); }
- pop_back
尾删一个数据。
void test() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.pop_back(); v.pop_back(); v.pop_back(); }
- insert
在某个位置插入一个数据，或这n个数据。
我们可以看到，insert需要我们传迭代器过去，并且返回一个迭代器，返回的这个迭代器就是你插入的那个位置的值的迭代器。
void test() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.insert(v.begin(), 10, 0); v.insert(v.begin(), 0); for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; }
- erase
删除一个数据，或者一段迭代器区间。
void test() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.erase(v.begin()); v.erase(v.begin(), v.end()-1); for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; }
swap
交换两个vector
void test1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int> v1; v1.push_back(2); v1.push_back(2); v.swap(v1); }
vector的模拟实现
结构
我们string是用的和顺序表一样的结构，没有用模板模拟实现，但是，vector我们要用模板来模拟实现，而且结构也和前面的大有不同，但是换汤不换药，还是顺序表的原理。
我们说迭代器是一种类似指针的东西，但是不一定是指针，我们将T*重命名为iterator，也就是迭代器，可以说我们vector这个结构的成员就是三个迭代器，一个指向开始位置，一个指向有效数据的最后一个的下一个位置，还有一个指向空间的最后。
我们知道指针是可以相减的，同类型的指针相减就是两个指针数据的个数，所以size=_finish-_start,同理capacity = _end-_start.
那么我们就先来把简单的接口实现一下：
//我们声明成员变量时给了缺省值，所以这里什么都不用写，都会初始化为nullptr，但是必须有这个函数。 vector() {} ~vector() { delete[] _start; _start = _finish = _end = nullptr; } iterator begin() { return _start; } iterator end() { return _start + size(); } const_iterator cbegin() const { return _start; } const_iterator cend() const { return _start+size(); } size_t size() const { return _finish - _start; } size_t capacity() const { return _end - _start; } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end, v._end); }
上面的这些接口都很简单，就不细讲了。
- reserve和resize
reserve就是扩容逻辑，我们需要先开一个空间，然后把数据拷过去，然后在释放原来的空间，把新的空间给_start即可，然后更新_finish和_end。但是需要注意，我们需要先记录一下之前的size，因为_start修改后，就无法知道以前的_size了。
void reserve(size_t n) { if (n > capacity()) { int sz = size(); T* tmp = new T[n]; if (_start) { for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = tmp + sz; _end = tmp + n; } }
resize还是和string一样，如果修改的size 比之前小的话就是删除，比之前大就是看需不需要扩容，然后插数据就可以了。
void resize(size_t n, const T& val = T()) { if (n <= size()) { _finish = _start + n; } else { reserve(n); while (_finish < _start + n) { *_finish = val; _finish++; } } }
- 插入和删除数据
push_back
和顺序表逻辑一样，直接尾插即可。
void push_back(const T& x) { if (size() == capacity()) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; _finish++; }
pop_back
void pop_back() { assert(size() > 0); _finish--; }
insert
insert和之前不同的是，之前传的是下标，现在传的是一个迭代器，并且插入后返回插入那个数据的迭代器，因为我们插入数据后，那个位置的迭代器的内容就别更新了，或者有可能会扩容，扩容后原本的那个迭代器就失效了。所以我们会返回插入的那个数据的迭代器。
iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); if (size() == capacity()) { //防止迭代器失效 int len = pos-_start; reserve(capacity() == 0 ? 4 : capacity() * 2); //及时更新pos pos = _start + len; } iterator end = _finish; while (end > pos) { *(end) = *(end - 1); end--; } *pos = x; _finish++; return pos; }
erase
还是传一个迭代器，删除这个迭代器位置的数据，同样，这个数据被删除了，同样会是迭代器失效，我们还是会返回一个迭代器，返回的还是这个位置的迭代器，指向被删除的数据的下一个数据。
iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator begin = pos; while (begin < _finish - 1) { *begin = *(begin + 1); begin++; } _finish--; return pos; }
- 构造和赋值重载
我们知道库里面有很多构造，可以用n个val来初始化，也可以用一段迭代器区间，都是一样的思路，直接尾插数据就可以了，但是n个val可以复用resize这个函数。
vector(int n, const T& value = T()) { resize(n, value); } 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) { push_back(e); } }
赋值重载
我们直接拷贝构造一份数据，和this交换。
vector<T>& operator= (vector<T> tmp) { swap(tmp); return *this; }
