C++ STL 容器完全指南：序列、關聯與適配器

為什麼選擇 STL 容器？

手寫動態數組、鏈表、映射表雖能鍛鍊功力，但在生產代碼中，STL 容器以專家級實現、卓越效率、強異常安全保證完勝自製輪子。本文系統梳理 STL 核心容器體系。

容器分類全景圖

1. 序列式容器 — 線性存儲，位置敏感

2. 關聯式容器 — 基於鍵值，有序存儲，查找 O(log n)

3. 容器適配器 — 封裝底層容器，提供特定接口

• stack：後進先出（LIFO），默認底層 deque，核心 push/pop/top
• queue：先進先出（FIFO），默認底層 deque，核心 push/pop/front/back，注意：vector 無 pop_front 不能作為 queue 底層
• priority_queue：優先級隊列，默認底層 vector + less<T>（大頂堆），可自定義比較函數

容器通用接口速查

幾乎所有容器共享：構造/拷貝/析構、empty/size/max_size、賦值/比較運算符、swap、迭代器 begin/end/rbegin/rend、erase/clear。

深度解析：vector 實戰精要

構造與初始化

vector v1;                 // 空
vector v2(10);             // 10 個 0
vector v3(10, 42);         // 10 個 42
vector v4(v3);             // 拷貝構造
vector v5{v3.begin(), v3.end()};// 範圍構造 (C++11)

核心操作

• 增：push_back、insert（單值/多值/範圍）、emplace_back (C++11 原地構造)
• 刪：pop_back、erase（單位置/範圍）、clear
• 查：at（帶邊界檢查）、operator[]、front/back、data() 獲取底層數組指針
• 容量管理：size/capacity/reserve/resize/shrink_to_fit (C++11)

避坑指南

1. 迭代器失效：任何導致內存重新分配的操作（push_back、insert、reserve 等）會失效所有迭代器、指針、引用。
2. 擴容策略：通常按 1.5~2 倍增長，capacity 只增不減，shrink_to_fit 為非強制請求。
3. 結構體元素：擴容移動會觸發移動構造/析構，確保類型滿足 MoveConstructible。

進階容器實戰片段

priority_queue 自定義比較 — 學生成績排名

struct Student {
    int id; string name; int math, chinese;
    bool operator<(const Student& o) const { // less: 小者優先級低(堆頂)
        if (math != o.math) return math < o.math;
        if (chinese != o.chinese) return chinese < o.chinese;
        return id < o.id;
    }
};
// 大頂堆：數學高者優先，同分比語文，再比學號
priority_queue, less> pq;
// 若想小頂堆：greater 並重載 operator>

bitset 位壓縮存儲 — 節省 93.75% 空間

某系統需存儲 4 組長度 10、元素範圍 [1,20] 的遞增整數數組。int[10] 需 40 字節，改用 bitset<24> 僅 3 字節（對齊到字節），壓縮比 1/13.3。

template
class BitArray {
    bitset bits;
public:
    void set(const int* arr, int n) {
        bits.reset();
        for (int i=0; i

set s = {1,3,5,7,9};
auto itLow = s.lower_bound(4);  // 指向 5 (首個 >=4)
auto itUp  = s.upper_bound(4);  // 指向 5 (首個 >4)
auto range = s.equal_range(5);  // pair 等於 5 的區間

map festival;
festival["1-1"] = "元旦";           // operator[] 插入/修改
festival.insert({"5-1", "勞動節"}); // insert 不覆蓋既有鍵
// multimap 允許重複鍵，insert 必須用 pair 或 emplace