C++內置了數組的類型，在使用數組的時候，必須指定數組的長度，一旦配置了就不能改變了，通常我們的做法是：盡量配置一個大的空間，以免不夠用，這樣做的缺點是比較浪費空間，預估空間不當會引起很多不便。

STL實現了一個Vector容器，該容器就是來改善數組的缺點。vector是一個動態空間，隨著元素的加入，它的內部機制會自行擴充以容納新元素。因此，vector的運用對於內存的合理利用與運用的靈活性有很大的幫助，再也不必因為害怕空間不足而一開始就配置一個大容量數組了，vector是用多少就分配多少。

要想實現動態分配數組，Vector內部就需要對空間控制做到有效率的掌控，這些機制要如何運作才能高效地實現動態分配呢？本篇博客就從源代碼的角度帶你領略一下Vector容器內部的構造藝術。

Vector概述

大家知道，初始化一個數組的時候，需要給數組分配一塊內存，數組中的數據都是按序存放的。vector也是如此，再初始化的時候給vector容器分配一塊內存，用來存放容器中的數據，一旦分配的內存不足以存放新加入的數據時，就需要擴充空間。STLVector的做法是：重新開辟一段新的空間，將原空間的數據遷移過去，然後新加入的數據存放在新空間之後並釋放掉原有空間。

在這個過程中，配置新空間->數據移動->釋放舊空間會帶來一定的時間成本，所以必須盡可能高效的實現，STL的Vector設計中對這一部分做了相當大的優化，使得時間成本盡可能的小。下面就一起去看看這些優秀的設計吧↓。

Vector的數據結構

我們從最簡單的開始，Vector的數據結構相當簡單，由於需要判斷內存是否夠用，所以要用到三個指針，分別指向頭，目前使用空間的尾，目前可用空間的尾。其源代碼如下：

template //alloc是STL的空間配置器
class vector
{
    // 這裡提供STL標准的allocator接口
  typedef simple_alloc data_allocator;

  iterator start;               // 內存空間起始點
  iterator finish;              // 當前使用的內存空間結束點
  iterator end_of_storage;      // 實際分配內存空間的結束點
}

每當初始化一個vector的時候，先分配一段內存，稱為目前可用空間，大小為end_of_storage - start + 1，當往vector裡面加入數據的時候，finish就往後移，代表目前已使用的空間，這樣做的好處是，不用頻繁的擴充空間和轉移數據，使得時間成本下降。

在上述代碼中，我們看到vector采用了STL標准的空間配置其接口

vector提供了如下函數來支持獲取其數據結構中的相關參數。

//獲取指向vector首元素的迭代器
iterator begin() { return start; }

//獲取指向vector尾元素的迭代器
iterator end() { return finish; }

// 返回當前對象個數，即已使用空間的大小
size_type size() const { return size_type(end() - begin()); }

// 返回重新分配內存前最多能存儲的對象個數，即目前可用空間的大小
size_type capacity() const { return size_type(end_of_storage - begin()); }

Vector的迭代器

既然是STL的容器，必須要滿足迭代器的相關要求
。

vector維護的是一段連續的內存空間，所以不論容器中元素的型別為何，普通指針都可以作為vector的迭代器而滿足所有必要的條件。vector支持隨機存取，所以vector提供的是Random Access Iterator。

下面來看看vector關於迭代器的源碼：

template 
class vector
{
public:
    // vector內部是連續內存空間，所以迭代器采用原生指針即可
  typedef value_type* iterator;                                 

  //以下為滿足Traits功能定義的內嵌型別
  typedef T value_type;
  typedef value_type* pointer;                  
  typedef const value_type* const_pointer;
  typedef const value_type* const_iterator;
  typedef value_type& reference;                
  typedef const value_type& const_reference;
  typedef ptrdiff_t difference_type;  

  typedef size_t size_type;         
}

vector的構造函數

默認構造函數

在使用vector的時候，我們通常會有如下定義：

#include 

vector vec;

在上述定義中，調用了vector的默認構造函數，其默認不分配內存空間，如下：

// vector的默認構造函數默認不分配內存空間
vector() : start(0), finish(0), end_of_storage(0) {}

帶參構造函數

通常，vector的初始化可以指定元素個數和初始化類型。如下：

vector vec(10,1); // 將vec初始化為10個1

vector提供下面的構造函數以支持上述初始化操作：

 <喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwcmUgY2xhc3M9"brush:java;"> // 構造函數，允許指定vector的元素個數和初值 vector(size_type n, const T& value) { fill_initialize(n, value); } vector(int n, const T& value) { fill_initialize(n, value); } vector(long n, const T& value) { fill_initialize(n, value); } // 需要對象提供默認構造函數 explicit vector(size_type n) { fill_initialize(n, T()); } /** * 填充並予以初始化 */ void fill_initialize(size_type n, const T& value) { start = allocate_and_fill(n, value); finish = start + n; // 設置當前使用內存空間的結束點 //這裡不過多的分配內存 end_of_storage = finish; } /** * 配置一塊大小為n的內存空間，並予以填充 */ iterator allocate_and_fill(size_type n, const T& x) { // 調用STL的空間配置器配置一塊大小為n的內存空間 iterator result = data_allocator::allocate(n); // 調用底層函數uninitialized_fill_n予以填充 uninitialized_fill_n(result, n, x); return result; }

