STL版本比较多，第一个STL是在惠普实验室完成的，简称HP版本，后序版本STL都是基于HP版本给出来的，大同小异，本文主要基于SGI-STL版本进行探究，linux下采用就是SGI-STL，而且该版本的命名风格以及编码风格，可读性非常高。

vector底层实际是泛型的动态类型顺序表，因此其底层实际是一段连续的空间。在SGI-STL的vector中，实际在底层使用三个指针指向该段连续空间的，如下：

start指向空间的起始位置，finish指向最后一个元素的下一个位置，end_of_storage指向空间的末尾。

// SGI-STL部分源码
template <class T, class Alloc = alloc>
class vector {
public:
  typedef T value_type;           // vector中元素的类型
  typedef value_type* iterator;   // vector的迭代器，实际就是原生态的指针的别名
  // ...
protected:
  iterator start;                 // 指向底层空空间的起始位置
  iterator finish;                // 指向最后一个有效元素的下一个位置，没有元素时与start在同一位置
  iterator end_of_storage;        // 指向空间的末尾
  
  // ... 
  // 开辟n个元素的一段连续空间，并使用value来进行填充
  void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
  }
  
  // ...
  
public:
  // n向vector中填充n个位置value的元素
  vector(int n, const T& value) { fill_initialize(n, value); }
  // ...
 
 public:
  // vector的迭代器
  iterator begin(){ return start; }
  iterator end(){ return finish; }
  
  // ...
  
};

因为vector底层是连续空间，并且vector重载了[]下标运算符，用户可以向使用数组的方式访问vector中的每一个元素，即支持随机访问，但vector不适宜做任意位置的插入和删除操作，因为要进行大量元素的搬移，比如插入：

reference operator[](size_type n) 
{ 
    return *(begin() + n); 
}

const_reference operator[](size_type n) const 
{ 
    return *(begin() + n); 
}

vector不适宜做任意位置插入与删除操作，因为插入和删除时需要搬移大量元素：

在元素3的位置插入0时，需要将3 4 5 整体向后搬移一个位置，才可以插入数据0，最差情况下时间复杂度为O(N)；

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  // 检测是否需要扩容：如果finish和end_of_storage不在同一个位置，即还有空间
  // 则不需要库容
  if (finish != end_of_storage) {
    construct(finish, *(finish - 1));
    ++finish;
    T x_copy = x;
    
    // 将position之后的元素整体向后搬移一个位置
    copy_backward(position, finish - 2, finish - 1);
    *position = x_copy;
  }
  else {
   
    // finish与end_of_storage在同一个位置：需要进行扩容
    const size_type old_size = size();
    
    // 此处可以看到SGI-STL vector是按照2倍方式扩容的
    const size_type len = old_size != 0 ? 2 * old_size : 1;
    
    // 开辟新空间
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    __STL_TRY {
      // 将[start, position)区间中元素搬移到新空间，返回拷贝完成后新空间尾即原position相同位置
      new_finish = uninitialized_copy(start, position, new_start);
      
      // 在原position位置构造新对象
      construct(new_finish, x);
      ++new_finish;
      
      // 将原position位置元素搬移到新空间
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) {
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    destroy(begin(), end());
    deallocate();
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

为了能使算法操作容器中的元素，每个容器都提供了begin()和end()的迭代器，[begin, end)区间中包含了容器中的所有元素，vector也是如此。

iterator begin() { return start; }
iterator end() { return finish; }

size()和capacity()分别表示vector中的元素个数以及底层的空间大小。

size_type size() const { 
    return size_type(end() - begin()); // finish - start
}

size_type capacity() const { 
    return size_type(end_of_storage - begin()); // end_of_storage - start
}

在向vector中插入元素时，如果finish移动到与end_of_storage在同一个位置时，即size等于容量空间不足，则需要扩容，如下代码实现主要探测vector的扩容机制：

// SGI-STL扩容机制
void reserve(size_type n) {
    // 当n大于当前vector的容量时才会扩容，小于等于当前容量则忽略本次操作
    if (capacity() < n) {
      const size_type old_size = size();
        
      // 使用空间配置器开辟n个新空间，并将旧空间元素拷贝到新空间
      iterator tmp = allocate_and_copy(n, start, finish);
        
      // 释放旧空间
      // a. 先调用析构函数，将[start, finish)区间总所有的对象析构完整
      destroy(start, finish);
        
      // b. 将空间规划给空间配置器
      deallocate();
        
      // 3. 接收新空间并更新其成员
      start = tmp;
      finish = tmp + old_size;
      end_of_storage = start + n;
    }
  }

从上述源码中可以看到：

SGI-STL中vector是按照2倍方式扩容的，扩容需要经过以下步骤：

1. 开辟新空间
2. 拷贝元素
3. 释放旧空间
4. 使用新空间

扩容的实际为：在插入时，当finish与start在同一个位置，或者调用reserve操作，或者resize操作等都可能引起扩容。

// vector::capacity
#include <iostream>
#include <vector>
int main ()
{
    size_t sz;
	std::vector<int> foo;
	sz = foo.capacity();
	std::cout << "making foo grow:n";
	for (int i=0; i<100; ++i) 
    {
		foo.push_back(i);
		if (sz!=foo.capacity()) 
        {
			sz = foo.capacity();
			std::cout << "capacity changed: " << sz << 'n';
		}
	}
}

vs：运行结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
    
g++运行结果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128

从上述代码可以得出：

1. 在向vector中插入元素时，vector会自动进行扩容

2. vs下是几乎是按照1.5倍方式扩容的，linux下是按照2倍方式扩容的

3. 如果确定vector中大概要存储多少个元素时，尽量提前把空间申请好，否则边插入边扩容，会影响程序的效率。

   温馨提示：随着元素不断增多，边扩容边插入程序效率会非常低下，因此如果能够预估到vector中要存储多少个元素，可以一次性将空间给足，然后再插入。

   #include <iostream>
   #include <vector>
   int main ()
   {
       size_t sz;
   	std::vector<int> foo;
       foo.reserve(100);   // 先将vector底层空间扩增到100个，然后插入
   	sz = foo.capacity();
   	std::cout << "making foo grow:n";
   	for (int i=0; i<100; ++i) 
       {
   		foo.push_back(i);
   		if (sz!=foo.capacity()) 
           {
   			sz = foo.capacity();
   			std::cout << "capacity changed: " << sz << 'n';
   		}
   	}
   }
   

   此时再运行以上代码，几乎就看不到扩容的过程了。

本文主要对vector底层进行了探究，具体包含：

相同通过对本文的学习，同学们对于vector有更深的了解，在面试中也不会捉襟见肘，谢谢。