STL漫遊之vector
std::vector 源碼分析
從源碼視角觀察 STL 設計，代碼實現為 libstdc++(GCC 4.8.5).
由於只關注 vector 的實現，並且 vector 實現幾乎全部在頭文件中，可以用一個這樣的方法里獲取比較清爽的源碼
// main.cpp
#include <vector>
int main() {
std::vector<int> v;
v.emplace_back(1);
}
g++ -E main.cpp -std=c++11 > vector.cpp
在 vscode 中打開 vector.cpp 使用正則 “#.*\n” 把所以編譯器相關的行刪除，這樣再進行格式化，就可以把預編譯指令全部過濾了，而且不依賴外部的實現，跳轉也沒有壓力
allocator
對於一個 allocator 需要實現的 trait，至少需要
- allocate 內存的分配
- deallocate 內存的回收
allocator 分配的最小粒度為對象，故要增加一個最大分配的數量
- max_size 最大分配數量
以上是實現一個分配器的最基礎功能。在此基礎上，擴展對象的構造和析構，對於需要使用分配器的地方比如 STL，容器自身就不用再關注對象的構造和析構的內存相關功能了。
- construct 對象構造，意味着需要使用模版實現，通用化
- destroy 對象銷毀
綜上，實現 allocator 具有的 alloc_traits 如下：
- allocate 分配
- deallocate 回收
- construct 對象構造，意味着需要使用模版實現，通用化
- destroy 對象銷毀
- max_size 最大分配數量
std::allocator
標準庫的分配器實現比較簡單，分配和回收使用 ::operator new/delete
pointer allocate(size_type __n, const void * = 0) {
if (__n > this->max_size())
std::__throw_bad_alloc();
return static_cast<_Tp *>(::operator new(__n * sizeof(_Tp)));
}
void deallocate(pointer __p, size_type) { ::operator delete(__p); }
對於最大分配數量，整個進程空間（虛擬）都可以進行分配
// sizeof(size_t) = 進程地址寬度
size_type max_size() const throw() { return size_t(-1) / sizeof(_Tp); }
對於對象的構造和析構，則使用布置構造和析構函數
void construct(pointer __p, const _Tp &__val) {
::new ((void *)__p) _Tp(__val);
}
void destroy(pointer __p) { __p->~_Tp(); }
std::vector
通用順序容器，支持自定義內存分配器；
基礎實現
libstdc++ 對 vector 的定義如下，裏面提供了：
template <typename _Tp, typename _Alloc = std::allocator<_Tp>>
class vector : protected _Vector_base<_Tp, _Alloc> {};
兩個模版參數：一個容器內的元素類型，一個分配器類型，並且分配器類型不是必須參數。
使用 protected 繼承 _Vector_base，不過這裡並沒有利用空基類優化(EBO), 更多的是做了類的隔離；
觀察 _Vector_base 的實現，包含了一個 impl：
template <typename _Tp, typename _Alloc> struct _Vector_base {
typedef
typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other
_Tp_alloc_type;
typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer pointer;
struct _Vector_impl : public _Tp_alloc_type {
pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;
}
public:
_Vector_impl _M_impl;
}
_Vector_base 提供了 vector 的對內存的操作，包括分配內存和釋放，_Vector_impl public 繼承 _Tp_alloc_type(默認為 std::allocator<_Tp1>)，從 C++ 的語義上說 _Vector_impl 也可以叫做一個分配器（事實也是）。
_Vector_impl
_Vector_impl 實現比較簡單，三個核心成員變量，作為 vector 的底層表達
- _M_start 元素空間起始地址，data() 返回的地址
- _M_finish 元空間結束地址, 和 size() 相關
- _M_end_of_storage 元素可用空間結束地址，和 capacity() 相關
struct _Vector_impl : public _Tp_alloc_type {
pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;
_Vector_impl()
: _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
_Vector_impl(_Tp_alloc_type const &__a)
: _Tp_alloc_type(__a), _M_start(0), _M_finish(0),
_M_end_of_storage(0) {}
void _M_swap_data(_Vector_impl &__x) {
std::swap(_M_start, __x._M_start);
std::swap(_M_finish, __x._M_finish);
std::swap(_M_end_of_storage, __x._M_end_of_storage);
}
};
_Vector_base
_Vector_impl 已經提供了底層存儲的表達，_Vector_base 則為對底層表達的初始化，及屏蔽內存的實現並對上層提供申請/釋放接口
// 只選了一個構造函數展示
_Vector_base(size_t __n) : _M_impl() { _M_create_storage(__n); }
void _M_create_storage(size_t __n) {
this->_M_impl._M_start = this->_M_allocate(__n);
this->_M_impl._M_finish = this->_M_impl._M_start;
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
}
// 釋放內存
~_Vector_base() {
_M_deallocate(this->_M_impl._M_start,
this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
}
pointer _M_allocate(size_t __n) {
return __n != 0 ? _M_impl.allocate(__n) : 0;
}
void _M_deallocate(pointer __p, size_t __n) {
if (__p)
_M_impl.deallocate(__p, __n);
}
構造函數
拿了三個構造函數的實現來看，後面兩者需要注意構造的時候就會有 size() 個複製的代價
L174 默認構造函數，除了基礎的初始化什麼都不做
L209 構造擁有 initializer_list init 內容的容器
L214 構造擁有範圍 [first, last) 內容的容器
174 explicit vector(const allocator_type &__a) : _Base(__a) {}
209 vector(initializer_list<value_type> __l,
210 const allocator_type &__a = allocator_type())
211 : _Base(__a) {
212 _M_range_initialize(__l.begin(), __l.end(), random_access_iterator_tag());
213 }
214 template <typename _InputIterator,
215 typename = std::_RequireInputIter<_InputIterator>>
216 vector(_InputIterator __first, _InputIterator __last,
217 const allocator_type &__a = allocator_type())
218 : _Base(__a) {
219 _M_initialize_dispatch(__first, __last, __false_type());
220 }
方法
搞明白 std::vector 的底層實現，後面直接看提供的方法了，最基本的增刪改查大小。
大小相關
size() 內部的元素個數，實現為
size_type size() const {
return size_type(this->_M_impl._M_finish - this->_M_impl._M_start);
}
capacity() 可用空間的大小，實現為
size_type capacity() const {
return size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
}
push_back
push_back 是使用最頻繁的方法，搞清楚它的實現，整個 vector 的變化策略都會比較清晰。
60 void push_back(const value_type &__x) {
61 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) {
62 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
63 ++this->_M_impl._M_finish;
64 } else
65 _M_emplace_back_aux(__x);
66 }
67
68 void push_back(value_type &&__x) { emplace_back(std::move(__x)); }
85 template <typename _Tp, typename _Alloc>
86 template <typename... _Args>
87 void vector<_Tp, _Alloc>::emplace_back(_Args && ...__args) {
88 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) {
89 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
90 std::forward<_Args>(__args)...);
91 ++this->_M_impl._M_finish;
92 } else
93 _M_emplace_back_aux(std::forward<_Args>(__args)...);
94 }
push_back() 底層有使用 emplace_back(c++11) 優化的情況:
size() < capacity() 的情況下，直接在最後一個元素後的位置進行複製/移動構造，底層地址偏移+1.
size() == capacity() 的情況下，需要先申請一塊新的內存後,再插入新的元素並且需要將之前的元素也移動至新的內存中，實現如下，忽略了異常處理和不需要的分支處理。
11 template <typename _Tp, typename _Alloc>
12 template <typename... _Args>
13 void vector<_Tp, _Alloc>::_M_emplace_back_aux(_Args && ...__args) {
14 const size_type __len =
15 _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
16 pointer __new_start(this->_M_allocate(__len));
17 pointer __new_finish(__new_start);
19 _Alloc_traits::construct(this->_M_impl, __new_start + size(),
20 std::forward<_Args>(__args)...);
21 __new_finish = 0;
22 __new_finish = std::__uninitialized_move_if_noexcept_a(
23 this->_M_impl._M_start, this->_M_impl._M_finish, __new_start,
24 _M_get_Tp_allocator());
25 ++__new_finish;
26 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
27 _M_get_Tp_allocator());
28 _M_deallocate(this->_M_impl._M_start,
29 this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
30 this->_M_impl._M_start = __new_start;
31 this->_M_impl._M_finish = __new_finish;
32 this->_M_impl._M_end_of_storage = __new_start + __len;
33 }
_M_check_len 校驗是否有足夠的空間進行分配，並且返回增長後的大小，實現如下
size_type _M_check_len(size_type __n, const char *__s) const {
if (max_size() - size() < __n)
__throw_length_error((__s));
const size_type __len = size() + std::max(size(), __n);
return (__len < size() || __len > max_size()) ? max_size() : __len;
}
可以得知，第一次 push_back 後，size() == capacity() == 1，第二次為2，後面依次 *2，最大為 size_t(-1)/sizeof(T).
L14 獲取需要分配的的空間大小
L16 申請一塊新的內存
L19 對新的元素進行構造
L22 對舊的元素，複製/移動構造至新的內存中
L26 對舊的元素進行析構
L28 對舊的空間進行釋放
L30-L32 更新底層實現的索引
所以可以看到 vector 的底層實現一定是順序表，可以在棧上（自己實現分配器）也可以在堆上（默認）。
關於擴容，增長因子為 2，並且有最大大小限制，還考慮了整數溢出的情況。
關於構造函數，每次插入都會有一個複製構造函數的調用
insert
插入元素到容器中的指定位置。
insert 和 push_back 實現差別不大，多了(size() – pos)次複製/移動構造函數
resize
改變容器中可存儲元素的個數
這裡只看默認初始化新元素值的實現
298 void resize(size_type __new_size) {
299 if (__new_size > size())
300 _M_default_append(__new_size - size());
301 else if (__new_size < size())
302 _M_erase_at_end(this->_M_impl._M_start + __new_size);
303 }
525 void _M_erase_at_end(pointer __pos) {
526 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
527 this->_M_impl._M_finish = __pos;
528 }
408 void vector<_Tp, _Alloc>::_M_default_append(size_type __n) {
409 if (__n != 0) {
410 if (size_type(this->_M_impl._M_end_of_storage -
411 this->_M_impl._M_finish) >= __n) {
412 std::__uninitialized_default_n_a(this->_M_impl._M_finish, __n,
413 _M_get_Tp_allocator());
414 this->_M_impl._M_finish += __n;
415 } else {
416 const size_type __len = _M_check_len(__n, "vector::_M_default_append");
417 const size_type __old_size = this->size();
418 pointer __new_start(this->_M_allocate(__len));
419 pointer __new_finish(__new_start);
420 try {
421 __new_finish = std::__uninitialized_move_if_noexcept_a(
422 this->_M_impl._M_start, this->_M_impl._M_finish, __new_start,
423 _M_get_Tp_allocator());
424 std::__uninitialized_default_n_a(__new_finish, __n,
425 _M_get_Tp_allocator());
426 __new_finish += __n;
427 } catch (...) {
428 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
429 _M_deallocate(__new_start, __len);
430 throw;
431 }
432 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
433 _M_get_Tp_allocator());
434 _M_deallocate(this->_M_impl._M_start,
435 this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
436 this->_M_impl._M_start = __new_start;
437 this->_M_impl._M_finish = __new_finish;
438 this->_M_impl._M_end_of_storage = __new_start + __len;
439 }
440 }
441 }
resize 中也存在三種情況
當需要重置大小等於目前容器的大小時，忽略
當重置大小小於目前容器大小時，處理簡單，釋放內存，修改 finish 的值
當重置大小大於目前容器大小時：
- 當前重置小於等於容器的容量，直接在尾部以默認構造函數額外的元素
- 當重置的大小大於容器的容器，和push_back一樣，需要先申請內存，再複製/移動元素，再重複1的步驟
L416-L412 為申請新的內存，並且複製/移動元素
L424 為在尾部以默認構造函數額外的元素
clear
清除容器內的元素，之後 size() = 0
實現較為簡單
521 void clear() noexcept { _M_erase_at_end(this->_M_impl._M_start); }
525 void _M_erase_at_end(pointer __pos) {
526 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
527 this->_M_impl._M_finish = __pos;
528 }
reserve
預留存儲空間, 增加 vector 的容量到(大於或)等於 new_cap 的值.
實現也比較簡單，new_cap 的值大於容器的容量時，進行重新分配，再複製/移動到新的內存中，最後更新底層數據結構
566 template <typename _Tp, typename _Alloc>
567 void vector<_Tp, _Alloc>::reserve(size_type __n) {
568 if (__n > this->max_size())
569 __throw_length_error(("vector::reserve"));
570 if (this->capacity() < __n) {
571 const size_type __old_size = size();
572 pointer __tmp = _M_allocate_and_copy(
573 __n, std::__make_move_if_noexcept_iterator(this->_M_impl._M_start),
574 std::__make_move_if_noexcept_iterator(this->_M_impl._M_finish));
575 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
576 _M_get_Tp_allocator());
577 _M_deallocate(this->_M_impl._M_start,
578 this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
579 this->_M_impl._M_start = __tmp;
580 this->_M_impl._M_finish = __tmp + __old_size;
581 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
582 }
583 }
shrink_to_fit
請求移除未使用的容量
void shrink_to_fit() { _M_shrink_to_fit(); }
template <typename _Tp, typename _Alloc>
bool vector<_Tp, _Alloc>::_M_shrink_to_fit() {
if (capacity() == size())
return false;
return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
}
template <typename _Tp> struct __shrink_to_fit_aux<_Tp, true> {
_Tp(__make_move_if_noexcept_iterator(__c.begin()),
__make_move_if_noexcept_iterator(__c.end()), __c.get_allocator())
.swap(__c);
return true;
};
模板太多看起來費勁，換一種表達
std::vector<int> v;
v.push_back(1); // size()=1 capacity()=1
v.push_back(1); // size()=2 capacity()=2
v.push_back(1); // size()=3 capacity()=4
std::vector<int>(v.begin(), v.end()).swap(v); // size()=3 capacity()=3
時間複雜度分析
| 複雜度 | 方法 | 說明 |
|---|---|---|
| \(O(1)\) | size() | 變量相減 |
| \(O(1)\) | capacity() | 變量相減 |
| \(O(1)\) | push_back() | 均攤最壞情況為3 |
| \(O(n)\) | insert() | 操作需要對size()-pos進行拷貝 |
| \(O(n)\) | clear() | size() 次析構 |
| \(O(n)\) | reserve() | 擴容需要size()次拷貝 |
| \(O(n)\) | shrink_to_fit() | 構造需要size()拷貝，swap()為常數 |
push_back 複雜度證明
以libstdc++為準備，vector的增長因子為2，分析對一個空的 vector 執行 n 個 push_back 的複雜度。
第 \(i\) 個操作的需要的複製構造次數的 \(c_i\)，分為兩種情況:
- size() < capacity(), \(c_i=1\)
- size() == capacity()，vector 進行擴張，\(c_i=i\)
得到每次的次數為：
\[c_i=\left\{
\begin{aligned}
i, & 若 i-1 恰為 2 的冪 \\
1, & 其他
\end{aligned}
\right.
\]
\begin{aligned}
i, & 若 i-1 恰為 2 的冪 \\
1, & 其他
\end{aligned}
\right.
\]
n 個 push_back 總的複製構造函數的次數為
\[\sum_{i=1}^nc_i \le n + \sum_{j=0}^{\lfloor lgn \rfloor}2^j \le n+2n = 3n
\]
\]
n個push_back的上界為 3n，單一的攤還次數為 3，所以複雜度為 \(O(1)\)
