一、迭代器：泛型指標
- 重載
*, ->, ++, -- 等運算子。
- 普通指標指向記憶體位址；迭代器指向容器內位置。
- 每個容器定義專屬迭代器類型，演算法透過統一介面操作不同容器。
二、迭代器五大類別
| 類別 | 支援操作 | 典型容器 |
|---|
| Input Iterator | *p, ++ | istream_iterator |
| Output Iterator | *p = val, ++ | ostream_iterator |
| Forward Iterator | Input + Output, 單向遍歷 | forward_list |
| Bidirectional Iterator | Forward + -- | list, set, map |
| Random Access Iterator | Bidirectional + +n, -n, [] | vector, deque, string |
能力遞增：Input/Output → Forward → Bidirectional → Random Access。
三、容器常用成員函數
begin(), end(), rbegin(), rend()size(), empty(), max_size()insert(), erase(), clear(), swap()- 序列容器額外：
push_back(), pop_back(), front(), back(), resize(), reserve()（vector/string）
- 關聯容器額外：
find(), count(), lower_bound(), upper_bound(), equal_range()
四、迭代器實作剖析（以 vector 為例）
// 簡化版
template
class _Vector_const_iterator {
typedef T* pointer;
pointer _Myptr; // 內部就是原始指標
public:
T& operator*() const { return *_Myptr; }
_Vector_const_iterator& operator++() { ++_Myptr; return *this; }
// ...
};
template
class _Vector_iterator : public _Vector_const_iterator {
// 繼承 const 版本，operator* 回傳 non-const reference
};
typedef _Vector_iterator iterator;
typedef reverse_iterator reverse_iterator; // 適配器包裝
迭代器本質是包裝原始指標的智慧指標；reverse_iterator 以適配器模式包裝正向迭代器實現反向遍歷。
五、迭代器失效規則（關鍵！）
vector
push_back：若觸發擴容（capacity 變化），**所有**迭代器失效；否則僅 end() 失效。insert/erase：插入/刪除點及其後所有迭代器失效。
deque
- 頭尾插入：不失效任何迭代器。
- 頭尾刪除：僅指向被刪除元素的迭代器失效。
- 中間插入/刪除：**所有**迭代器失效。
list / set / map（節點式容器）
- 插入：不失效任何迭代器。
- 刪除：僅指向被刪除節點的迭代器失效，其餘不受影響。
六、安全使用建議
// 正確：使用 insert/erase 返回的新迭代器
iter = vec.insert(iter, val);
iter = vec.erase(iter);
// 錯誤：迭代器失效後繼續使用
for (auto it = v.begin(); it != v.end(); ++it) {
if (cond) v.erase(it); // UB!
}
原則：修改容器結構後，重新獲取迭代器或使用返回值。
