简单理解，就是vector是利用上述三个指针来表示的，基本示意图如下： 两个关键大小： 大小：size=_Mylast - _Myfirst； 容量：capacity=_Myend - _Myfirst； 分别对应于resize()、reserve()两个函数。 size表示vector中已有元素的个数，容量表示vector最多可存储的元素的个数；为了降低二次分配时的成本，vector实际配置的大小可能比客户需求的更大一些，以备将来扩充，这就是容量的概念。即capacity>=size，当等于时，容器此时已满，若再要加入新的元素时，就要重新进行内存分配，整个vector的数据都要移动到新内存。二次分配成本较高，在实际操作时，应尽量预留一定空间，避免二次分配。
1、构造 vector的构造函数主要有以下几种：
vector() : _Mybase() { // construct empty vector _Buy(0); } explicit vector(size_type _Count) : _Mybase() { // construct from _Count * _Ty() _Construct_n(_Count, _Ty()); } vector(size_type _Count, const _Ty& _Val) : _Mybase() { // construct from _Count * _Val _Construct_n(_Count, _Val); } vector(const _Myt& _Right) : _Mybase(_Right._Alval) { // construct by copying _Right if (_Buy(_Right.size())) _Mylast = _Ucopy(_Right.begin(), _Right.end(), _Myfirst); } 1234567891011121314151617vector优异性能的秘诀之一，就是配置比其所容纳的元素所需更多的内存，一般在使用vector之前，就先预留足够空间，以避免二次分配，这样可以使vector的性能达到最佳。因此元素个数_Count是个远比元素值 _Val重要的参数，因此当构造一个vector时，首要参数一定是元素个数。 由上各构造函数可知，基本上所有构造函数都是基于_Construct _n() 的
bool _Buy(size_type _Capacity) { // allocate array with _Capacity elements _Myfirst = 0, _Mylast = 0, _Myend = 0; if (_Capacity == 0) //_Count为0时，直接返回 return (false); else { // nonempty array, allocate storage _Myfirst = this->_Alval.allocate(_Capacity); //分配内存，并更新成员变量 _Mylast = _Myfirst; _Myend = _Myfirst + _Capacity; } return (true); } void _Construct_n(size_type _Count, const _Ty& _Val) { // 构造含有_Count个值为_Val的元素的容器 if (_Buy(_Count)) _Mylast = _Ufill(_Myfirst, _Count, _Val); } 12345678910111213141516171819这样就完成了vector容器的构造了。
2、析构 vector的析构函数很简单，就是先销毁所有已存在的元素，然后释放所有内存
void _Tidy() { // free all storage if (_Myfirst != 0) { // something to free, destroy and deallocate it _Destroy(_Myfirst, _Mylast); this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst); } _Myfirst = 0, _Mylast = 0, _Myend = 0; } 123456789vector的插入和删除元素是通过push_ back () 、 pop_back()两个接口来实现的，他们的内部实现也非常简单
void push_back(const _Ty& _Val) { // insert element at end if (size() < capacity()) _Mylast = _Ufill(_Mylast, 1, _Val); else insert(end(), _Val); //空间不足时，就会触发内存的二次分配 } void pop_back() { // erase element at end if (!empty()) { // erase last element _Destroy(_Mylast - 1, _Mylast); --_Mylast; } } 123456789101112131415161、reserve()操作
之前提到过reserve（Count） 函数主要是预留Count大小的空间，对应的是容器的容量，目的是保证（_Myend - _Myfirst）>=Count。只有当空间不足时，才会操作，即重新分配一块内存，将原有元素拷贝到新内存，并销毁原有内存
void reserve(size_type _Count) { // determine new minimum length of allocated storage if (capacity() < _Count) { // not enough room, reallocate pointer _Ptr = this->_Alval.allocate(_Count); _Umove(begin(), end(), _Ptr); size_type _Size = size(); if (_Myfirst != 0) { // destroy and deallocate old array _Destroy(_Myfirst, _Mylast); this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst); } _Myend = _Ptr + _Count; _Mylast = _Ptr + _Size; _Myfirst = _Ptr; } } 12345678910111213141516172、resize()操作 resize（Count） 函数主要是用于改变size的，也就是改变vector的大小，最终改变的是（_Mylast - _Myfirst）的值，当size < Count时,就插入元素，当size >Count时，就擦除元素。
void resize(size_type _Newsize, _Ty _Val) { // determine new length, padding with _Val elements as needed if (size() < _Newsize) _Insert_n(end(), _Newsize - size(), _Val); else if (_Newsize < size()) erase(begin() + _Newsize, end()); } 12345673、_Insert_n()操作
resize()操作和insert()操作都会利用到_Insert_n()这个函数，这个函数非常重要，也比其他函数稍微复杂一点 虽然_Insert_n(_where, _Count, _Val ) 函数比较长，但是操作都非常简单，主要可以分为以下几种情况：
1、_Count == 0，不需要插入，直接返回
2、max_size() - size() < _Count，超过系统设置的最大容量，会溢出，造成Xlen（）异常
3、_Capacity < size() + _Count，vector的容量不足以插入Count个元素，需要进行二次分配，扩大vector的容量。 在VS下，vector容量会扩大50%，即 _Capacity = _Capacity + _Capacity / 2; 若仍不足，则 _Capacity = size() + _Count; else if (_Capacity < size() + _Count) { // not enough room, reallocate _Capacity = max_size() - _Capacity / 2 < _Capacity ? 0 : _Capacity + _Capacity / 2; // try to grow by 50% if (_Capacity < size() + _Count) _Capacity = size() + _Count; pointer _Newvec = this->_Alval.allocate(_Capacity); pointer _Ptr = _Newvec; _Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),_Newvec); // copy prefix _Ptr = _Ufill(_Ptr, _Count, _Val); // add new stuff _Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr); // copy suffix //内存释放与变量更新 } 12345678910111213这种情况下，数据从原始容器移动到新分配内存时是从前到后移动的
4、空间足够，且被插入元素的位置比较靠近_Mylast,即已有元素的尾部
这种情况下不需要再次进行内存分配，且数据是从后往前操作的。首先是将where~last向后移动，为待插入数据预留Count大小的空间，然后从_Mylast处开始填充，然后将从where处开始填充剩余元素
else if ((size_type)(_Mylast - _VEC_ITER_BASE(_Where)) < _Count) { // new stuff spills off end _Umove(_VEC_ITER_BASE(_Where), _Mylast, _VEC_ITER_BASE(_Where) + _Count); // copy suffix _Ufill(_Mylast, _Count - (_Mylast - _VEC_ITER_BASE(_Where)), _Val); // insert new stuff off end _Mylast += _Count; std::fill(_VEC_ITER_BASE(_Where), _Mylast - _Count, _Val); // insert up to old end } 12345678910 5、空间足够，但插入的位置比较靠前 { // new stuff can all be assigned _Ty _Tmp = _Val; // in case _Val is in sequence pointer _Oldend = _Mylast; _Mylast = _Umove(_Oldend - _Count, _Oldend, _Mylast); // copy suffix _STDEXT _Unchecked_move_backward(_VEC_ITER_BASE(_Where), _Oldend - _Count, _Oldend); // copy hole std::fill(_VEC_ITER_BASE(_Where), _VEC_ITER_BASE(_Where) + _Count, _Tmp); // insert into hole } 12345678910114、erase()操作
iterator erase(const_iterator _First_arg, const_iterator _Last_arg) { // erase [_First, _Last) iterator _First = _Make_iter(_First_arg); iterator _Last = _Make_iter(_Last_arg); if (_First != _Last) { // worth doing, copy down over hole pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast, _VEC_ITER_BASE(_First)); _Destroy(_Ptr, _Mylast); _Mylast = _Ptr; } return (_First); } 12345678910111213141516主要操作就是将后半部分的有效元素向前拷贝，并将后面空间的无效元素析构，并更新_Mylast变量
5、assign()操作
assign()操作最终都会调用到下面的函数，主要操作是首先擦除容器中已有的全部元素，在从头开始插入Count个Val元素
void _Assign_n(size_type _Count, const _Ty& _Val) { // assign _Count * _Val _Ty _Tmp = _Val; // in case _Val is in sequence erase(begin(), end()); insert(begin(), _Count, _Tmp); } 123456五、基本使用 在经过上述对vector内部实现的分析后，再来理解相应接口就变得简单得多。 vector对外接口主要可以分为：
构造、析构： ector<Elem> c vector <Elem> c1(c2) vector <Elem> c(n) vector <Elem> c(n, elem) vector <Elem> c(beg,end) c.~ vector <Elem>() 123456 插入、删除、赋值 c.push_back(elem) c.pop_back() c.insert(pos,elem) c.insert(pos,n,elem) c.insert(pos,beg,end) c.erase(pos) c.erase(beg,end) c.clear() c.assign(beg,end) c.assign(n,elem) 12345678910 大小相关 c.capacity() c.max_size() c.resize(num) c.reserve() c.size() 12345 获取迭代器 c.begin() c.end() c.rbegin() c.rend() 1234 获取数据 operator[] c.at(idx) c.front() c.back() 四：常用方法 v1.push_back() //在数组的最后添加一个数据 v1.pop_back() //去掉数组的最后一个数据 v1.front() //返回第一个元素(栈顶元素) v1.begin() //得到数组头的指针，用迭代器接受 v1.end() //得到数组的最后一个单元+1的指针，用迭代器接受 v1.clear() // 移除容器中所有数据 v1.empty() //判断容器是否为空 v1.erase(pos) //删除pos位置的数据 v1.erase(beg,end)// 删除[beg,end)区间的数据 v1.size() //回容器中实际数据的个数 v1.insert(pos,data) //在pos处插入数据 五：常见的坑 从迭代器中取值切记需要判断是否为空 例如： 复制代码 1 vector<int> vtTest; 2 vtTest.clear(); 3 if (vtTest.empty()){ 4 return 0; 5 } 6 7 int *pTest = &vtTest[0]; 复制代码 如果没有忘了判断则会出现这样的异常_DEBUG_ERROR("vector subscript out of range"); 其实这条异常是Visual C++专有，在g++当中并不会出现，所取得的数值是0。可问题是你怎么区分里面所存的数据本身是0还是vector为空呢？ 带有容器的结构体不要使用memset清0 例如以下代码： 复制代码 1 struct _Test{ 2 int i; 3 vector<int> vtTest; 4 }; 5 6 _Test test; 7 memset(&test,0,sizeof(test)); 8 test.vtTest.push_back(0); 9 test.vtTest.push_back(0); 10 test.vtTest.push_back(0); 复制代码 其实这部分代码完全可以正常运行，但是如果加上以下代码就一样了 1 vector<int>::iterator it = test.vtTest.begin(); 2 it++; 问题就出在it++这条语句之上，此时会抛出vector iterator not incrementable 因为在自加的操作中，有这么一条判断 复制代码 1 if (this->_Getcont() == 0 2 || this->_Ptr == 0 3 || ((_Myvec *)this->_Getcont())->_Mylast <= this->_Ptr) 4 { // report error 5 _DEBUG_ERROR("vector iterator not incrementable"); 6 _SCL_SECURE_OUT_OF_RANGE; 7 } 复制代码 在this->_Getcont()函数内部，其实现是这样的; return (_Myproxy == 0 ? 0 : _Myproxy->_Mycont); 一旦调用上面的memset(&test,0,sizeof(test));之后，vector的_Myproxy数据结构也被清0了，此时_Getcont()函数的返回值就是0，那么程序就会执行到_DEBUG_ERROR("vector iterator not incrementable");经过分析发现，_Myproxy变量是vector用来寻找相邻的数值，而我们的清0操作导致这个链条断裂了，破坏了vector的数据结构从而导致异常。但是g++编译器并没有以上问题，因为VS改写了STL代码。 其实memset清0操作对于结构体或者类都必须慎重，因为很容易破坏自身的数据结构，最典型的就是带有虚函数的类，一旦清0连虚表都给破坏掉了。 vector内存控制 vector每次调用push_back的时候，如果之前内存够用就直接插入，如果不够用了就重新申请一块更大的内存(g++是在原基础上增加一倍长度，VS是增加百分之五十)，然后将数据拷贝到新内存当中，释放原内存，再插入新数据。 那么有两个问题，第一，如果能预测到数据量是固定数字，一定要首先预备一块内存，然后插入数据，这样第一避免多次重复申请释放，拷贝等耗资源和时间的无用操作，也可以避免多出一块并不会使用的内存。 其次如果从vector中删除元素，由于vector内存只增不减，当你申请一万个元素空间，删除了9999个，但是其占用仍然是10000个元素空间，如果条件允许，其实可以考虑增加策略来避免内存浪费，因为这些内存只有在析构的时候才会彻底释放掉。如果是指针则必须要手动析构，先遍历逐一delete，然后clear。 由于vector是申请的一块内存，所以如果要从首部删除元素会导致后面的所有元素向前移动一个单位，如果一直这么操作其占用可想而知。。。