這裡面調用了uninitialized_fill_n函數，這個函數是STL的內存基本處理函數，存放在stl_uninitialized.h中，下面來看看它的源碼：

// 如果copy construction和operator =等效, 並且destructor is trivial
// 那麼就可以使用本函數
template 
inline ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T& x, __true_type)
{
  return fill_n(first, n, x);
}
// 不是POD類型使用以下函數
template 
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T& x, __false_type)
{
  ForwardIterator cur = first;
  for ( ; n > 0; --n, ++cur)
    construct(&*cur, x);
  return cur;
}
// 利用type_traits來判斷是否是POD類型
template 
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n,
    const T& x, T1*)
{
  typedef typename __type_traits::is_POD_type is_POD;
  return __uninitialized_fill_n_aux(first, n, x, is_POD());

}
// 利用Iterator_traits來萃取出其值類型
template 
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,
    const T& x)
{
  return __uninitialized_fill_n(first, n, x, value_type(first));
}

vector的元素操作函數

push_back()

push_back()函數將新元素插入於vector的尾部，該函數再完成這一操作的時候，先檢查是否還有備用空間，如果有直接再備用空間上構造函數；如果沒有就擴充空間，通過重新配置一塊大空間，移動數據，釋放原空間的操作來完成push_back操作。其源代碼如下：

////////////////////////////////////////////////////////////////////////////////
// 向容器尾追加一個元素, 可能導致內存重新分配
////////////////////////////////////////////////////////////////////////////////
//                          push_back(const T& x)
//                                   |
//                                   |---------------- 容量已滿?
//                                   |
//               ----------------------------
//           No  |                          |  Yes
//               |                          |
//               ↓                          ↓
//      construct(finish, x);       insert_aux(end(), x);
//      ++finish;                           |
//                                          |------ 內存不足, 重新分配
//                                          |       大小為原來的2倍
//      new_finish = data_allocator::allocate(len);       
//      uninitialized_copy(start, position, new_start);   
//      construct(new_finish, x);                         
//      ++new_finish;
//      uninitialized_copy(position, finish, new_finish); 
////////////////////////////////////////////////////////////////////////////////
void push_back(const T& x)
{
  // 內存滿足條件則直接追加元素, 否則需要重新分配內存空間
  if (finish != end_of_storage) {
    construct(finish, x);
    ++finish;
  }
  else
    insert_aux(end(), x);
}

