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

Question

说我有

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

Find 使用类中的 == 运算符是否正确？

我的参考文献还说它有 log(n) 最坏情况运行时间，其中 n 是集合中元素的数量。这在内部是如何实现的呢？我知道关键是集合中的元素有一个顺序（因此插入需要很长时间才能创建该顺序），对于整数集，顺序意味着什么很清楚，但对于随机类则不然。

Answer 1

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

\n\n

\n

3 短语\xe2\x80\x9cekeys\xe2\x80\x9d 的等价性表示由比较强加的等价关系，而不是keys 上的操作符==。也就是说，如果对于比较对象 comp，comp(k1, k2) == false && comp(k2, k1) == false，则两个键 k1 和 k2 被认为是等效的。对于同一容器中的任意两个键 k1 和 k2，调用 comp(k1, k2) 应始终返回相同的值。

\n

\n\n

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

\n\n

如果您没有显式指定比较对象，则该类默认使用在其运算符函数中std::less使用的标准函数对象operator <。所以你的类必须定义运算符<。

\n\n

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

\n