C++ STL 迭代器深度解析：從智能指針到失效規則完全指南

前言：為什麼需要迭代器？

在 C/C++ 中，裸指針雖強大但極易導致記憶體洩漏（如 new 後未 delete、異常拋出導致釋放邏輯跳過）。C++ 引入**智能指針**（如已棄用的 auto_ptr、現代的 unique_ptr/shared_ptr）透過 RAII 機制自動管理生命週期。**迭代器**正是 STL 對「智能指針」思想的另一種應用：封裝原始指針操作，提供統一、安全、泛型的容器遍歷介面。

迭代器：連接容器與算法的橋樑

STL 六大組件中，迭代器扮演「中介者」角色。以 find 為例：

vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
auto it = find(vec.begin(), vec.end(), 7);

find 原型為 template<class InputIt, class T> InputIt find(InputIt first, InputIt last, const T& val)。它完全不關心底層容器是 vector、list 還是 deque，只需輸入迭代器支援 ++、==、!=、解引用即可。這正是**泛型程式設計**的精髓：算法與容器解耦，迭代器提供統一協定。

五大迭代器類別與能力階層

**關鍵繼承關係**：RandomAccess → Bidirectional → Forward → Input。派生類物件可隱式轉型為基類參數，故 vector::iterator（Random Access）可直接傳給要求 InputIterator 的 find。

容器專屬迭代器與失效規則（核心重點）

每個容器內部實現不同，其迭代器行為亦異。**迭代器失效**指原指向元素被移動或銷毀，繼續使用會導致未定義行為。

vector

• 插入（push_back, insert）：
  • 觸發擴容（capacity 變化）→ 所有迭代器失效
  • 未擴容 → 插入位置**之後**的迭代器失效
• 刪除（erase, pop_back, clear）：被刪除元素及其**之後**的迭代器失效
• resize：
  • size > capacity → 全部失效
  • size < capacity 且縮小 → 被切除元素的迭代器失效
• 賦值/assign：左側容器所有迭代器失效
• swap：**不失效**（僅交換內部指標）

deque

• 首尾 push_front/back：**不失效**
• 中間插入/刪除：**全部失效**
• 首尾刪除：僅被刪除元素迭代器失效

list / set / map（節點基礎容器）

• 插入：**從不失效**
• 刪除：**僅被刪除元素的迭代器失效**
• 原因：節點通過指標連結，增刪僅調整指標，不移動其他節點記憶體

STL 迭代器內部實現精要

標準庫通過以下機制實現泛型操作：

1. 標籤類別：input_iterator_tag 等空結構體，用於函式重載分派（如 distance, advance）。
2. iterator 基類模板：定義五大嵌套型別（iterator_category, value_type, difference_type, pointer, reference）。
3. iterator_traits：萃取機制，支援原始指針偏特化，使算法能統一處理迭代器與指針。
4. 核心算法：distance（輸入迭代器 O(n)、隨機存取 O(1)）、advance（根據類別選擇 ++ 迴圈或 +=n）。

實戰建議與最佳實踐

1. 優先使用 auto + begin()/end()，避免手寫冗長型別。
2. 範圍 for 迴圈（C++11）隱式使用迭代器，最安全簡潔。
3. 刪除時正確更新迭代器：it = vec.erase(it);（回傳下一個有效迭代器）。
4. 預留空間：vec.reserve(N) 減少擴容導致的迭代器失效。
5. 選擇合適容器：頻繁中間增刪用 list；需隨機存取用 vector；鍵值查找用 unordered_map。

結語

迭代器是 STL 泛型架構的基石，理解其分類、失效規則與實現原理，能讓你寫出更健壯、高效的 C++ 代碼。下次當你看到 for (auto& x : container) 時，腦海中應浮現的是「這是一個安全、統一、零成本的抽象」，而非單純的語法糖。