STL 算法源碼級解析：集合算法篇 (set_union, intersection, difference, symmetric_difference)

集合算法前提條件

• 輸入區間必須已排序 (升序，由 operator< 或自定義 Compare 定義)
• 允許重復元素 (視為多重集合)
• 輸出區間需足夠大
• 算法穩定：相對順序保持，元素優先來自第一序列

1. set_union - 並集 (A ∪ B)

語義：輸出兩序列所有元素。若值在 A 出現 m 次，B 出現 n 次，輸出 max(m,n) 次 (優先來自 A)。

template <class InputIter1, class InputIter2, class OutputIter>
OutputIter set_union(InputIter1 first1, InputIter1 last1,
                     InputIter2 first2, InputIter2 last2,
                     OutputIter result) {
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) { *result = *first1; ++first1; }
        else if (*first2 < *first1) { *result = *first2; ++first2; }
        else { *result = *first1; ++first1; ++first2; } // 相等：取一個，雙雙前進
        ++result;
    }
    // 尾部剩餘直接拷貝
    return copy(first2, last2, copy(first1, last1, result));
}

2. set_intersection - 交集 (A ∩ B)

語義：輸出同時出現在兩序列的元素。若值在 A 出現 m 次，B 出現 n 次，輸出 min(m,n) 次 (全部來自 A)。

template <class InputIter1, class InputIter2, class OutputIter>
OutputIter set_intersection(InputIter1 first1, InputIter1 last1,
                            InputIter2 first2, InputIter2 last2,
                            OutputIter result) {
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) ++first1;
        else if (*first2 < *first1) ++first2;
        else { *result = *first1; ++first1; ++first2; ++result; } // 相等：輸出，雙雙前進
    }
    return result;
}

3. set_difference - 差集 (A - B)

語義：輸出「在 A 中但不在 B 中」的元素。若值在 A 出現 m 次，B 出現 n 次，輸出 max(m-n, 0) 次 (來自 A)。

template <class InputIter1, class InputIter2, class OutputIter>
OutputIter set_difference(InputIter1 first1, InputIter1 last1,
                          InputIter2 first2, InputIter2 last2,
                          OutputIter result) {
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) { *result = *first1; ++first1; ++result; } // 僅在A
        else if (*first2 < *first1) ++first2; // 僅在B，跳過
        else { ++first1; ++first2; } // 相等：抵消，雙雙前進
    }
    return copy(first1, last1, result); // A剩餘全部輸出
}

4. set_symmetric_difference - 對稱差集 (A Δ B = (A-B) ∪ (B-A))

語義：輸出「僅在其中一個序列中」的元素。若值在 A 出現 m 次，B 出現 n 次，輸出 |m-n| 次。若 m>n，多出的來自 A；反之來自 B。

template <class InputIter1, class InputIter2, class OutputIter>
OutputIter set_symmetric_difference(InputIter1 first1, InputIter1 last1,
                                    InputIter2 first2, InputIter2 last2,
                                    OutputIter result) {
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) { *result = *first1; ++first1; ++result; }
        else if (*first2 < *first1) { *result = *first2; ++first2; ++result; }
        else { ++first1; ++first2; } // 相等：抵消，雙雙前進
    }
    return copy(first2, last2, copy(first1, last1, result)); // 雙方剩餘全輸出
}

四大算法核心邏輯對比

自定義比較器版本

所有算法均提供接受 Compare comp 的重載，將 *a < *b 替換為 comp(*a, *b)，邏輯完全一致。

實戰應用示例

vector a = {1,2,2,3,4,5}, b = {2,2,4,6,7};
vector result;

// 並集
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// result: 1,2,2,3,4,5,6,7

// 交集
result.clear();
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// result: 2,2,4

// 差集 A-B
result.clear();
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// result: 1,3,5

// 對稱差集
result.clear();
set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// result: 1,3,5,6,7

複雜度與性能

• 時間：O(m+n) - 線性掃描，單次遍歷
• 空間：O(1) 輔助空間 (輸出空間不計)
• 穩定性：穩定，相對順序保持

常見誤區

1. 輸入未排序：結果未定義，必須先 sort。
2. 輸出迭代器無效：如直接寫入 vector 末尾需用 back_inserter 或預留空間。
3. 混淆 difference 方向：set_difference(A,B) 是 A-B，非 B-A。
4. 多重集合計數邏輯：理解 max/min/|m-n| 規則，而非簡單去重。

這四大集合算法是 STL 中「有序序列處理」的基石，掌握其多重集合語義與線性掃描邏輯，能高效解決去重、合並、差異檢測等大量實際問題。