STL set 容器深度解析：自定義類型比較規則與去重陷阱

set 基本特性回顧

• **有序、唯一** 的關聯式容器，底層通常為紅黑樹。
• 元素**不可重複**，判斷依據是 **operator< 定義的嚴格弱序**。
• 對於內建類型 (int、string 等) 直接可用；**自定義類型必須提供比較方式**。

自定義類型存入 set 的兩種方式

方式一：類內重載 operator<

class MyType {
public:
    int a, b, c;
    MyType(int a, int b, int c) : a(a), b(b), c(c) {}
    // 必須定義嚴格弱序
    bool operator<(const MyType& other) const {
        // 錯誤示範：只比較 a
        // return a < other.a;
        // 正確：全鍵比較
        if (a != other.a) return a < other.a;
        if (b != other.b) return b < other.b;
        return c < other.c;
    }
};

方式二：外部仿函數 / Lambda (C++11)

struct MyTypeCmp {
    bool operator()(const MyType& lhs, const MyType& rhs) const {
        if (lhs.a != rhs.a) return lhs.a < rhs.a;
        if (lhs.b != rhs.b) return lhs.b < rhs.b;
        return lhs.c < rhs.c;
    }
};

std::set s;
// 或
auto cmp = [](const MyType& l, const MyType& r) {
    return std::tie(l.a, l.b, l.c) < std::tie(r.a, r.b, r.c);
};
std::set s(cmp);

核心陷阱：不完整比較導致「誤判重複」

現象演示

class MyType {  // 只比較 a
    bool operator<(const MyType& o) const { return a < o.a; }
};

std::set s;
s.insert(MyType(1, 2, 3));  // 成功
s.insert(MyType(1, 2, 4));  // 失敗！set 認為與第一個相同
// s.size() == 1

原因解析

set 判斷兩元素相等的邏輯：

!(a < b) && !(b < a)  // 即 equivalent(a, b)

若 operator< 僅比較 a，則 (1,2,3) 和 (1,2,4) 互不小於，被視為**等價**，第二次插入被忽略。

正確比較實現（字典序）

bool operator<(const MyType& o) const {
    return std::tie(a, b, c) < std::tie(o.a, o.b, o.c);
    // 或手寫：
    // if (a != o.a) return a < o.a;
    // if (b != o.b) return b < o.b;
    // return c < o.c;
}

修正後，(1,2,3) 和 (1,2,4) 可共存，s.size() == 2。

嚴格弱序要求

比較函數 comp(a, b) 必須滿足：

1. **非自反性**：comp(a, a) == false
2. **反對稱性**：comp(a, b) == true ⇒ comp(b, a) == false
3. **傳遞性**：comp(a, b) && comp(b, c) ⇒ comp(a, c)
4. **等價傳遞性**：若 equiv(a, b) 且 equiv(b, c) 則 equiv(a, c)

違反上述任一條件 → **未定義行為**（可能死循環、崩潰、錯誤結果）。

常見錯誤模式

實用技巧

• 用 std::tie 自動生成字典序比較：簡潔、不易出錯、支援 C++11 起。
• 需要「多鍵值」查找：考慮 std::map 或 std::multimap，而非在 set 中塞入複合結構。
• 只需去重、不需有序：std::unordered_set (哈希表) 平均 O(1)，需提供 hash 與 ==。
• 調試技巧：在比較函數加日誌或斷點，觀察實際比較次序與等價判斷。

總結

1. 自定義類型入 set **必須**提供完整、正確的嚴格弱序比較。
2. **部分比較 = 誤判重複**，導致數據悄悄丟失，極難排查。
3. 推薦用 std::tie 一行搞定字典序，或外部仿函數分離比較邏輯。
4. 若業務允許「同鍵不同值」，改用 multiset 或 map。