C++ 封裝向量（Vector）容器：自動擴容、迭代器與泛型實現

STL std::vector 是 C++ 最常用的動態陣列容器，其核心特性在於連續記憶體、自動擴容、隨機訪問 O(1)。本文將從零手寫一個精簡版 ZArray，涵蓋抽象基類設計、模板實現、迭代器模式、擴縮容策略與單元測試，幫助您深入理解 STL 內部機制。

設計前的思考

• 自動擴容：容量不足時按 2 倍分配新記憶體、拷貝舊資料、釋放舊空間
• 迭代器訪問：解耦容器與遍歷邏輯，支援多態
• 下標隨機訪問：operator[]、at()
• 增刪查改：push_back、pop、remove
• 長度管理：length()、capacity

三層架構設計

1. 抽象基類 Sequence<T>

定義容器統一介面：push_back、pop、at、remove、iterator、operator[]，並提供預設 remove(val, compare) 通用實現。

2. 抽象迭代器 Iterator<T>

定義遍歷協議：next()、data()、hasNext()、operator++（前置/後置）。

3. 具體實現 ZArray<T> & ZArrayIterator<T>

• 資料成員：_array（動態陣列）、_length、capacity
• expand()：capacity << 1（乘 2）
• shink()：capacity >> 1（除 2），可選實現
• 迭代器內部僅持有 pointTo（索引）與容器指標

// 擴容核心邏輯
T* expand() {
    T* newLoc = new T[capacity << 1];
    for (size_t i = 0; i < _length; ++i) newLoc[i] = _array[i];
    delete[] _array;
    _array = newLoc;
    capacity <<= 1;
    return _array;
}

// push_back 自動觸發擴容
void push_back(const T& val) {
    if (_length == capacity) _array = expand();
    _array[_length++] = val;
}

模板實現注意事項

模板類的聲明與定義必須放在同一個頭檔中，否則會產生連結錯誤（undefined reference），因為編譯器需要在實例化點看到完整定義。

單元測試驗證

基本型別 int

ZArray<int>* arr = new ZArray<int>(6);
arr->push_back(5); arr->push_back(6);
auto& it = arr->iterator();
while (it.hasNext()) cout << it.data() << endl, ++it;
cout << "length: " << arr->length() << endl;
cout << arr->at(0) << endl;
cout << arr->pop(0) << " after length:" << arr->length() << endl;

自訂類別 Student

class Student { string name; int age; /* 建構、拷貝、display() */ };
ZArray<Student>* arr = new ZArray<Student>;
arr->push_back(Student("zz", 19));
arr->push_back(Student("ee", 20));
// 迭代器遍歷呼叫 display()

核心設計模式總結

反思與擴展

• 目前 remove 為 O(n) 移動元素，可考慮「交換刪除」優化至 O(1)（順序不敏感時）
• 缺少 reserve、shrink_to_fit、insert、emplace_back 等現代 C++ 接口
• 記憶體管理可引入 std::allocator 或自定義分配器
• 異常安全性：擴容時若拷貝拋出異常，需保證強異常安全

這個練習雖簡單，卻完整展現了「封裝、繼承、多態、泛型」四大支柱如何協作構建工業級容器雛形。STL 的核心思想，正是以不變的代碼框架承載可變的資料型別與演算法。