C++ STL 算法源碼深度解析：核心算法實現原理

C++ STL 算法源碼深度解析：核心算法實現原理

STL 算法是泛型編程的精華，本文解析 `` 中核心算法的實現邏輯，理解其對迭代器要求、優化策略、邊界處理。

search / search_n：子序列查找

// unique: 就地刪除相鄰重複
// 1. 保存第一個元素
// 2. 掃描：若當前 != 保存值 → 移動到下一位置，更新保存值
// 3. 返回新邏輯末尾

// unique_copy: 複製去重
// 類似，但寫入輸出迭代器

rotate：區間旋轉

三種迭代器類別的優化實現：

partition / stable_partition：分區

// 關鍵常數
const int __stl_threshold = 16;

// introsort_loop
while (last - first > __stl_threshold) {
    if (depth_limit == 0) { partial_sort(first, last, last); return; }
    --depth_limit;
    cut = unguarded_partition(first, last, median3);
    introsort_loop(cut, last, depth_limit);
    last = cut; // 尾遞歸優化
}
final_insertion_sort(first, last);

nth_element：選擇算法

快速選擇：partition 後只遞歸包含第 n 個元素的那一側，平均 O(n)。

lower_bound / upper_bound / equal_range：二分查找

merge / set_operations：有序區間運算

// 1. 從右向左找首個 a[i] < a[i+1]
// 2. 從右向左找首個 a[j] > a[i]
// 3. swap(a[i], a[j])
// 4. reverse(a[i+1], end)
// 字典序下一排列，O(n)

heap 操作：make_heap, push_heap, pop_heap, sort_heap

• 底層：完全二叉樹數組表示
• 調整：`__adjust_heap`、`__push_heap`、`__pop_heap`
• sort_heap：反覆 pop_heap 獲得有序序列

核心設計智慧

1. 迭代器分類：針對不同能力提供最優算法
2. 尾遞歸優化：`introsort_loop` 消除一半遞歸
3. 三數取中樞紐：避免有序數組最壞情況
4. 混合策略：大數據快排、深度過大堆排、小數據插排
5. 未檢查版本：`unguarded_*` 省去邊界檢查，性能極致

研讀 STL 源碼不僅能理解算法細節，更能學習到泛型編程、性能優化、接口設計的精髓。