vector：動態數組首選
連續內存，隨機訪問 O(1)，尾部增刪均攤 O(1)。關鍵方法：`push_back`, `pop_back`, `insert`, `erase`, `resize`, `reserve`, `clear`, `swap`, `assign`, `front`, `back`, `operator[]`, `at`, `begin`, `end`。比較運算符支持字典序比較。
迭代器：容器與算法的膠水
五類：輸入、輸出、前向、雙向、隨機訪問。`vector::iterator` 為隨機訪問迭代器。`begin()` 指首元素，`end()` 指尾後。配合 STL 算法（`copy`, `sort`, `find` 等）實現泛型編程。範圍 for 底層即迭代器遍歷。
string：字符串專用容器
本質 `vector`，支持 `+`, `+=`, `==`, `<`, `substr`, `find`, `c_str` 等豐富操作。優先用 `string` 替代 `char*`。
stack / queue / priority_queue：受限容器適配器
- `stack`：`push`, `pop`, `top`, `empty`, `size`。底層默認 `deque`。
- `queue`：`push`, `pop`, `front`, `back`, `empty`, `size`。底層默認 `deque`。BFS 必備。
- `priority_queue`：堆實現，`top` 返回最大元素（默認 `less`）。自定義比較：重載 `operator<` 或模板參數 `greater`/自定義函數對象。例題 POJ 1338 丑數。
map / multimap：有序關聯容器
紅黑樹實現，鍵值對 `pair`，鍵唯一（`multimap` 允許重複）。`operator[]` 自動插入/修改，`insert`, `find`, `erase`, `lower_bound`, `upper_bound`。迭代器遍歷按鍵升序。例題 HDU 1263 水果。嵌套 `map>` 處理多級分類統計。
set / multiset：有序集合
紅黑樹，自動去重（`multiset` 允許重複），有序遍歷。自定義比較：構造函數傳仿函數 `struct Cmp { bool operator()(A a, B b) { return a.id > b.id; } }`。結構體排序需定義比較邏輯。
常用算法速查
- `min_element` / `max_element`：返回迭代器，解引用得值。
- `sort(begin, end)` / `sort(begin, end, greater<()>)`：O(n log n)，不穩定。穩定用 `stable_sort`。
- `copy(src_begin, src_end, dest_begin)`：區間複製，目標空間需足夠。支持重疊複製（如向右移動）。
- `lower_bound` / `upper_bound` / `equal_range`：二分查找區間。
- `unique`：移除相鄰重複，返回新邏輯末尾，需配合 `erase`。
- `reverse` / `rotate` / `partition`：序列變換。
allocator：底層內存分配器
分離內存分配與對象構造：`allocate(n)` 獲取原始內存，`construct(p, args)` 就地構造，`destroy(p)` 析構，`deallocate(p, n)` 釋放。`uninitialized_copy/fill` 算法配合使用。`vector`/`string` 內部使用分配器。
競程實戰技巧
- `ios::sync_with_stdio(false); cin.tie(nullptr);` 加速 I/O。
- 優先用 `vector` 替代動態數組，`string` 替代 `char[]`。
- `priority_queue` 解決 Top-K、 Dijkstra、Huffman 等堆問題。
- `map`/`set` 處理離散化、計數、區間查詢。
- 整除分塊、莫比烏斯反演等數論題常用 `vector` 預計算前綴和。
- 自定義 `struct` + `operator<` / 仿函數 適配有序容器。
總結
STL 是 C++ 競程的核心武器庫。熟練掌握容器特性、迭代器範式、算法庫、分配器模型，能將複雜問題轉化為標準組件組合，代碼簡潔、高效、少錯。本文匯總高頻知識點，適合作為速查手冊與系統複習教材。
