C++ Primer 學習筆記 47：STL 剖析（二）—— vector 源碼與記憶體配置器 Allocator

一、vector 初始化流程追蹤

vector v;  // 呼叫鏈：
// 1. vector() -> _Mybase()
// 2. allocator() -> _Vector_alloc() -> _Vector_val()
// 3. _Myfirst = _Mylast = _Myend = nullptr (指標初始化為 0)

二、vector 繼承體系

// VC2008 實作
template>
class vector : public _Vector_val<_Ty, _Ax> { ... };

template
class _Vector_val : public _CONTAINER_BASE_AUX_ALLOC<_Alloc> {
    _Alty _Alval;  // allocator 實例，用於元素記憶體管理
    pointer _Myfirst, _Mylast, _Myend;  // 首、尾、容量末尾指標
};

_Alty 經由 allocator::rebind 取得，對應元素型別的配置器。

三、動態擴容機制

capacity 增長策略

size_type _Grow_to(size_type _Count) const {
    size_type _Capacity = capacity();
    _Capacity = max_size() - _Capacity / 2 < _Capacity ? 0 : _Capacity + _Capacity / 2; // 1.5 倍
    if (_Capacity < _Count) _Capacity = _Count;
    return _Capacity;
}

實測 push_back 容量變化：0 → 1 → 2 → 3 → 4 → 6 → 9 → 13 → 19 ...（每次 +50%）。

三指標關係

• _Myfirst：元素起始位置。
• _Mylast：當前元素末尾（size 邊界）。
• _Myend：配置空間末尾（capacity 邊界）。
• size() = _Mylast - _Myfirst，capacity() = _Myend - _Myfirst。

預留空間減少重新配置與拷貝開銷，提升插入效率。

四、記憶體配置器 Allocator

標準介面

template
class allocator {
public:
    T* allocate(size_t n);           // 呼叫 ::operator new
    void deallocate(T* p, size_t n); // 呼叫 ::operator delete
    void construct(T* p, const T& val); // placement new
    void destroy(T* p);              // 呼叫析構函數
};

list vs vector 配置器差異

• vector：_Alval 配置元素陣列（連續）。
• list：_Alnod 配置節點（含前後指標 + 值），_Alptr 配置節點指標，_Alval 配置節點內的值。

五、總結

1. vector 以三指標管理動態陣列，1.5 倍擴容平衡時間/空間。
2. Allocator 封裝原始記憶體操作，支援自訂記憶體策略。
3. 兩級配置器（>128B malloc / ≤128B 記憶池）兼顧大小物件效率並減少碎片。