文章目錄

• • • 前言
    • vector的核心接口
    • vector push_back實現
    • • vector 的 Allocator
      • vector 的 push_back
    • 總結

前言

---

vector 是我們C++STL中經常使用的一個容器，提供容量可以動態增長，并且隨機訪問內部元素的數據存儲功能。

這個容器我們最常使用，所以也是最為熟悉的一種容器。通過它來看STL的源碼設計，以及STL六大組件之間的搭配使用，可以讓我們對C++這種語言，對優秀的編碼設計，對有趣的數據結構和算法都能有深刻的理解和認識。

STL六大組件關系如下：

其中容器主要是 提供數據存儲的功能。分配器用來給容器的數據存儲分配空間，算法通過迭代器可以訪問容器中的數據。仿函數提供類似于函數的功能，這里算法就是用仿函數來實現的。各個適配器給各個組件做一些功能上的補充。

今天主要對容器的vector的實現進行深入的分析。

本節涉及的源代碼是基于:gcc 2.95 版本的libstdc++ 標準庫進行分析的。不同版本的代碼實現方式可能有一些差異，但是核心思想應該是一樣的。
gcc-2.95 源碼下載

vector的核心接口

我們在使用vector的過程中從聲明到使用的基本接口如下：

vecotor<int,std::alloctor<int>> arr(10,0); 
arr.push_back(3);
arr.size();
arr.max_szie();
arr.back();
arr.pop_back();
arr.capacity();
arr.erase(3);
...

詳細的就不一一列舉了，這里我們主要關注的是push_back()插入的操作，因為只有元素的持續插入，vector的底層數據存儲結構才會跟著進行變化，這也是它的核心接口了。

vector push_back實現

首先用一張圖來表示vector的基本存儲情況以及擴容的過程（其中的字段是源碼部中的字段）

左側的存儲代表擴容之前的存儲結構，右側是擴容之后的存儲結構。
擴容的過程是兩倍的容量擴充，且不是在原來的基礎上進行增長的，而是重新分配一塊兩倍于原來大小的內存空間，將原來的存儲空間的元素一個一個拷貝到新的兩倍大小的存儲空間之中。

• _M_start 代表起始位置的指針
• _M_finish 代表已存儲的元素的末尾位置
• _M_end_of_storage 代表整個vector空間的結束位置
• size ,即 我們使用的arr.size() ,表示vector實際存儲的元素的個數
• capacity， 即我們使用的arr.capacity()，表示當前vector可以存儲的元素個數（包括已分配空間，但未存儲元素的空間區域）

具體實現的類圖關系如下：

從上面的類圖關系中我們能夠看到最終vector對象的大小sizeof(vector<Tp>())為24B（x86_64），三個指針類型的大小(_M_start, _M_finish,_M_end_of_storage)

接下來我們來看一下具體的成員函數實現

vector 的 Allocator

vector類 通過函數模版，制定了基本數據類型，以及實例化了分配器的類型

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
private:typedef _Vector_base<_Tp, _Alloc> _Base;
public:typedef _Tp value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type* iterator;typedef const value_type* const_iterator;typedef value_type& reference;typedef const value_type& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;...

這里我們再追蹤一下空間分配器 Allocator是如何參與到vector容器之中的。

可以很明顯得看到這里分配器使用的是stl默認的分配器 allocator，即

define __STL_DEFAULT_ALLOCATOR(T) allocator<T>

allocator的聲明如下,這里主要看一下stl分配器中的allocate和deallocate函數，他們如何進行空間分配

