帶你深入理解STL之Vector容器

ykhust 9年前發布 | 47K 次閱讀 STL C/C++開發

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

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

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

Vector概述

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

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

Vector的數據結構

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

template<classT,classAlloc = alloc>//alloc是STL的空間配置器
classvector
{
// 這里提供STL標準的allocator接口
typedefsimple_alloc<value_type, Alloc> data_allocator;

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

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

在上述代碼中，我們看到vector采用了STL標準的空間配置其接口，關于空間配置器的知識在帶你深入理解STL之空間配置器(思維導圖+源碼) 一文中有講解，如有疑惑，可以跳轉復習一下再來！

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

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

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

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

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

Vector的迭代器

既然是STL的容器，必須要滿足迭代器的相關要求，如對迭代器有疑惑的，參考帶你深入理解STL之迭代器和Traits技法。

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

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

template<classT,classAlloc = alloc>
classvector
{
public:
// vector內部是連續內存空間，所以迭代器采用原生指針即可
typedefvalue_type* iterator;

//以下為滿足Traits功能定義的內嵌型別
typedefT value_type;
typedefvalue_type* pointer;
typedefconstvalue_type* const_pointer;
typedefconstvalue_type* const_iterator;
typedefvalue_type& reference;
typedefconstvalue_type& const_reference;
typedefptrdiff_tdifference_type;

typedefsize_tsize_type;
}

vector的構造函數

默認構造函數

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

#include<vector>

vector<int> vec;

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

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

帶參構造函數

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

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

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

// 構造函數，允許指定vector的元素個數和初值
vector(size_type n,constT& value) { fill_initialize(n, value); }
vector(intn,constT& value) { fill_initialize(n, value); }
vector(longn,constT& value) { fill_initialize(n, value); }

// 需要對象提供默認構造函數
explicitvector(size_type n){ fill_initialize(n, T()); }

/**
 * 填充并予以初始化
 */
voidfill_initialize(size_type n,constT& value)
{
 start = allocate_and_fill(n, value);
 finish = start + n; // 設置當前使用內存空間的結束點

//這里不過多的分配內存
 end_of_storage = finish;
}

/**
 * 配置一塊大小為n的內存空間，并予以填充
 */
iterator allocate_and_fill(size_type n,constT& x)
{
// 調用STL的空間配置器配置一塊大小為n的內存空間
 iterator result = data_allocator::allocate(n); 

// 調用底層函數uninitialized_fill_n予以填充
 uninitialized_fill_n(result, n, x);
returnresult;
}

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

// 如果copy construction和operator =等效, 并且destructor is trivial
// 那么就可以使用本函數
template<classForwardIterator,classSize,classT>
inlineForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
constT& x,__true_type)
{
returnfill_n(first, n, x);
}
// 不是POD類型使用以下函數
template<classForwardIterator,classSize,classT>
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
constT& x,__false_type)
{
 ForwardIterator cur = first;
for( ; n >0; --n, ++cur)
 construct(&*cur, x);
returncur;
}
// 利用type_traits來判斷是否是POD類型
template<classForwardIterator,classSize,classT,classT1>
inlineForwardIterator__uninitialized_fill_n(ForwardIterator first, Size n,
constT& x, T1*)
{
typedeftypename__type_traits<T1>::is_POD_type is_POD;
return__uninitialized_fill_n_aux(first, n, x, is_POD());

}
// 利用Iterator_traits來萃取出其值類型
template<classForwardIterator,classSize,classT>
inlineForwardIteratoruninitialized_fill_n(ForwardIterator first, Size n,
constT& 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); <stl_alloc.h>
// uninitialized_copy(start, position, new_start); <stl_uninitialized.h>
// construct(new_finish, x); <stl_construct.h>
// ++new_finish;
// uninitialized_copy(position, finish, new_finish); <stl_uninitialized.h>
////////////////////////////////////////////////////////////////////////////////
voidpush_back(constT& 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<classT,classAlloc>
voidvector<T, Alloc>::insert_aux(iterator position,constT& 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{
// 內存不足, 需要重新分配
constsize_type old_size = size();
//配置原則：如果原大小為0，就配置1個元素大小
// 如果原大小不為0，就配置原大小的兩倍
// 前半段用來放置原數據，后半段用來放置新數據
constsize_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函數彈出當前尾端元素。其源代碼比較簡單，如下：

voidpop_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);
returnposition;//返回刪除點的迭代器
}

清除某個區間上的所有函數

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

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

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

voidclear(){ 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<classT,classAlloc>
voidvector<T, Alloc>::insert(iterator position, size_type n,constT& x)
{
// 如果n為0則不進行任何操作
if(n !=0) {
if(size_type(end_of_storage - finish) >= n) {// 剩下的內存夠分配
 T x_copy = x;
constsize_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{// 剩下的內存不夠分配, 需要重新分配
constsize_type old_size = size();
constsize_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容器到此就介紹完畢了。其中對改善效率作了不少優化，很多設計點都值得學習！若有疑惑可以在博文下方留言，我看到會及時幫大家解答！

參考：

C++ STL源碼剖析
STL源碼剖析——迭代器
侯捷先生的《STL源碼剖析》華中科技大學出版社

來自：http://zcheng.ren/2016/08/24/STLVector/

Save

本文由用戶 ykhust 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1471952557903.html

STL C/C++開發