STL 算法源碼級解析：基本算法篇 (equal, fill, copy, lexicographical_compare 等)

SGI STL 算法實現精華

本文解析 SGI STL 中基本算法的源碼實現，展示模板元編程、迭代器萃取、類型特性、偏特化等高級技巧如何為通用算法提供極致性能。

1. equal - 序列比較

// 版本1：operator==
template <class InputIter1, class InputIter2>
bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2) {
    for (; first1 != last1; ++first1, ++first2)
        if (*first1 != *first2) return false;
    return true;
}

// 版本2：自定義二元謂詞
template <class InputIter1, class InputIter2, class BinaryPred>
bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2, BinaryPred pred) {
    for (; first1 != last1; ++first1, ++first2)
        if (!pred(*first1, *first2)) return false;
    return true;
}

注意：第二序列較長時多餘元素被忽略；較短時行為未定義 (調用者責任保證長度)。

2. fill / fill_n - 賦值填充

// 通用版本
template <class ForwardIter, class T>
void fill(ForwardIter first, ForwardIter last, const T& value) {
    for (; first != last; ++first) *first = value;
}

// 偏特化優化：針對 1 字節類型用 memset
inline void fill(unsigned char* first, unsigned char* last, const unsigned char& c) {
    memset(first, c, last - first);
}
inline void fill(signed char* first, signed char* last, const signed char& c) {
    memset(first, static_cast<unsigned char>(c), last - first);
}
inline void fill(char* first, char* last, const char& c) {
    memset(first, static_cast<unsigned char>(c), last - first);
}

// fill_n 返回填充區間結尾迭代器
template <class OutputIter, class Size, class T>
OutputIter fill_n(OutputIter first, Size n, const T& value) {
    for (; n > 0; --n, ++first) *first = value;
    return first;
}

技巧：函數重載 + 偏特化實現 POD 類型 memset 極速填充。

3. iter_swap - 迭代器所指對象交換

// 核心實現需要知道 value_type 來聲明臨時變量
template <class ForwardIter1, class ForwardIter2, class T>
inline void __iter_swap(ForwardIter1 a, ForwardIter2 b, T*) {
    T tmp = *a; *a = *b; *b = tmp;
}

// 公開接口提取 value_type
template <class ForwardIter1, class ForwardIter2>
inline void iter_swap(ForwardIter1 a, ForwardIter2 b) {
    __iter_swap(a, b, VALUE_TYPE(a)); // 宏展開為 iterator_traits<...>::value_type*
}

亮點：利用迭代器萃取機制獲取值類型，展現 STL 設計精妙。

4. lexicographical_compare - 字典序比較

// 通用版本
template <class InputIter1, class InputIter2>
bool lexicographical_compare(InputIter1 first1, InputIter1 last1,
                             InputIter2 first2, InputIter2 last2) {
    for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
        if (*first1 < *first2) return true;
        if (*first2 < *first1) return false;
    }
    return first1 == last1 && first2 != last2; // 第一序列先結束 = 較小
}

// 指針偏特化：調用 memcmp 極速比較
inline bool lexicographical_compare(const unsigned char* first1, const unsigned char* last1,
                                    const unsigned char* first2, const unsigned char* last2) {
    size_t len1 = last1 - first1, len2 = last2 - first2;
    int res = memcmp(first1, first2, min(len1, len2));
    return res != 0 ? res < 0 : len1 < len2;
}

優化：原生指針 + POD 類型直接調用高度優化的 memcmp。

5. min / max - 極值獲取

template <class T> inline const T& max(const T& a, const T& b) {
    return a < b ? b : a;
}
template <class T, class Compare> inline const T& max(const T& a, const T& b, Compare comp) {
    return comp(a, b) ? b : a; // comp 定義「小於」
}
// min 同理，邏輯反轉

6. mismatch - 首個不匹配點

template <class InputIter1, class InputIter2>
pair<InputIter1, InputIter2> mismatch(InputIter1 first1, InputIter1 last1, InputIter2 first2) {
    while (first1 != last1 && *first1 == *first2) { ++first1; ++first2; }
    return {first1, first2}; // 返回指向不匹配元素的迭代器對
}
// 若完全匹配，返回 (last1, first2+(last1-first1))

7. swap - 對象交換

template <class T> inline void swap(T& a, T& b) {
    T tmp = a; a = b; b = tmp; // 經典三步交換
    // C++11 後建議用 std::move 優化：T tmp = std::move(a); a = std::move(b); b = std::move(tmp);
}

8. copy / copy_backward - 核心拷貝算法 (最複雜、最精華)

分層派發機制

copy 根據迭代器類別和值類型特性，多層派發選擇最優實現：

// 入口
template <class InputIter, class OutputIter>
OutputIter copy(InputIter first, InputIter last, OutputIter result) {
    return __copy_aux(first, last, result, VALUE_TYPE(first));
}

// 層1：按迭代器類別分發 (InputIter vs RandomAccessIter)
template <class InputIter, class OutputIter, class Distance>
OutputIter __copy(InputIter first, InputIter last, OutputIter result, input_iterator_tag, Distance*) {
    for (; first != last; ++result, ++first) *result = *first; // 慢：逐個比較迭代器
    return result;
}
template <class RAIter, class OutputIter, class Distance>
OutputIter __copy(RAIter first, RAIter last, OutputIter result, random_access_iterator_tag, Distance*) {
    for (Distance n = last - first; n > 0; --n) { // 快：預知長度 n
        *result = *first; ++first; ++result;
    }
    return result;
}

// 層2：按值類型是否有 trivial assignment operator 分發
template <class T> inline T* __copy_trivial(const T* first, const T* last, T* result) {
    memmove(result, first, sizeof(T) * (last - first)); // 最快：內存塊拷貝
    return result + (last - first);
}

// 派發邏輯 (利用偏特化或函數重載)
struct __copy_dispatch<T*, T*, true_type> { // 偏特化：指針 + trivial assign
    static T* copy(const T* first, const T* last, T* result) {
        return __copy_trivial(first, last, result);
    }
};

copy_backward - 逆向拷貝 (處理重疊區間)

// 同樣的分層派發：BidirectionalIter vs RandomAccessIter + trivial assign
// 核心邏輯：從後往前 *--result = *--last
// 關鍵用途：vector::insert 向右移動元素時避免覆蓋

核心技術總結

SGI STL 算法實現展示了「泛型編程 + 編譯期優化」的極致：同一接口，根據類型屬性自動選擇從通用迭代器遍歷到裸指針 memmove 的最優路徑，這正是 STL 高性能的秘密。