STL Vector 容器深度剖析：動態陣列的記憶體管理藝術

Vector 核心設計理念

C++ 內建陣列長度固定，使用時常預分配大空間造成浪費，或容量不足導致問題。std::vector 實現動態空間：隨元素加入自動擴容，按需分配，極大提升記憶體利用率與靈活性。

資料結構：三個迭代器掌控全局

template 
class vector {
    typedef simple_alloc data_allocator;
    iterator start;            // 記憶體起始位置
    iterator finish;           // 已使用空間結束位置
    iterator end_of_storage;   // 實際分配空間結束位置
};

• capacity() = end_of_storage - start：總可用容量
• size() = finish - start：當前元素個數
• 預留備用空間（end_of_storage - finish）減少擴容頻率

迭代器設計

Vector 維護連續記憶體，原生指標即可作為隨機存取迭代器，滿足所有 STL 迭代器要求：

typedef T* iterator;
typedef const T* const_iterator;
// ... 其他嵌套型別定義

建構函數與記憶體初始化

預設建構

vector() : start(0), finish(0), end_of_storage(0) {} // 不分配記憶體

帶參數建構

vector(size_type n, const T& value) { fill_initialize(n, value); }
void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish; // 精確分配，不預留額外空間
}

核心輔助函式 uninitialized_fill_n 利用型別萃取（__type_traits）判斷 POD 型別：POD 型別直接 fill_n，非 POD 型別逐個呼叫 construct 建構物件。

核心操作函數深度解析

push_back()：兩倍擴容策略

void push_back(const T& x) {
    if (finish != end_of_storage) {
        construct(finish, x);
        ++finish;
    } else {
        insert_aux(end(), x); // 觸發擴容
    }
}

擴容邏輯：原容量為 0 則分配 1，否則分配 2 倍原容量。流程：分配新空間 → uninitialized_copy 遷移舊資料 → 建構新元素 → 遷移剩餘資料 → 銷毀舊資料 → 釋放舊空間 → 更新三指標。

insert()：高效插入的多種情況

根據「剩餘空間是否足夠」與「插入點後元素個數 vs 新增元素個數」分三種情況處理，極致優化資料移動：

1. 空間足夠且插入點後元素較多：尾部複制 n 個元素騰空間 → copy_backward 後移舊元素 → 填充新元素。
2. 空間足夠但插入點後元素較少：尾部建構新增元素 → 遷移插入點後舊元素 → 填充插入點位置。
3. 空間不足：分配新空間（舊大小 + max(舊大小, 新增個數)）→ 三段式遷移（插入點前、新元素、插入點後）→ 釋放舊空間。

erase() 與 clear()

iterator erase(iterator position) {
    if (position + 1 != end())
        copy(position + 1, finish, position); // 前移後續元素
    --finish;
    destroy(finish);
    return position;
}
void clear() { erase(begin(), end()); }

pop_back()

void pop_back() { --finish; destroy(finish); }

總結

Vector 透過三指標管理、兩倍擴容、分情況優化插入、POD/非 POD 差異化建構等精妙設計，在保證介面簡潔的同時實現了高效的動態陣列。原始碼中大量運用 uninitialized_copy、construct、destroy 等底層記憶體操作，展現了 STL 記憶體管理的藝術。