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

Question

Say I have

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

Find does use the == operator from the class correct?

Also my reference says it has log(n) worst case runtime where n is the number of elements in the set. How is this realized internally? I understand that the key is that the elements in the set have a order (so insertion takes long to create that order), for integer sets it is clear what order means but for random classes not so much.

Answer 1

From the C++ Standard (23.2.4 Associative containers)

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.

Member function find seeks a key according to the comparison object comp

If you did not specify explicitly the comparison object then the class uses by default standard functional object std::less that uses operator < within its operator function. So your class has to have the operator < defined.

If you want to use operator == for comparison values in the set then you can use standard algorithm std::find instead of the method find.