36

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?

R Sahu
  • 204,454
  • 14
  • 159
  • 270
  • 1
    Doesnt `std::set` and `std::map` are RB-Trees under the hood? – Sebastian Hoffmann Mar 10 '14 at 18:38
  • 2
    But this will mean having to overload the `-` operator for any data type that wishes to use the map or set – smac89 Mar 10 '14 at 19:31
  • @Smac89, that is true. What's also true is that you have to implement `operator<` now. – R Sahu Mar 10 '14 at 19:36
  • @Paranaix I think it's technically an implementation detail. But if you go down to the bottom of the standard specs, you'll probably find it hard to come up with another implementation that still satisfies the performance constraints that the standard ***does*** specify. – sehe Mar 10 '14 at 19:38
  • @Paranaix, the standard doesn't mandate any particular structure, just performance guarantees. – vonbrand Mar 10 '14 at 20:22
  • @RSahu Your proposed `compare` could overflow for signed types, leading to undefined behavior. However, a `compare` could be implemented with `less` via `less(b, a) - less(a, b)`. – jxh Oct 21 '19 at 19:31
  • @jxh, definitely. The accepted answer has a link to such a post. – R Sahu Oct 21 '19 at 19:44

2 Answers2

25

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.

Community
  • 1
  • 1
Jo So
  • 25,005
  • 6
  • 42
  • 59
  • *Originally, I proposed 3-way comparisons.* It's not clear from your post whether he wanted them as a generic functor or he wanted to use them in the implementation of `std::map` and `std::set`. – R Sahu May 04 '17 at 04:25
  • 6
    Oh. This is pretty nice. The horse's mouth. Can't argue with that :) Love this answer – sehe May 04 '17 at 08:12
  • @RSahu: Do you mean: whether he thinks that 3-way comparisons are useful specifically in trees? Whether it's better to actually test equality at each node since it's cheap with 3-way and enables us to return early? He didn't respond to that specifically. – Jo So May 04 '17 at 14:34
  • @RSahu: But actually I think the ability to visit 2-ish nodes less in a search for a node that *is* in the tree, for real world RB trees of depth ~20, is worthwhile. Because it saves 2 cache misses. I haven't benchmarked it yet, though. – Jo So May 04 '17 at 14:35
  • ... And when I asked him I was still of the misconception that with the C++ interface we had to make *twice* as many comparisons. But it's only a constant number of additional comparisons. So that might be the reason why he didn't lose many words on that. – Jo So May 04 '17 at 14:40
  • @JoSo, I was wondering whether he thought the 3-way comparison functors would have been better in trees. – R Sahu May 04 '17 at 15:01
  • @RSahu Ok - so as explained, I assume 3-way is better in trees. And actually *specifically* in trees. In binary searches over flat arrays I'd expect 3-way to not typically save cache misses since "leaves" are adjacent. Someone said that the 2-way binary search code here is adapted from Knuth, Volume 3a: http://en.cppreference.com/w/cpp/algorithm/lower_bound – Jo So May 04 '17 at 15:19
  • 3
    looks like 3-way compare is coming to c++, in the form of `operator<=>`, see http://open-std.org/JTC1/SC22/WG21/docs/papers/2017/p0515r0.pdf – sp2danny Aug 23 '17 at 09:35
17

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)

