std::set<classtype>.find(element) 是否使用 class 中的 == 运算符来比较元素？

Question

说我有

std::set<classtype> set;
class classtype {
    bool operator==(const classtype& ct) {
        //..
    } 
};
//..
std::set<classtype>::iterator it = set.find(element);

查找确实使用了 class 中的 == 运算符，正确吗？

我的参考资料还说它有 log(n) 最坏情况运行时，其中 n 是集合中的元素数。这在内部是如何实现的？我知道关键是集合中的元素有一个顺序（因此插入需要很长时间才能创建该顺序），对于整数集来说，顺序的含义很清楚，但对于随机 classes 不是那么多。

Answer 1

来自 C++ 标准（23.2.4 关联容器）

3 The phrase “equivalence of keys” means the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false. For any two keys k1 and k2 in the same container, calling comp(k1, k2) shall always return the same value.

成员函数find根据比较对象求keycomp

如果您没有明确指定比较对象，则 class 默认使用标准函数对象 std::less，后者在其运算符函数中使用 operator <。因此，您的 class 必须定义运算符 <。

如果您想使用 operator == 作为集合中的比较值，那么您可以使用标准算法 std::find 而不是方法 find.

std::set<classtype>.find(element) 是否使用 class 中的 == 运算符来比较元素？

Does std::set<classtype>.find(element) use the == operator from the class to compare the elements?

c++

time-complexity

stdset