面试题：C++中set如何保证元素唯一性

Question

在C++的STL中，set容器能保证其内部元素的唯一性。请详细阐述set是通过何种机制来实现这一特性的？并且说明如果自定义类型要放入set中，需要满足什么条件才能保证唯一性判断正确。

Answer 1

set实现元素唯一性的机制

1. 基于比较函数：
   • set 内部通常使用红黑树（一种自平衡二叉搜索树）来存储元素。在插入元素时，会根据元素的比较函数（默认是 std::less<T>，即小于运算符 <）来确定元素在树中的位置。
   • 当插入一个新元素时，set 会从根节点开始，根据比较函数将新元素与树中已有的节点进行比较。如果找到一个节点，其值与新元素相等（根据比较函数判断），则插入操作失败，因为 set 不允许重复元素。
   • 例如，对于 std::set<int>，默认比较函数是 <。如果插入一个值为 5 的元素，它会从根节点开始比较，如果已有值为 5 的节点，就不会再插入。
2. 比较函数的严格弱序性质：
   • set 使用的比较函数必须满足严格弱序（strict weak ordering）关系。这意味着对于任意三个元素 a、b 和 c：
     • 反对称性：如果 a < b 为真，则 b < a 为假。
     • 传递性：如果 a < b 且 b < c 为真，那么 a < c 也为真。
     • 自反性：a < a 为假。
   • 这种严格弱序性质确保了红黑树结构的正确性，进而保证了元素的唯一性。

自定义类型放入set需满足的条件

1. 重载比较运算符：
   • 如果自定义类型要放入 std::set 中，必须提供一个满足严格弱序的比较函数。最常见的方式是重载 < 运算符。
   • 例如：

class MyClass {
public:
    int value;
    MyClass(int v) : value(v) {}
    bool operator<(const MyClass& other) const {
        return value < other.value;
    }
};

• 这样，MyClass 类型的对象就可以放入 std::set 中，并且 std::set 能够根据 operator< 来正确判断元素的唯一性。

2. 自定义比较函数对象：
   • 除了重载 < 运算符，也可以定义一个自定义的比较函数对象，并将其作为模板参数传递给 std::set。
   • 例如：

class MyComparator {
public:
    bool operator()(const MyClass& a, const MyClass& b) const {
        return a.value < b.value;
    }
};

std::set<MyClass, MyComparator> mySet;

• 这里，MyComparator 是一个函数对象，std::set 会使用它来比较 MyClass 对象，以确保元素的唯一性。