写在前面

vector是我们在STL中最常用的容器，我们对它的各种操作也都了然于胸。然而我们在使用vector的时候总会有一种很虚的感觉，由于我们不清楚接口内部是如何实现的。在我们眼里宛如一个黑箱，既危险又迷人。

为了打破这种顾虑，接下来我就带大家深入vector底层，彻底弄懂vector接口内部实现细节，打开这个黑箱。这样在使用vector的时候我们也就不会慌了，做到真正的了然于胸。

vector 底层原理概述

vector是动态空间，随着元素的添加，其内部机制会自行扩充空间来容纳新元素。

vector动态添加大小时，并不是在原空间之后持续新空间（由于根本无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，而后将内容拷贝过来，而后才开始在原内容之后构造新元素，并释放原空间，

重点源码了解

１．迭代器内部型别

下面我们来看看STL源码里面是如何来定义迭代器的吧。

template <class T, class Alloc = alloc>class vector {public:    // vector 的嵌套型别定义    typedef T value_type;    typedef value_type* iterator;    // 迭代器本身是一个模板类的对象    typedef value_type& reference;    ...};

如上面代码所示，迭代器iterator本身是一个类类型，运算符*被重载。迭代器iterator指向vector的内部元素，可以了解为iterator与vector的内部元素捆绑在一起，其行为相似指针，但是又不能把它当作指针。

灵魂拷问一：迭代器与指针有什么区别？

我们可以这样了解，迭代器本质上就是模板类产生的一个对象，而其运算符*和->都是经过运算符重载实现的。这个对象指向vector的内部元素（元素又是迭代器的对象），所以当迭代器指向的元素被删除或者者移动，迭代器与元素就断开链接，迭代器也就没有用了，也就是我们通常说的迭代器失效。迭代器的行为相似指针，但是又有所区别。

反观指针，指针与内存是联络在一起的。假如指针指向的内存地址存储的元素被删除或者者移动，指针并不会因而失效，它仍然指向了该地址。

根据上述定义，迭代器可以这样公告：

vector<int>::iterator ivite;vector<Shape>::iterator svite;

看完上面的源码，我们也就清楚为什么迭代器要这样公告了。

２．vector 的数据结构

vector使用两个迭代器start和finish来表示已使用空间的范围，并以迭代器end_of_storage指向分配空间的尾端。代码如下：

template <class T, class Alloc = alloc>class vector {...protected:    iterator start;          // 表示目前使用空间的头    iterator finish;         // 表示目前使用空间的尾，即最后一个元素的下一个元素    iterator end_of_storage; // 表示目前分配的整个空间的尾    ...};

利用以上三个迭代器，我们能够封装vector的各种成员函数。

template <class T, class Alloc = alloc>class vector {...public:  iterator begin() { return start; }  iterator end() { return finish; }  size_type size() const { return size_type(end() - begin()); }  bool empty() const { return begin() == end(); }  reference front() { return *begin(); }  reference back() { return *(end() - 1); }  reference operator[](size_type n) { return *(begin() + n); }// 运算符[]重载，能够使用迭代器来访问元素};

上面少量基础操作已经一目了然了，这里就不逐个述说了。这里只提两点，第一，从上面代码可以看出operator[]()对运算符[]进行了重载，这样能够使迭代器像数组索引一样遍历vector。

第二，迭代器finish指向的是vector最后一个元素的下一个元素，封装的end()函数也如此。这也就是我们常常说的vector的前闭后开特性。

灵魂拷问二：为什么容器要设计成前闭后开的特性？

这样做是为了在遍历容器元素时减少判断条件。由于STL的核心是泛型编程，使得设计的接口是通用的。因为只有部分容器支持>和<运算符重载，而!=则是一律容器都支持，所以遍历元素的时候优先使用!=重载运算符。

假如将end()指向容器最后一个元素的下一个，则遍历操作只要要写成：

vector<int> vec;auto it = vec.begin();while (it != vec.end()) {    ...     ++it;}

但是假如end()指向的是最后一个元素，上述代码会少遍历一个元素，这就需要在while循环里添加额外的判断条件，并且这个判断条件可能因容器的不同要进行修改，而上述代码在任何顺序容器都能这样调用，减少了很多多余工作。

３．vector 的元素操作

vector 的构造函数

vector的构造函数有多种形式，下面摘取源码中的部分代码：

// 构造函数，允许指定 vector 大小和初值vector() : start(0), finish(0), end_of_storage(0) {}vector(size_type n, const T& value) { fill_initialize(n, value); }explicit vector(size_type n) { fill_initialize(n, T()); }

分别对应如下初始化：

vector<int> vec;vector<int> vec(2,3);vector<int> vec(2);

push_back() 与 pop_back()

当我们以push_back()将新元素插入vector尾端时，该函数首先检查能否还有备用空间，假如有就直接在备用空间上构造元素，并调整迭代器finish。假如没有备用空间了，就扩充空间（重新配置、移动数据、释放原空间）。

void push_back(const T& x) {  if (finish != end_of_storage) { // 还有备用空间    construct(finish, x);    ++finish;  }  else                            // 已无备用空间    insert_aux(end(), x);         // 插入函数}

插入函数原型为：

void insert_aux(iterator position, const T& x);

这个函数比较长，具体思路：在有备用空间情况下，在备用空间起始处构造一个元素，迭代器finish自增一；在无备用空间情况下，重新配置两倍的原内存空间，将原vector的内容拷贝到新vector中，再释放掉原空间。

注：插入函数是将元素插入到对应位置，原价该位置以及后面的元素都向后移动一位。

删除vector尾部元素操作pop_back()更加简单。

void pop_back() {  --finish;  destroy(finish);}

直接将尾部迭代器finish向前移动一位，而后释放掉。因为尾部迭代器finish指向的是最后一个元素的下一位，所以减一后正好是原来的最后一个元素。

erase() 与 clear()

erase()表示删除vector的某一个元素或者者某一区间内的所有元素。

// 删除 vector 的某一个位置的元素iterator erase(iterator position) {  if (position + 1 != end())    copy(position + 1, finish, position);  --finish;  destroy(finish);  return position;}// 删除 vector 的某一个区间的元素iterator erase(iterator first, iterator last) {  iterator i = copy(last, finish, first);  destroy(i, finish);  finish = finish - (last - first);  return first;}

假如不对erase()函数谨慎使用，可能会出现迭代器失效的问题。

灵魂拷问三：在什么情况下使用erase()函数迭代器会失效？

通常我们写出这样的代码迭代器会失效。

for(auto it = vec.begin();it != vec.end();++it) {    if(/* 删除某元素的判断条件 */) {        vec.erase(it);    }}

由灵魂拷问一可知，删除元素后因为被删除元素后面的数据都会发生移动，所以后面的迭代器都会失效。故上述代码在删除了某个迭代器后，后面的++it遍历已经失去意义，不会得到正确的结果。

那应该如何更改呢？由前面删除vector的某一个位置的元素的源代码可知，erase()返回的是一个迭代器，这个迭代器实际上是被删除元素的下一个元素绑定的迭代器，这个迭代器是数据移动后新的有效的迭代器。也可以说是升级了迭代器。

正确的写法为：

for(auto it = vec.begin();it != vec.end();) {    if(/* 删除某元素的判断条件 */) {        it = vec.erase(it);  // 升级了迭代器    }    else {        ++it;    }}

clear()表示清空vector上的所有元素。

void clear() { erase(begin(), end()); }

最后

正如侯捷老师说的“源码之前，了无秘密”一样，在看了vector容器的实现源码后，我对其中的底层实现机制有了更深刻的了解。以前常常被迷雾笼罩倍感慌乱，而现在慢慢开始拨开云雾，看到了之前看不到的风景。