C++ STL set 容器詳解與集合運算實戰

set 簡介

set 是 STL 關聯容器，底層為紅黑樹（平衡二叉搜索樹），特點：

• 元素唯一、自動按鍵值排序（默認升序）。
• 不支持隨機訪問，只能通過迭代器遍歷。
• 插入、刪除、查找均為 O(log n)。
• 插入元素不會使現有迭代器失效（除非刪除該元素）。

常用成員函數

集合運算算法（需 ）

• set_union：並集
• set_intersection：交集
• set_difference：差集（第一個減第二個）
• set_symmetric_difference：對稱差集

以上算法輸出需用 inserter(dest, dest.begin()) 作為輸出迭代器。

實戰例題：集合運算輸出

輸入兩個集合 A、B，輸出 A、B、A∪B、A∩B、A-B、SA、SB（補集相對於 A∪B）。

代碼實現

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

void printSet(const set<int>& s) {
    cout << "{";
    for (auto it = s.begin(); it != s.end(); ) {
        cout << *it;
        if (++it != s.end()) cout << ", ";
    }
    cout << "}\n";
}

int main() {
    int T; cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        set<int> A, B, C;
        int n, x;
        cin >> n;
        while (n--) { cin >> x; A.insert(x); }
        cin >> n;
        while (n--) { cin >> x; B.insert(x); }
        cout << "Case# " << cas << ":\n";
        cout << "A = "; printSet(A);
        cout << "B = "; printSet(B);
        set_union(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
        cout << "A u B = "; printSet(C); C.clear();
        set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
        cout << "A n B = "; printSet(C); C.clear();
        set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
        cout << "A - B = "; printSet(C); C.clear();
        set_difference(B.begin(), B.end(), A.begin(), A.end(), inserter(C, C.begin()));
        cout << "SA = "; printSet(C); C.clear();
        set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
        cout << "SB = "; printSet(C);
    }
    return 0;
}

inserter 迭代器適配器

inserter(c, c.begin()) 創建一個插入迭代器，每次賦值時調用 c.insert(it, val)。適用于所有支持 insert 的容器（vector, list, set, map 等）。

總結

set 適合需要自動去重、有序存儲、頻繁查找/插入/刪除的場景。結合 中的集合運算算法，可輕鬆實現並集、交集、差集等操作。掌握迭代器遍歷與 inserter 用法是關鍵。