Why does std::set::contains() call the spaceship operator twice on a target element?

Question

Consider:

#include <print>
#include <set>

struct Num {
    auto operator <=> (const Num& other) const{
        std::println ("{} <=> {}", val, other.val);
        return val <=> other.val;
    };
    int val;
};

int main() {
    std::set<Num> s{{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
    std::println("------------");
    return !s.contains({8});
}

For the part that calls contains this prints out (among other things):

...
8 <=> 8
7 <=> 8
8 <=> 8

I would expect that after calling the spaceship operator with arguments (8,8), the set would know it found the element and can return true immediately.

Is this just because std::set in implementations I checked (libc++ and libstdc++) was never updated to move from using logic written for operator <, or is there a more fundamental reason for this? Is this still faster than all the time checking if compared elements are equal (since that happens at most once during lookup and moves the logic from handling two outcomes to handling three outcomes)?

Answer 1

std::set bases its ordering of the contents on a template parameter. And the ordering functor doesn't test equality; it only says if one item is "less than" another. As such, set considers two objects to be equivalent if the ordering functor returns false for comp(A, B) and comp(B, A) (neither is "less than" the other).

So even if operator<=> is being called, set doesn't know that. All it sees is the ordering; it has to manufacture equivalence.