sehe
  • 374,641
  • 47
  • 450
  • 633
  • A comparison function that returns `< 0`, `== 0` or `> 0` is implementable for *any* comparison function `less`, simply by returning `0` if `!less(a, b) && !less(b, a)`. It would be *exactly* as expressive, there are no types that can have a usable `less` function but not a usable `compare` function. –  Mar 10 '14 at 19:44
  • @hvd That's a tautology. However, in practice, `operator=` is usually used to express _equality_ semantics, not _equivalence_. It would be very surprising to mix the two. Not all types with a total ordering necessarily have equality implemented. – sehe Mar 10 '14 at 19:48
  • Yes, you're right, I had already edited my previous comment to remove my reference to `operator==`. But functions that compare two items and return negative, zero, or positive depending on the comparison result are already commonly used, where zero doesn't imply equality. A very common example is a case-insensitive string comparison. –  Mar 10 '14 at 19:51
  • Good point, @hvd. You're right. That's a `Comparable` concept, which is has more requirements than `LessThanComparable` – sehe Mar 10 '14 at 20:02
  • @sehe, I believe you mean `operator==` – vonbrand Mar 10 '14 at 20:23
  • @sehe, I think the question is not conclusively answered. I appreciate your point about equivalence vs equality, but these are only a matter of a standpoint and formalism. Equality *is always* an equivalence, and conversely an equivalence can be equality in a context where two objects are equivalent for all that currently matters. – Jo So May 03 '17 at 13:47
  • @sehe, ... the question was really: To detect *equivalence* using `std::less`, we might have to call `std::less(a,b)` first and then `std::less(b,a)`, which is inefficient, for example when comparing two strings that only differ in the last character. Right? – Jo So May 03 '17 at 13:50
  • @sehe, More specifically, is the interface of `std::set` (which is parameterized by a `less` boolean function less efficient than it must be, by requiring a tree search to call `less` twice at each node if `less` doesn't return true immediately? – Jo So May 03 '17 at 13:53
  • @JoSo no. First of all, ordered containers do not care about equality at all, they are only ordered. Second, all these objections reason outside compiler optimization. E.g. [for int](http://paste.ubuntu.com/24505757/), we get [no runtime difference](http://stackoverflow-sehe.s3.amazonaws.com/2e567a43-4a89-414a-9527-96511d78ba2c/stats.html) - unsurprisingly looking at the assembly https://godbolt.org/g/yUt0J0 – sehe May 03 '17 at 15:26
  • Though I guess it is technically possible to get better performance using targeted equality functions. These are - not coincidentally - used for non-ordered containers. Compare with std::string: https://godbolt.org/g/PEX6EA the equality test is considerably simpler. That doesn't mean it's necessarily [that much slower](http://stackoverflow-sehe.s3.amazonaws.com/c609f406-4b3a-44f3-bb05-f99e6da2a7dc/stats.html): [source code](http://paste.ubuntu.com/24505807/). Also, that doesn't make using tree operations slower, because they naturally work on (strict) weak total ordering. – sehe May 03 '17 at 15:38
  • @sehe, it makes no difference if you call it equality or equivalence. You can't put the integer 3 in a set more than once, so the set has to have a way to recognize if it's already there. Similarly, if you have a set containing only 3 and you insert x, the implementation might check if x < 3 (which would mean that x has to be left child of 3 in the tree). When that evaluates to false, it still doesn't know whether 3 < x (x has to right child) or not (no insertion). I don't see how there could possibly be a away to avoid that second test. – Jo So May 03 '17 at 16:13
  • Also, that assembly output is of no help given the obfuscation of the C++ input. It doesn't show anything. I agree that it's not much slower on random strings, since typically only the first character of each string has to be compared (unless they're equal), so function call overhead dominates. – Jo So May 03 '17 at 16:20
  • Test it with longer strings which are only different in the last character. – Jo So May 03 '17 at 16:21
  • There is ZERO obfuscation. If anything, the lack of premature optimization shows that the compiler has no problem seeing through those after inlining. – sehe May 03 '17 at 16:21
  • I didn't focus on naming. The points I made are that 1. the relative comparisons are logically dominant in ordered node-based containers (it's not fair to zoom in on the last comparison only, when the tree might have a depth of _n_ levels). 2. The "extra" cost of the "extra" call is easily overestimated (I hope you looked at the exemplary benchmarks and disassemblies). These are hard facts. You can construct scenarios where the difference is non-negligable, but the design of a _standard_ library doesn't necessarily focus on these cases. – sehe May 03 '17 at 16:22
  • I'm out. I'm not here to debate things without proof or relevant use cases. – sehe May 03 '17 at 16:22
  • @sehe, I did not intend to make you angry. I had the misconception that each node on the way down must be compared twice. But it's only a few more comparisons at the bottom. (My criticism of your benchmark still holds). – Jo So May 04 '17 at 03:25
  • Anyway, you might want to check my answer, I have interesting new stuff there. – Jo So May 04 '17 at 03:26
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/143366/discussion-between-sehe-and-jo-so). – sehe May 04 '17 at 08:09