Why use std::less as the default functor to compare keys in std::map and std::set?

Question

I am wondering why std::map and std::set use std::less as the default functor to compare keys. Why not use a functor that works similar to strcmp? Something like:

  template <typename T> struct compare
  {
     // Return less than 0 if lhs < rhs
     // Return 0 if lhs == rhs
     // Return greater than 0 if lhs > rhs
     int operator()(T const& lhs, T const& rhs)
     {
        return (lhs-rhs);
     }
  }

Say a map has two object in it, with keys key1 and key2. Now we want to insert another object with key key3.

When using std::less, the insert function needs to first call std::less::operator() with key1 and key3. Assume std::less::operator()(key1, key3) returns false. It has to call std::less::operator() again with the keys switched, std::less::operator()(key3, key1), to decide whether key1 is equal to key3 or key3 is greater than key1. There are two calls to std::less::operator() to make a decision if the first call returns false.

Had std::map::insert used compare, there would be sufficient information to make the right decision using just one call.

Depending on the type of the key in map, std::less::operator()(key1, key2) could be expensive.

Unless I am missing something very basic, shouldn't std::map and std::set use something like compare instead of std::less as the default functor to compare keys?

Answer 1

I decided to ask Alexander Stepanov (designer of the STL) about this. I'm allowed to quote him as follows:

Originally, I proposed 3-way comparisons. The standard committee asked me to change to standard comparison operators. I did what I was told. I have been advocating adding 3-way components to the standard for over 20 years.

But note that perhaps unintuitively, 2-way is not a huge overhead. You don't have to make twice as many comparisons. It's only one comparison per node on the way down (no equality check). The cost is not being able to return early (when the key is in a non-leaf) and one extra comparison at the end (swapping the arguments to check equality). If I'm not mistaken, that makes

1 + 1/2*1 + 1/4*2 + 1/8*3 + ...
= 1 + 1/2+1/4+1/8+... + 1/4+1/8+... + ...
-> 3  (depth -> infty)

extra comparisons on average on a balanced tree that contains the queried element.

On the other hand, 3-way comparison doesn't have terrible overhead: Branchless 3-way integer comparison. Now whether an extra branch to check the comparison result against 0 (equality) at each node is less overhead than paying ~3 extra comparisons at the end is another question. Probably doesn't matter much. But I think the comparison itself should have been 3-valued, so that the decision whether to use all 3 outcomes could be changed.

Update: See comments below for why I think that 3-way comparison is better in trees, but not necessarily in flat arrays.

Answer 2

Tree based containers only require Strict Weak Total Ordering.

See https://www.sgi.com/tech/stl/StrictWeakOrdering.html

1. write access

   The insertion point for maps and sets is purely determined by a single binary search, e.g. lower_bound or upper_bound. The runtime complexity of binary search is O(log n)

2. read access

   The same applies to searching: the search is vastly more efficient than a linear equality scan, precisely because most elements do not need to be compared. The trick is that the containers are ordered.

---

The upshot is that the equality information need not be present. Just, that items can have equivalent ordering.

In practice this just just means fewer constraints on your element types, less work to implement the requirements and optimal performance in common usage scenarios. There will always be trade-offs. (E.g. for large collections, hash-tables (unordered sets and maps) are often more efficient. Note that these do require equatable elements, and they employ a hashing scheme for fast lookup)