手寫常見操作：vector 擴容、string 分割、鏈表翻轉

（一）vector擴容

在 C++ 中，vector 的擴容機制是動態數組實現的核心特性，直接關系到性能和內存使用效率。以下是深入剖析：

---

1. 擴容觸發條件

vector<int> v;
v.push_back(1);  // 當 size() == capacity() 時觸發擴容

• 當插入新元素時，若當前元素數量 size() 等于容量 capacity()，則觸發擴容

---

2. 擴容算法核心步驟

// 偽代碼邏輯
void push_back(const T& value) {if (size == capacity) { // 需要擴容new_cap = max(2 * capacity, 1); // 典型增長策略new_data = allocate(new_cap);    // 1. 申請新內存copy_or_move(old_data, new_data); // 2. 遷移數據deallocate(old_data);            // 3. 釋放舊內存}// 插入新元素...
}

---

3. 關鍵特性與復雜度分析

(1) 擴容因子（Growth Factor）

編譯器實現	擴容策略	數學證明最優性
GCC	2 倍擴容（常見）	分攤 O(1) 時間復雜度
MSVC	1.5 倍擴容	更好內存利用率

(2) 時間復雜度

• 單次 push_back：最壞 O(n)（觸發擴容時）
• 均攤時間復雜度：O(1)（通過分攤分析證明）

---

4. 擴容過程可視化

vector<int> v;
// 初始狀態: capacity=0, size=0v.push_back(1); // 第1次擴容 → capacity=1
v.push_back(2); // 第2次擴容 → capacity=2
v.push_back(3); // 第3次擴容 → capacity=4
v.push_back(4); // 無需擴容
v.push_back(5); // 第4次擴容 → capacity=8

---

5. 性能優化技巧

(1) 預分配內存

vector<int> v;
v.reserve(1000); // 直接分配足夠容量，避免多次擴容

(2) 移動語義優化（C++11+）

class BigObject {
public:BigObject(BigObject&& other) noexcept; // 移動構造函數
};vector<BigObject> v;
v.push_back(BigObject()); // 觸發移動而非拷貝

---

6. 不同編譯器的擴容策略

通過代碼驗證不同編譯器的擴容行為：

vector<int> v;
size_t last_cap = 0;for (int i = 0; i < 100; ++i) {v.push_back(i);if (v.capacity() != last_cap) {cout << "Size: " << v.size() << ", New Capacity: " << v.capacity() << endl;last_cap = v.capacity();}
}

• GCC 輸出：1 → 2 → 4 → 8 → 16 → 32 → 64 → 128…
• MSVC 輸出：1 → 2 → 3 → 4 → 6 → 9 → 13 → 19…

---

7. 擴容時的元素遷移

• 拷貝語義：調用元素的拷貝構造函數（深拷貝）
• 移動語義（C++11+）：優先調用移動構造函數（高效）