STL 容器核心知識體系總結：迭代器、分配器、容器分類與操作大全

STL（標準模板庫）是 C++ 泛型編程基石，掌握其容器體系對高效開發至關重要。本文系統梳理迭代器分類、分配器機制、容器特性對比及通用操作接口。

一、迭代器體系

五大類別（能力遞增）

1. 輸入迭代器：單向只讀（如 istream_iterator）
2. 輸出迭代器：單向只寫（如 ostream_iterator）
3. 前向迭代器：多遍單向讀寫（如 forward_list）
4. 雙向迭代器：雙向遍歷（如 list、set、map）
5. 隨機訪問迭代器：任意跳轉（如 vector、deque、數組指針）

常用適配器迭代器

• back_insert_iterator：調用 push_back（適用 vector/deque/list）
• front_insert_iterator：調用 push_front（適用 deque/list）
• insert_iterator：調用 insert（適用所有關聯容器）
• reverse_iterator：反向遍歷適配器

二、分配器機制

分配器封裝內存管理策略，容器通過模板參數注入，默認 std::allocator 使用 new/delete。核心接口：

• allocate(n)：分配原始內存（未構造對象）
• construct(p, val)：在內存上構造對象
• destroy(p)：析構對象
• deallocate(p, n)：釋放內存
• rebind<U>::other：類型重綁定機制

自定義分配器可實現內存池、共享內存、對象追蹤等高級功能。

三、容器分類與特性對比

順序容器

關聯容器（紅黑樹實現，有序）

容器適配器

• stack：LIFO，默認 deque 底層
• queue：FIFO，默認 deque 底層
• priority_queue：最大堆，默認 vector 底層

四、通用操作接口

所有容器共有

• 構造/拷貝/析構/賦值/比較（== != < 等）
• empty()、size()、max_size()、swap()

順序/關聯容器共有

• begin/end/rbegin/rend 返回迭代器
• erase()、clear()

關鍵 typedef 類型

value_type、reference、iterator、const_iterator、reverse_iterator、difference_type、size_type

五、選型決策指南

1. 需隨機訪問、尾部高效增刪 → vector
2. 需雙端高效增刪 → deque
3. 頻繁中間增刪、無隨機訪問 → list
4. 需唯一鍵快速查找 → set/map
5. 允許重複鍵 → multiset/multimap
6. LIFO/FIFO/優先級 → stack/queue/priority_queue