c++ - 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.