STL 源碼級剖析：vector 容器的記憶體管理與核心操作實現

設計目標與核心結構

本文嘗試從零實現一個與 std::vector 介面相容的容器，核心要求：

1. 介面與 STL 完全一致，可直接替換使用。
2. 最大化實現標準介面（迭代器、容量管理、元素存取等）。

vector 本質是動態陣列，維護三個關鍵指標：

• T* buf：指向堆上連續記憶體塊
• size_t size_：當前元素個數
• size_t capacity_：已分配容量

擴容策略：幾何增長

當 size_ == capacity_ 時觸發擴容，典型增長因子為 1.5~2.0（本實現採用 2 倍）：

void newCapacity(size_t newCap) {
    T* newBuf = static_cast<T*>(::operator new(newCap * sizeof(T)));
    // 移動構造/拷貝構造現有元素
    for (size_t i = 0; i < size_; ++i)
        new (newBuf + i) T(std::move(buf[i])); // C++11 move 語義
    // 銷毀舊元素並釋放記憶體
    for (size_t i = 0; i < size_; ++i) buf[i].~T();
    ::operator delete(buf);
    buf = newBuf;
    capacity_ = newCap;
}

關鍵細節：使用 operator new 原始分配、placement new 就地構造、顯式呼叫解構函式，避免 new T[n] 強制要求預設構造函式。

插入操作：insert(iterator, const T&)

void insert(const_iterator iter, const T& t) {
    size_t index = iter - begin(); // 迭代器差值得索引
    if (index < size_) {
        if (size_ == capacity_) newCapacity(calculateCapacity());
        // 向後搬移 [index, size_) 區間
        std::memmove(buf + index + 1, buf + index,
                     (size_ - index) * sizeof(T));
        buf[index] = t; // 拷貝賦值
        ++size_;
    }
}

效能考量：

• 使用 memmove 而非逐元素搬移，針對 TriviallyCopyable 型別可優化為 memcpy。
• 非尾部插入平均時間 O(n)，尾部攤銷 O(1)。

刪除操作：erase(iterator) 與 clear()

iterator erase(const_iterator iter) {
    size_t index = iter - begin();
    if (index < size_ && size_ > 0) {
        // 向前搬移 (index, size_) 區間
        std::memmove(buf + index, buf + index + 1,
                     (size_ - index) * sizeof(T));
        buf[--size_] = T(); // 銷毀最後元素，置為預設值
    }
    return iterator(iter);
}

void clear() {
    while (size_ > 0) erase(begin()); // 僅銷毀元素，不釋放記憶體
}

設計哲學：clear() 保留容量，避免頻繁增減容造成記憶體碎片；記憶體釋放留給析構函式或 shrink_to_fit()。

迭代器實現要點

• 隨機存取迭代器：支援 +、-、[]、< 等運算，本質封裝 T*。
• begin() = buf，end() = buf + size_。
• const_iterator 透過 const T* 實現唯讀視圖。

完整介面清單（節選）

踩坑總結與最佳實踐

1. 異常安全：擴容時先構造新元素再銷毀舊元素，若構造拋出異常，原容器不變。
2. 移動語義：C++11 後優先使用 std::move 避免不必要拷貝。
3. 縮小容量：shrink_to_fit() 為非強制請求，實現可選擇忽略。
4. 對齊需求：C++17 std::aligned_alloc 或 alignas 處理過度對齊型別。