C++ 標準模板庫 (STL) 核心架構詳解

一、基本概念

1.1 泛型程式設計

C++ 的核心優勢在於軟體重用，體現在兩大範式：

• 面向對象：繼承、多態、標準類庫。
• 泛型程式設計：模板機制、標準模板庫 (STL)。

泛型程式設計將常用數據結構（鏈表、數組、二叉樹等）與算法（排序、查找等）寫成模板，使用時無關具體數據類型，避免重複造輪子，且性能極高。

1.2 STL 三大核心組件

對象插入容器時存入的是副本；許多算法需比較元素，故放入容器的類型通常應重載 == 與 < 運算符。

二、容器詳解

2.1 順序容器

元素順序由插入位置決定，與值無關。

2.2 關聯容器

元素自動按鍵值排序（通常用紅黑樹實現），查找/插入/刪除均為 O(log N)。

2.3 容器適配器

2.4 通用成員函數

• 迭代器：begin(), end(), rbegin(), rend()
• 容量/修改：size(), empty(), clear(), erase()
• 元素存取：front(), back(), push_back(), pop_back()

三、迭代器

3.1 基本用法

vector v = {1,2,3,4};
// 常量迭代器（只讀）
for (auto it = v.cbegin(); it != v.cend(); ++it) cout << *it << ',';
// 反向迭代器
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) cout << *rit << ',';
// 非常量迭代器（可修改）
for (auto it = v.begin(); it != v.end(); ++it) *it = 100;

3.2 迭代器分類與操作

容器適配器（stack/queue/priority_queue）不支援迭代器。

四、算法概覽

4.1 設計原則

• 算法即函數模板，多數在 <algorithm> 中。
• 透過迭代器操作容器，實現容器無關性。
• 許多算法接受區間 [first, last)（左閉右開）。
• 可作用於容器，也可作用於原始數組。

4.2 典型算法原型

template 
InIt find(InIt first, InIt last, const T& val); // 返回指向 val 的迭代器，或 last

五、STL 中「大、小、相等」的語義

• 預設以 operator< 定義「小」：x < y 為真 ⇔ x 比 y 小 ⇔ y 比 x 大。
• 「相等」有兩種語境：
  • 無序區間算法（如 find）：x == y 為真。
  • 有序區間算法/關聯容器：!(x < y) && !(y < x) 視為相等（即嚴格弱序下的等價）。
• 使用者可自定義比較函數/函數對象，改變排序與相等判斷規則。

示例：自定義比較

class A {
    int v;
public:
    A(int v):v(v){}
    bool operator<(const A& a) const {
        cout << v << "<" << a.v << "? ";
        return v < a.v;
    }
};
// binary_search 會用 !(a