C++ std::set如何检测重复元素？代码实例解析

示例代码 #

#include <iostream>
#include "set"

using namespace std;

struct WeightedEdge {
public:
    int weight;
    int n1;
    int n2;

    WeightedEdge(int n1, int n2, int weight) {
        this->n1 = n1;
        this->n2 = n2;
        this->weight = weight;
    }

    void print() {
        cout << "WeightedEdge(" << "n1= " << n1 << ",n2= " << n2;
        cout << ",weight= " << weight << ")" << endl;
    }

    bool operator<(const WeightedEdge &other) const {
        if (weight < other.weight) {
            return true;
        } else if (weight > other.weight) {
            return false;
        } else {
            if (n1 < other.n1) {
                return true;
            } else if (n1 > other.n1) {
                return false;
            } else {
                if (n2 < other.n2) {
                    return true;
                } else if (n2 > other.n2) {
                    return false;
                } else {
                    return false;
                }
            }
        }
    }
};

int main() {
    set<WeightedEdge> edges;

    edges.insert(WeightedEdge(1, 2, 5));
    edges.insert(WeightedEdge(1, 12, 5));
    edges.insert(WeightedEdge(1, 5, 5));
    edges.insert(WeightedEdge(1, 3, 5));
    edges.insert(WeightedEdge(1, 2, 5));

    for (auto i = edges.begin(); i != edges.end(); ++i) {
        auto edge = *i;
        edge.print();
    }
}

核心逻辑：严格弱序下的等价判断 #

std::set判断元素是否重复，不是只看单次operator<的返回值，而是基于严格弱序规则：当且仅当!(a < b) && !(b < a)时，才会认为a和b是等价元素（即重复）。

针对示例的具体分析 #

• 插入(1,2,5)和(1,12,5)
  调用(1,2,5) < (1,12,5)时，n2=2 < 12，返回true；调用(1,12,5) < (1,2,5)时，n2=12 > 2，返回false。此时!(a < b)为false，!(b < a)为true，不满足等价条件，因此std::set认为二者是不同元素，允许插入。

• 插入两个(1,2,5)
  调用a < b时，所有属性均相等，返回false；调用b < a时，同样返回false。此时!(a < b) && !(b < a)的结果为true，std::set判定二者等价，因此拒绝插入第二个重复元素。

补充说明 #

std::set底层基于红黑树实现，必须依赖严格弱序的比较规则来维护容器的有序性和唯一性。你实现的operator<完全符合严格弱序的要求（满足反自反性、非对称性、传递性等），因此能正确完成元素的排序和重复检测。

内容的提问来源于stack exchange，提问作者Emad Kheyroddin