When are two elements of an STL set considered identical?

Question

From cplusplus.com:

template < class Key, class Compare = less<Key>,
       class Allocator = allocator<Key> > class set;

"Compare: Comparison class: A class that takes two arguments of the same type as the container elements and returns a bool. The expression comp(a,b), where comp is an object of this comparison class and a and b are elements of the container, shall return true if a is to be placed at an earlier position than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function (see constructor for an example). This defaults to less, which returns the same as applying the less-than operator (a<b). The set object uses this expression to determine the position of the elements in the container. All elements in a set container are ordered following this rule at all times."

Given that the comparison class is used to decide which of the two objects is "smaller" or "less", how does the class check whether two elements are equal (e.g. to prevent insertion of the same element twice)?

I can imagine two approaches here: one would be calling (a == b) in the background, but not providing the option to override this comparison (as with the default less<Key>)doesn't seem too STL-ish to me. The other would be the assumption that (a == b) == !(a < b) && !(b < a) ; that is, two elements are considered equal if neither is "less" than the other, but somehow this doesn't feel right to me either, considering that the comparison can be an arbitrarily complex bool functor between objects of an arbitrarily complex class.

So how is it really done?

Answer 1

Your second option is the right one. Why doesn't feel it right? What would you do if the equality test wasn't consistent with the equation you give?

Answer 2

Not an exact duplicate, but the first answer here answers your question

Your second guess as to the behaviour is correct

Answer 3

Associative containers in the standard library are defined in terms of equivalence of keys, not equality per se.

As not all set and map instances use less, but may use a generic comparison operator it's necessary to define equivalence in terms of this one comparison function rather then attempting to introduce a separate equality concept.

In general, two keys (k1 and k2) in an associative container using a comparison function comp are equivalent if and only if:

comp( k1, k2 ) == false && comp( k2, k1 ) == false

In a container using std::less for types that don't have a specific std::less specialization, this means the same as:

!(k1 < k2) && !(k2 < k1)

Answer 4

Your mistake is the assumption that "the comparison can be an arbitrarily complex bool functor". It can't.

std::set requires a partial ordering so that a<b implies !(b<a). This excludes most binary boolean functors. Because of that, we can talk about the relative position of a and b in that ordering. If a<b, a precedes b. If b<a , b precedes a. If neither a<b nor b<a, then a and b occupy the same position in the ordering and thus are equivalent.