概述
vector是STL的容器之一。vector的底层结构类似于数组——在内存中开辟一块连续的空间。与数组不同的是vector可以动态的改变空间的大小（扩容或缩容）。
vector一般不会缩容，而是会经常的扩容——扩容的大小总比用户需要的多，这和vector的扩容机制有关。
vector不支持原地扩容，会新开辟一块更大的空间。将旧空间的值浅拷贝给新空间，然后释放旧空间。vector的空间的动态改变是有代价的，尤其是数据量特别大时，不会轻易缩容。
不同平台的扩容原则是一样的，但扩容的细节并不相同。VS下是根据旧空间的1.5倍扩容，g++是根据旧空间的2倍扩容。
迭代器
vector的迭代器不需要像list的那样把普通指针进行封装，
因为vector维护的是一段线性空间，它的底层是一块连续的空间。普通的指针刚好能完成数据的随机访问，空间的遍历，数据的存取等。下面是迭代器的源码定义。
templat <class T, class Alloc = alloc> class vector { //...... protected: iterator start; iterator finish; iterator end_of_storage; //...... }
T*就是vector的迭代器。如果vector存的是int类型的数据，vector的迭代器就是int*类型的指针。存的如果是string类（自定义类型）类型的数据，vector的迭代器就是string*类型的指针。
迭代器失效
扩容会引发迭代器失效。首先获取了一个空间的迭代器，然后这个空间发生了扩容，此时这个迭代器是指向旧空间的，旧空间会被归还给操作系统。这种情景下的迭代器失效可以理解为野指针问题。VS环境下会强制报错。如下图
数据结构
vector管理线性空间用了三个迭代器，如下是源代码定义
templat <class T, class Alloc = alloc> class vector { //...... protected: iterator start; iterator finish; iterator end_of_storage; //...... }
start——指向空间的开头
finish——指向有效数据的下一个位置
end_of_storage——指向有效空间的下一个位置
优点和缺点
优点：支持随机访问，排序消耗的时间复杂度比其他容器低
有如下代码，验证三大容器vector， list， deque，在相同数据量，相同数据，数据的顺序也相同的情况下，用vector容器的排序有多大优势。在release环境下验证
#include<vector> #include<list> #include<deque> #include<algorithm> #include<time.h> #include<iostream> void Test() { //数据量 int N = 100000;//十万 //int N = 1000000;//百万 //int N = 10000000;//千万 //int N = 100000000;//一亿 std::vector<int> v; //三大容器 std::list<int> l; std::deque<int>d; for (int i = N; i > 0; i--) //插入相同的数据，数据顺序也相同 { int e = rand(); v.push_back(e); l.push_back(e); d.push_back(e); }; clock_t begin1 = clock(); //时间函数 sort(v.begin(), v.end()); clock_t end1 = clock(); clock_t begin2 = clock(); l.sort(); clock_t end2 = clock(); clock_t begin3 = clock(); sort(d.begin(), d.end()); clock_t end3 = clock(); printf("vector的用时是%d毫秒\n", end1 - begin1); printf("list的用时是%d毫秒\n", end2 - begin2); printf("deque的用时是%d毫秒\n", end3 - begin3); } int main() { Test(); return 0; }
结果展示
即使排了一亿个数据，快排加vector容器也只用了4秒。list的底层是链表用了将近两分钟，效率低下。deque是一个类似于vector和list的结合体的容器，用了20秒。vector最引以为豪的优势——排序的效率高。原因在于vector的底层是连续的空间，支持随机访问，只需O(1)复杂度便可访问任意位置的数据。
在空间足够的情况下，尾部插入，尾部删除的效率为O(1)。
缺点：头部插入，头部删除，随机位置插入，随机位置删除，效率为O(N)。原因很简单：这些操作都需要挪动数据。如果数据量大，并且要频繁的头插头删，这便是堪比一个O(N^2)的算法。在标准库的接口中，并没有直接给头插，头删的接口。
接口介绍
begin
获取第一个数据位置的迭代器或const迭代器 |
end
| 获取最后一个有效数据的下一个位置的迭代器或const迭代器 |
rbegin
| 获取最后一个有效数据的迭代器或const迭代器 |
rend
| 获取第一个有效数据的前一个位置的迭代器 |
resize
| 改变vector容器有效数据的个数，改变为n个数据。如果n小于有效空间，删数据。n大于有效空间，扩容，并把多余的有效数据初始化为val |
reseve
| 改变容器的有效空间。n小于有效空间时，不做处理。n大于有效空间时，把空间开至n或更大。 |
insert
| 在迭代器position之前插入val |
| 在迭代器position之前插入n个val |
| 在迭代器position之前插入迭代器区间first到last的元素 |
erase
| 删除迭代器position位置的元素，或删除迭代器区间first到last的元素 |
其他一些接口
size |
获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
push_back |
尾插 |
| pop_back | 尾删 |
operator[] |
像数组一样访问 |
模拟实现
框架
namespace bit { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; }
获取迭代器
iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
深浅拷贝
过vector容器存的是自定义类型，它们的数据可能会指向某一块空间。当我们想要新的vector容器拷贝旧的vector容器数据时，新的vector容器是否要额外开空间储存自定义类型指向的空间的数据，便涉及深浅拷贝问题。
如下示意图
上文已经提到扩容时是浅拷贝，当 vector 需要扩容时，它会分配一个新的更大的内存块，然后将原来的元素拷贝到新的内存中，并释放原来的内存。这确保了在扩容时，原有元素的地址不会改变，从而避免了深拷贝的开销。
而在拷贝构造函数和赋值运算符中，vector 会执行深拷贝，即它会复制其中的每个元素，而不是简单地复制指向内存的指针。这样，每个vector 对象都有自己独立的内存存储其元素，互不影响，也避免了浅拷贝可能带来的问题。
有了上述了解，模拟实现一下赋值重载
赋值重载
现在写法
void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; }
reseve
void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * sz); for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n; } }
resize
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; } } }
拷贝构造
vector(const vector<T>& v) { _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T)*v.size()); for (size_t i = 0; i < v.size(); i++) { _start[i] = v._start[i]; //赋值重载 } _finish = _start + v.size(); _endofstorage = _start + v.capacity(); }
构造
vector(size_t n, const T& val = T()) { resize(n, val); }
析构
~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } }
insert
iterator insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish); if (_finish == _endofstorage) { size_t len = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); // 解决pos迭代器失效问题 pos = _start + len; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; }
erase
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; ++it; } --_finish; return pos; }
其他
void push_back(const T& x) { insert(end(), x); } void pop_back() { erase(--end()); } size_t capacity() const { return _endofstorage - _start; } size_t size() const { return _finish - _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]; }
本篇内容就到这里啦
