C++ Primer 學習筆記 46：STL 剖析（一）—— 泛型程式設計、STL 六大組件與關係

一、泛型程式設計

• 核心思想：相同邏輯/演算法處理不同資料型別。
• 將演算法從資料結構抽象出來，實現通用化。
• C++ 模板為泛型程式設計奠定語言基礎。

二、什麼是 STL

• STL (Standard Template Library)：標準模板庫，高效 C++ 程式庫。
• 包含常用資料結構（容器）與演算法。
• 提供可擴展應用框架，體現軟體復用性。
• 邏輯層面體現泛型程式設計；實現層面採用型別參數化（模板）。

三、STL 六大組件

四、容器、演算法、迭代器關係

• 容器管理資料儲存。
• 演算法實作邏輯操作。
• 迭代器提供統一遍歷介面，使演算法與容器解耦。

五、容器分類與選擇指南

序列式容器

• vector：尾部增刪快，支援隨機存取，中間/頭部操作慢。
• deque：頭尾增刪快，支援隨機存取。
• list：任意位置增刪快，不支援隨機存取。

關聯式容器

• set/multiset、map/multimap：元素按值排序，查找 O(log n)。

六、迭代器分類

七、函數物件

• 重載 operator() 的類別物件，稱為仿函數。
• STL 內建算術、關係、邏輯三大類，需含 <functional>。

八、配置器

• 負責記憶體配置/釋放，預設 allocator 為兩級配置器：
• 大於 128 bytes：一級配置器直接 malloc。
• 小於 128 bytes：二級配置器從記憶池（16 個自由鏈表，8~128 bytes）分配，減少碎片、提升速度。
• 可自訂配置器作為容器模板參數：vector。

參考資料

• C++ Primer 第 4 版
• Effective C++ 3rd
• C++ 編程規範