template <class _Tp>
class allocator {typedef alloc _Alloc;          // The underlying allocator.
public:typedef size_t     size_type;typedef ptrdiff_t  difference_type;typedef _Tp*       pointer;typedef const _Tp* const_pointer;typedef _Tp&       reference;typedef const _Tp& const_reference;typedef _Tp        value_type;......// __n is permitted to be 0.  The C++ standard says nothing about what// the return value is when __n == 0.// 傳入要分配的個數n,并調用_Alloc的allocate函數進行空間的分配// 分配的總大小是n *  sizeof(_Tp)_Tp* allocate(size_type __n, const void* = 0) {return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))): 0;}......

_Alloc的allocate最終會調用malloc_allc::allocate函數，再通過malloc分配空間。

static void* allocate(size_t __n)
{_Obj* __VOLATILE* __my_free_list;_Obj* __RESTRICT __result;//如果一次分配的空間大于128B，則會直調用malloc進行空間的申請if (__n > (size_t) _MAX_BYTES) {return(malloc_alloc::allocate(__n));}// 如果不足128B，從空閑鏈表中取出空間__my_free_list = _S_free_list + _S_freelist_index(__n);// Acquire the lock here with a constructor call.// This ensures that it is released in exit or during stack// unwinding.
#       ifndef _NOTHREADS/*REFERENCED*/_Lock __lock_instance;
#       endif__result = *__my_free_list;if (__result == 0) {void* __r = _S_refill(_S_round_up(__n));return __r;}*__my_free_list = __result -> _M_free_list_link;return (__result);
};static void* allocate(size_t __n)
{void* __result = malloc(__n);if (0 == __result) __result = _S_oom_malloc(__n);return __result;
}

同樣allocator的deallocate函數實現如下，最終也會調用到free進行空間的釋放

//allocator 的deallocate函數
void deallocate(pointer __p, size_type __n){ _Alloc::deallocate(__p, __n * sizeof(_Tp)); }//_Alloc的deallocate函數
static void deallocate(void* __p, size_t __n)
{_Obj* __q = (_Obj*)__p;_Obj* __VOLATILE* __my_free_list;if (__n > (size_t) _MAX_BYTES) {malloc_alloc::deallocate(__p, __n);return;}__my_free_list = _S_free_list + _S_freelist_index(__n);// acquire lock
#       ifndef _NOTHREADS/*REFERENCED*/_Lock __lock_instance;
#       endif /* _NOTHREADS */__q -> _M_free_list_link = *__my_free_list;*__my_free_list = __q;// lock is released here
}// malloc_alloc的deallocate函數
static void deallocate(void* __p, size_t /* __n */)
{free(__p);
}

到此我們就基本清楚了當前版本的vector容器是如何得到具體的存儲空間的。

接下來我們繼續回到vector的實現之中。

vector 的 push_back

vector的push_back 邏輯有兩種

1. 當vector的內部的finish指針并沒有達到end_of_storage指針，即沒有達到我們理解的容量的上限的時候，會構造一個_Tp的對象加入到finish指針區域，同時finish指針增加。
2. 當finish指針到達end_of_storage指針的位置的時候需要重新進行分配。
   分配的過程是 重新分配一塊原來存儲空間兩倍大小的空間，將原來的元素拷貝到新的存儲空間。

接下來看一下具體的過程,push_back過程如下

void push_back(const _Tp& __x) {//finish指針 沒有到達end的位置，表示還有空間可用if (_M_finish != _M_end_of_storage) {construct(_M_finish, __x);++_M_finish;}else//否則，開始重新分配_M_insert_aux(end(), __x);
}

調用了_M_insert_aux函數，在空間不足時進行重新分配。
實現過程如下。

這里我們能看到 函數開頭又重新寫了是否達到容量上限的判斷邏輯。

因為這個函數除了被push_back調用，還會被迭代器的insert調用，導致當前線程想要分配的時候空間已經擴容好了，所以還需要再增加一次空間是否足夠的判斷。

同時擴容的過程中調用了兩次拷貝的過程，也是因為insert的函數，在指定的位置插入元素，可能也會造成vector的擴容，所以插入的位置前后都需要拷貝到新的存儲空間之中。

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{if (_M_finish != _M_end_of_storage) {construct(_M_finish, *(_M_finish - 1));++_M_finish;_Tp __x_copy = __x;copy_backward(__position, _M_finish - 2, _M_finish - 1);*__position = __x_copy;}else {/* 獲取舊的容量 */const size_type __old_size = size();const size_type __len = __old_size != 0 ? 2 * __old_size : 1;/* 重新分配 */iterator __new_start = _M_allocate(__len);iterator __new_finish = __new_start;/*try...catch子句，進行異常捕獲，如果這個過程失敗了，會回滾已經分配好了的空間*/__STL_TRY {/* 將原來的vector內容拷貝到當前vector：*/__new_finish = uninitialized_copy(_M_start, __position, __new_start);construct(__new_finish, __x);  // 為新的元素設置初始值，添加到vector末尾++__new_finish; // 調整水位// 這里需要再次進行一次拷貝，是因為當前函數可能還會被insert(p,x)調用// insert表示在第p個位置插入x元素，這個操作可能也會造成數組的擴容// 所以需要將安插點之后的數據拷貝到當前位置__new_finish = uninitialized_copy(__position, _M_finish, __new_finish); }/*catch*/__STL_UNWIND((destroy(__new_start,__new_finish), _M_deallocate(__new_start,__len)));/*銷毀舊的存儲空間，并更換三個指針為新的地址空間的指針*/destroy(begin(), end());_M_deallocate(_M_start, _M_end_of_storage - _M_start);_M_start = __new_start;_M_finish = __new_finish;_M_end_of_storage = __new_start + __len;}
}

總結

通過 vector的擴容過程的實現，我們能看到vector的擴容會有一些隱患：

1. 當擴容產生，將舊的空間的元素拷貝到新的空間的元素會觸發 臨時對象的構造和 拷貝構造函數，此時如果元素體量較為龐大，那大量的新對象的構造和拷貝構造函數調用 會產生一點的性能開銷。
2. 新的空間和元素都拷貝過去之后，舊的空閑也需要釋放，此時又會有大量的析構調用來進行空間的釋放。

驗證代碼如下：

#include <iostream>
#include <vector>
#include <unistd.h>using namespace std;class Test {
private:int num;public:Test(int x):num(x){std::cout << "constructed\n";}/*拷貝構造函數*/Test(const Test &obj) {num = obj.num;std::cout << "copy constructed\n";}/*C++11 支持的 轉移構造函數*/Test (Test &&obj) {num = std::move(obj.num);std::cout << "moved constructed\n";}};int main() {vector<Test> arr;std::cout << "push_back : Test(1)\n";arr.push_back(1);return 0;
}

push_back : Test(1)
constructed
moved constructed

怎么解決呢？
這就是我們C++11在這一方面推出的性能方面的改進邏輯：

1. push_back 將拷貝構造函數變更為 轉移構造(std::move)函數，減少來空間釋放的開銷
2. 推出emplace_back函數，使用變長模版參數forward進行對象在的原地構造，只需要一次對象本身的構造即可。

emplace_back函數，詳細的實現可以參考empalce_back和push_back的差異

vector的emplace_back實現如下:

vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
{if (this->__end_ < this->__end_cap()){__RAII_IncreaseAnnotator __annotator(*this);__alloc_traits::construct(this->__alloc(),_VSTD::__to_raw_pointer(this->__end_),_VSTD::forward<_Args>(__args)...);__annotator.__done();++this->__end_;}else__emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
#if _LIBCPP_STD_VER > 14return this->back();
#endif
}

可以看到STL的開發者們 不斷得完善邏輯，改進性能。并且不斷得推出新的特性來供給我們這一些語言的使用者來使用，如果我們還用不好，那是真的愧對大佬們的付出了。

精進自己，追求極致，向大佬們致敬。

總結

以上是生活随笔為你收集整理的C++ STL: 容器vector源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。