STL 容器
C++ 標準模板庫 (STL) 提供了一組豐富的通用類別和函式，它們實作了常見的資料結構和演算法。容器是儲存資料的物件。它們是模板類別，這表示它們可以容納任何資料類型的元素。理解 STL 容器對於高效且穩健的 C++ 程式設計至關重要，它提供了 JavaScript 內建陣列和物件類型的一個強大替代方案。
序列容器：vector、list、deque
序列容器以線性方式儲存元素，允許透過其位置存取元素。
std::vector
- 動態陣列： 類似於 JavaScript 陣列，
std::vector是一個動態陣列，其大小可以增長或縮小。 - 連續記憶體： 元素儲存在連續的記憶體位置，允許高效的隨機存取 (O(1))。
- 高效的尾部插入/刪除： 在尾部新增/移除元素是高效的 (攤銷 O(1))。
- 低效的中間插入/刪除： 在中間插入/刪除需要移動元素 (O(n))。
正在加载...
std::list
- 雙向鏈結串列： 元素不連續儲存。每個元素儲存指向前一個和後一個元素的指標。
- 高效的任意位置插入/刪除： 在列表中的任何位置新增/移除元素是高效的 (O(1))，一旦找到位置。
- 低效的隨機存取： 透過索引存取元素需要遍歷列表 (O(n))。
std::deque (雙端佇列)
- 區塊的動態陣列： 將元素儲存在非連續的記憶體區塊中。
- 高效的頭部/尾部插入/刪除： 在兩端新增/移除元素是高效的 (攤銷 O(1))。
- 高效的隨機存取： 支援隨機存取 (O(1))，儘管比
std::vector稍慢。
關聯容器：map、set、unordered_map
關聯容器以排序或雜湊方式儲存元素，允許根據鍵高效地查找。
std::map
- 排序的鍵值對： 以鍵值對的形式儲存元素，按鍵排序。
- 唯一鍵： 每個鍵必須是唯一的。
- 對數時間複雜度： 查找、插入和刪除操作通常是 O(log n)，因為其底層是樹狀結構（通常是紅黑樹）。
正在加载...
std::set
- 排序的唯一元素： 以排序順序儲存唯一元素。
- 對數時間複雜度： 查找、插入和刪除是 O(log n)。
std::unordered_map
- 雜湊的鍵值對： 使用雜湊表儲存鍵值對。
- 唯一鍵： 每個鍵必須是唯一的。
- 平均常數時間複雜度： 查找、插入和刪除通常平均為 O(1)，但在最壞情況下（雜湊衝突）可能退化為 O(n)。
std::unordered_set
- 雜湊的唯一元素： 使用雜湊表儲存唯一元素。
- 平均常數時間複雜度： 查找、插入和刪除通常平均為 O(1)。
容器適配器：stack、queue、priority_queue
容器適配器為底層容器提供受限介面，強制執行特定的資料存取模式。
std::stack
- 後進先出 (LIFO)： 元素從頂部新增和移除。
- 操作：
push、pop、top、empty、size。
std::queue
- 先進先出 (FIFO)： 元素新增到尾部，從頭部移除。
- 操作：
push、pop、front、back、empty、size。
std::priority_queue
- 最高優先級優先： 元素根據其優先級（預設為最大元素）檢索。
- 操作：
push、pop、top、empty、size。
迭代器概念和用法
迭代器是行為類似指標的物件，允許你遍歷容器的元素。它們提供了一種通用的方式來存取元素，無論容器類型如何。
begin()：返回指向第一個元素的迭代器。end()：返回指向最後一個元素之後的元素的迭代器（一個哨兵）。*iterator：解引用迭代器以獲取元素的值。++iterator：將迭代器移動到下一個元素。
正在加载...
容器性能特性分析
選擇正確的容器對於性能至關重要。以下是常見操作的典型時間複雜度摘要：
| 容器 | 存取 (隨機) | 插入 (任意位置) | 刪除 (任意位置) | 搜尋 (按值) |
|---|---|---|---|---|
std::vector | O(1) | O(n) | O(n) | O(n) |
std::list | O(n) | O(1) | O(1) | O(n) |
std::deque | O(1) | O(n) (中間), O(1) (兩端) | O(n) (中間), O(1) (兩端) | O(n) |
std::map | N/A | O(log n) | O(log n) | O(log n) |
std::set | N/A | O(log n) | O(log n) | O(log n) |
std::unordered_map | N/A | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) |
std::unordered_set | N/A | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) |
與 JavaScript 陣列/物件的比較
JavaScript 的 Array 和 Object 類型功能非常強大，但它們抽象了底層的記憶體管理和特定的資料結構。C++ STL 容器提供了明確的選擇，允許開發人員為其特定需求選擇最高效的資料結構。
- JavaScript
Array： 對於數值索引，其行為有點像std::vector，但也可以作為字串鍵的雜湊映射。它是一個單一、靈活的資料結構。 - JavaScript
Object： 主要是一個雜湊映射（鍵值儲存），功能類似於std::unordered_map或std::map，但沒有 C++ 容器明確的性能保證或類型安全。
容器選擇指南
std::vector： 序列的預設選擇。當你需要快速隨機存取和高效的尾部新增/刪除時使用。避免頻繁地在中間插入/刪除。std::list： 當你需要頻繁地在序列中的任何位置插入/刪除，並且隨機存取不是主要考量時使用。std::deque： 當你需要高效地在兩端插入/刪除，並且也需要快速隨機存取時使用。std::map/std::set： 當你需要排序的鍵值對 (map) 或唯一的排序元素 (set) 以及操作的對數時間複雜度時使用。當順序很重要時很有用。std::unordered_map/std::unordered_set： 當你需要平均情況下 O(1) 的快速查找、插入和刪除，並且元素順序不重要時使用。雜湊表類行為的理想選擇。std::stack/std::queue/std::priority_queue： 當你需要特定的 LIFO、FIFO 或基於優先級的存取模式時分別使用。
練習題：
- 描述
std::vector和std::list在其底層資料結構以及插入/刪除和隨機存取的性能特性方面的主要差異。 - 何時會選擇
std::map而不是std::unordered_map，反之亦然？解釋其權衡。 - 迭代器如何簡化 C++ 中不同 STL 容器的使用？提供一個使用迭代器遍歷
std::vector和std::list的簡單範例。
專案構想：
- 使用
std::map實作一個簡單的聯絡人管理系統，其中鍵是聯絡人的姓名（字串），值是包含其電話號碼和電子郵件的結構/類別。允許使用者新增、刪除、搜尋和顯示聯絡人。然後，嘗試使用std::vector的結構實作相同的系統，並比較搜尋操作的複雜度。