////////////////////////////////////////////////////////////////////////////////
// 提供插入操作
////////////////////////////////////////////////////////////////////////////////
//                 insert_aux(iterator position, const T& x)
//                                   |
//                                   |---------------- 容量是否足夠?
//                                   ↓
//              -----------------------------------------
//        Yes   |                                       | No
//              |                                       |
//              ↓                                       |
// 從opsition開始, 整體向後移動一個位置                     |
// construct(finish, *(finish - 1));                    |
// ++finish;                                            |
// T x_copy = x;                                        |
// copy_backward(position, finish - 2, finish - 1);     |
// *position = x_copy;                                  |
//                                                      ↓
//                            data_allocator::allocate(len);
//                            uninitialized_copy(start, position, new_start);
//                            construct(new_finish, x);
//                            ++new_finish;
//                            uninitialized_copy(position, finish, new_finish);
//                            destroy(begin(), end());
//                            deallocate();
////////////////////////////////////////////////////////////////////////////////
template 
void vector::insert_aux(iterator position, const T& x)
{
  if (finish != end_of_storage) {       // 還有剩余內存
    construct(finish, *(finish - 1));
    ++finish;
    T x_copy = x;
    copy_backward(position, finish - 2, finish - 1);
    *position = x_copy;
  }
  else {        
    // 內存不足, 需要重新分配
    const size_type old_size = size();
    //配置原則：如果原大小為0，就配置1個元素大小
    //        如果原大小不為0，就配置原大小的兩倍
    //              前半段用來放置原數據，後半段用來放置新數據
    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 {
        // 將原vector的內容拷貝到新vector
      new_finish = uninitialized_copy(start, position, new_start);
      // 構造新元素並賦值為x
      construct(new_finish, x);
      // 調整finish的位置
      ++new_finish;
      // 將安插點的原內容也拷貝過來
      new_finish = uninitialized_copy(position, finish, new_finish);
    }
        // 分配失敗則拋出異常
    catch (...) {
      destroy(new_start, new_finish);
      data_allocator::deallocate(new_start, len);
      throw;
    }
    // 析構原容器中的對象
    destroy(begin(), end());
    // 釋放原容器分配的內存
    deallocate();
    // 調整內存指針狀態
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

pop_back()函數

pop_back函數彈出當前尾端元素。其源代碼比較簡單，如下：

void pop_back()
{
    //調整finish
  --finish;
  //釋放調彈出的元素
  destroy(finish);
}

erase()函數

erase函數支持兩個版本：

iterator erase(iterator position)
{
  if (position + 1 != end())
    copy(position + 1, finish, position); //將[position+1,finish]移到[position,finish]
  --finish;
  destroy(finish);
  return position;//返回刪除點的迭代器
}

iterator erase(iterator first, iterator last)
{
  iterator i = copy(last, finish, first);//關於copy函數的源碼分析在以後的博文中會提到
  // 析構掉需要析構的元素
  destroy(i, finish);
  finish = finish - (last - first);
  return first;
}

這裡放上兩張《STL源碼剖析》中的圖，便於理解這一過程：

有上述erase函數，可以衍生出一個函數，用來清除迭代器中所有的元素

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

insert()函數

insert函數實現的功能是：從position開始，插入n個元素，元素的初值均為x。其源碼如下：

////////////////////////////////////////////////////////////////////////////////
// 在指定位置插入n個元素
////////////////////////////////////////////////////////////////////////////////
//             insert(iterator position, size_type n, const T& x)
//                                   |
//                                   |---------------- 插入元素個數是否為0?
//                                   ↓
//              -----------------------------------------
//        No    |                                       | Yes
//              |                                       |
//              |                                       ↓
//              |                                    return;
//              |----------- 內存是否足夠?
//              |
//      -------------------------------------------------
//  Yes |                                               | No
//      |                                               |
//      |------ (finish - position) > n?                |
//      |       分別調整指針                              |
//      ↓                                               |
//    ----------------------------                      |
// No |                          | Yes                  |
//    |                          |                      |
//    ↓                          ↓                      |
// 插入操作, 調整指針           插入操作, 調整指針           |
//                                                      ↓
//            data_allocator::allocate(len);
//            new_finish = uninitialized_copy(start, position, new_start);
//            new_finish = uninitialized_fill_n(new_finish, n, x);
//            new_finish = uninitialized_copy(position, finish, new_finish);
//            destroy(start, finish);
//            deallocate();
////////////////////////////////////////////////////////////////////////////////
template 
void vector::insert(iterator position, size_type n, const T& x)
{
  // 如果n為0則不進行任何操作
  if (n != 0) {
    if (size_type(end_of_storage - finish) >= n) {      // 剩下的內存夠分配
      T x_copy = x;
      const size_type elems_after = finish - position; // 計算插入點之後的現有元素個數
      iterator old_finish = finish;
      if (elems_after > n) {  // 插入點之後的現有元素個數大於新增元素個數，見下圖1
        // 先復制尾部n個元素到尾部
        uninitialized_copy(finish - n, finish, finish);
        finish += n; // 調整新的finish
        // 從後往前復制剩余的舊元素
        copy_backward(position, old_finish - n, old_finish);
        // 從position開始填充新元素
        fill(position, position + n, x_copy);
      }
      else {
        // 插入點之後的現有元素個數小於新增元素個數，見下圖2
        // 先在尾部填充n - elems_after個新增元素
        uninitialized_fill_n(finish, n - elems_after, x_copy);
        // 調整新的finish
        finish += n - elems_after;
        // 復制[position,old_finish]區間的數到新的finish之後
        uninitialized_copy(position, old_finish, finish);
        // 調整finish
        finish += elems_after;
        // 從position開始填充新增元素
        fill(position, old_finish, x_copy);
      }
    }
    else {      // 剩下的內存不夠分配, 需要重新分配
      const size_type old_size = size();
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        // 將舊的vector中插入點之前的元素復制到新空間，見下圖3
        new_finish = uninitialized_copy(start, position, new_start);
        // 將新增元素復制到新空間
        new_finish = uninitialized_fill_n(new_finish, n, x);
        // 將插入點之後的元素復制到新空間
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
      catch (...) {
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
      // 清除並釋放原有vector
      destroy(start, finish);
      deallocate();
      // 調整新的start和finish
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

上述操作可以使插入操作達到最高的效率。配合以下圖解更容易理解：

插入點之後的現有元素個數大於新增元素個數的情況

插入點之後的現有元素個數小於新增元素個數的情況

剩下的內存不夠分配，重新配置的情況

後記

STL的Vector容器到此就介紹完畢了。其中對改善效率作了不少優化，很多設計點都值得學習！若有疑惑可以在博文下方留言，我看到會及時幫大家解答！