C++ Vector 容器手寫實現：內存管理、迭代器與擴容機制

實現目標

從零手寫一個符合 STL 風格的 Vector<T>，涵蓋：

• 動態數組內存管理（分配/釋放/擴容）
• 元素構造/析構/拷貝/移動語義
• 迭代器支持（begin(), end(), 隨機訪問）
• 核心接口：push_back, size, capacity, operator[], 拷貝構造/賦值、析構函數

關鍵設計決策

1. 不使用 new/delete 直接管理對象：new 會同時分配內存並調用構造函數，而 Vector 需要分離「原始內存分配」與「對象構造」。採用 std::allocator<T>（或 malloc/free）獲取原始內存，再用 allocator::construct/destroy 或 uninitialized_fill/copy 操作對象。
2. 三指針結構：
   • data_：數組起始地址
   • avail_：已構造元素末尾的下一位置（即 size）
   • limit_：已分配內存末尾的下一位置（即 capacity）
3. 擴容策略：容量翻倍（max(2*size, 1)），分配新塊，uninitialized_copy 移動舊元素，銷毀舊塊並釋放。
4. 拷貝語義：深拷貝，賦值運算符先 uncreate() 釋放自身資源，再 create(rhs.begin(), rhs.end()) 複製。

核心代碼（C++98 風格，兼容 C++11）

#ifndef VECTOR_H_
#define VECTOR_H_
#include 
#include 
#include 

template 
class Vector {
public:
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef size_t size_type;
    typedef T value_type;

    Vector() { create(); }
    explicit Vector(size_type n, const T& val = T()) { create(n, val); }
    Vector(const Vector& v) { create(v.begin(), v.end()); }
    ~Vector() { uncreate(); }

    Vector& operator=(const Vector& rhs) {
        if (this != &rhs) { uncreate(); create(rhs.begin(), rhs.end()); }
        return *this;
    }

    T& operator[](size_type i) { return data_[i]; }
    const T& operator[](size_type i) const { return data_[i]; }

    void push_back(const T& val) {
        if (avail_ == limit_) grow();
        unchecked_append(val);
    }

    size_type size() const { return avail_ - data_; }
    size_type capacity() const { return limit_ - data_; }
    iterator begin() { return data_; }
    const_iterator begin() const { return data_; }
    iterator end() { return avail_; }
    const_iterator end() const { return avail_; }

private:
    iterator data_, avail_, limit_;
    std::allocator alloc_;

    void create() { data_ = avail_ = limit_ = 0; }
    void create(size_type n, const T& val) {
        data_ = alloc_.allocate(n);
        limit_ = avail_ = data_ + n;
        std::uninitialized_fill(data_, limit_, val);
    }
    void create(const_iterator b, const_iterator e) {
        data_ = alloc_.allocate(e - b);
        limit_ = avail_ = std::uninitialized_copy(b, e, data_);
    }
    void uncreate() {
        if (data_) {
            iterator it = avail_;
            while (it != data_) alloc_.destroy(--it);
            alloc_.deallocate(data_, limit_ - data_);
        }
        data_ = limit_ = avail_ = 0;
    }
    void grow() {
        size_type new_size = std::max(2 * (limit_ - data_), std::ptrdiff_t(1));
        iterator new_data = alloc_.allocate(new_size);
        iterator new_avail = std::uninitialized_copy(data_, avail_, new_data);
        uncreate();
        data_ = new_data;
        avail_ = new_avail;
        limit_ = data_ + new_size;
    }
    void unchecked_append(const T& val) {
        alloc_.construct(avail_++, val);
    }
};
#endif

測試用例

#include "Vector.hpp"
#include 
#include 
using namespace std;

int main() {
    Vector vec(3, "hello");
    for (auto it = vec.begin(); it != vec.end(); ++it) cout << *it << ' ';
    cout << "\nsize = " << vec.size() << ", capacity = " << vec.capacity();

    vec.push_back("foo");
    vec.push_back("bar");
    cout << "\nsize = " << vec.size() << ", capacity = " << vec.capacity();
    return 0;
}

輸出示例

hello hello hello
size = 3, capacity = 3
size = 5, capacity = 6

避坑指南

總結

手寫 Vector 是理解 STL 容器底層機制的最佳練習。核心在於「三指針 + allocator + uninitialized_* 算法」的協作，實現了內存與對象生命周期的精確控制。掌握此模式，可舉一反三實現 List、Deque 等容器。