C++ Primer 第5版 第9章順序容器完整筆記

9.1 順序容器概覽

C++ 標準庫提供 6 種順序容器：vector、deque、list、forward_list、array、string。選擇原則：

• 預設首選 vector：隨機訪問快、記憶體緊湊
• 需頭尾雙向高效插刪 → deque
• 需中間頻繁插刪 → list 或 forward_list
• 固定大小、嚴格棧分配 → array
• 字元序列專用 → string

9.2 容器操作核心

9.2.1 定義與初始化

vector v1;                    // 空
vector v2(10, 5);             // 10個5
vector v3{v2};                // 拷貝構造
vector v4 = {1,2,3,4,5};      // 列表初始化
list ls(istream_iterator(cin), {}); // 從輸入流構造

9.2.2 賦值與 swap

• c1 = c2 / c1.assign(b, e)：拷貝元素，迭代器失效
• swap(c1, c2)：常數時間交換內部結構（除 array 外），迭代器不失效（指向同元素，但屬於另一容器）

9.3 核心操作詳解

9.3.1 添加元素

9.3.2 訪問元素

• at(n) / operator[]：隨機訪問（vector, deque, string, array）
• front() / back()：首尾元素引用
• 順序容器不支援下標運算：list, forward_list

9.3.3 刪除元素

c.pop_back();           // 刪除尾部
c.pop_front();          // 刪除頭部 (deque, list, forward_list)
c.erase(pos);           // 刪除單個，返回下一有效迭代器
c.erase(beg, end);      // 刪除區間
c.clear();              // 清空

關鍵：erase 返回值必須接收，否則迭代器失效導致 UB。

9.3.4 forward_list 特有操作

單向鏈表無 push_back/back，提供 insert_after、erase_after、emplace_after，操作「前驅節點」而非目標節點。

9.3.5 改變容器大小

• resize(n)：擴大用值初始化填充，縮小截斷
• resize(n, val)：擴大用 val 填充
• capacity() / reserve()：僅 vector/string 支援，預分配避免重複擴容

9.4 string 專屬操作

9.4.1 構造與字串操作

• 從 C 風格字串、部分子串、重複字元構造
• substr(pos, len)、append、replace、insert、erase

9.4.2 搜尋與比較

s.find(args)       // 正向找第一個
s.rfind(args)      // 反向找第一個
s.find_first_of(args)  // 找任一字元首次出現
s.find_last_not_of(args) // 找最後一個不在集合中的字元
s.compare(s2)      // 字典序比較，返回負/0/正

9.4.3 數值轉換

• to_string(val)：數值 → string
• stoi/stol/stod 等：string → 數值，可指定進制、獲取處理字元數

9.5 容器適配器

在順序容器之上封裝特定介面：

• stack：LIFO，預設底層 deque，操作 push/pop/top
• queue：FIFO，預設 deque，操作 push/pop/front/back
• priority_queue：最大堆，預設 vector + less，操作 push/pop/top

適配器不支援迭代器，只能通過介面訪問。

學習建議

1. 熟記各容器「增刪改查」複雜度表
2. 實際項目中 vector 覆蓋 90% 場景
3. 善用 emplace_back 避免臨時對象拷貝
4. 迭代器失效規則是面試高頻考點，必須熟練