13

The unordered associative containers unordered_set, unordered_map etc do not have a less than operator operator<, neither as a member function nor as a free function. Why? There is no specialization of less either. SGI STL's hash_* types also lack this feature.

If we exclude the concept of underlying types, all container types fulfil the requirements of regular types as defined e.g. in Stepanov & McJones' Elements of Programming. The sole exception are the unordered associative types, which lack operator<.

I could not come up with an efficient implementation of such an operator that is consistent with the given definition of equality, so might efficiency be the reason? On the other hand, operator== for unordered associative containers in some cases needs to rehash every element of one container and look it up in the other - O(N) average, but worst case O(N²).

Brendan Long
  • 53,280
  • 21
  • 146
  • 188
dyp
  • 38,334
  • 13
  • 112
  • 177
  • Related: [C++11: Are there reasons why some Regular Types should not have `std::hash` specialised?](http://stackoverflow.com/q/29969322/) – dyp May 18 '15 at 00:32
  • In EoP, `operator+` is also defined between iterators and integers for which it is not an O(1) operation. Additionally, [Notes on Programming](http://stepanovpapers.com/notes.pdf) contains a remark on page 28 that suggests that efficiency should not be the reason. – dyp May 18 '15 at 00:36
  • 4
    If the elements of the container are conceptually `unordered` how can you meaningfully compare two such containers to determine which should be less than the other? – Galik May 18 '15 at 00:40
  • I mean if the characters in a string were conceptually `unordered` how would you compare two such strings? – Galik May 18 '15 at 00:41
  • @Galik A possible implementation of `operator<` for unordered containers is to copy both containers, sort the copies and then lexicographically compare the sorted ranges. It's O(NlogN) average, and consistent with `operator==`. As far as I can tell, Stepanov thinks that having a ("default") total ordering is important even if there is no conceptual relation to the values of the objects that are compared. See NoP on page 28 about comparing list iterators. In EoP p. 62, there's the example of complex numbers. – dyp May 18 '15 at 00:47
  • What problem are you trying to solve? What particular feature are you missing because of the lack of regularity? Which piece of code would be improved and which real-world problem would be solved if unordered containers were regular? – Kerrek SB May 18 '15 at 00:53
  • All of dyp's codebase are belong to `std::set>` – Barry May 18 '15 at 00:57
  • Ok, I see what you're saying. This is possibly too big a discussion for SO maybe. But conceptually the ordering is imposed by the container type, so comparing `unordered` containers, in terms of a different container, may impose limits on what can and can not be contained in an `unordered` container. (now I'll go read those notes you linked) – Galik May 18 '15 at 00:58
  • I don't get the primary opinion based close vote, Howard's answer shows it is not a matter of opinion. – Shafik Yaghmour May 18 '15 at 01:16
  • 1
    @KerrekSB I just want to store my set of `TelephoneBooks` digitally ;) -- Actually, it came up [in a discussion about why `operator<` is a free function](http://stackoverflow.com/questions/30265627/why-standard-containers-use-function-templates-instead-of-non-template-koenig-op/30268237?noredirect=1#comment48639088_30268237). – dyp May 18 '15 at 01:34
  • Who are Stepanov and McJones, and why do they get to decide what's a type and what isn't? – user253751 May 18 '15 at 05:32
  • 1
    @immibis: Because every culture craves someone to worship and follow. Writing a book, or [two](http://www.amazon.co.uk/Mathematics-Generic-Programming-Alexander-Stepanov/dp/0321942043), makes you a prime candidate for that. :-) – Kerrek SB May 18 '15 at 08:40
  • @immibis Alexander Stepanov is the main architect of the STL, which is the foundation of the C++ Standard Library container classes. He was also involved in the [definition of the concept of *regular types*](http://www.stepanovpapers.com/DeSt98.pdf). (It's not about "what's a type and what isn't"; *regularity* is a property of a type.) – dyp May 18 '15 at 12:42

1 Answers1

28

Conceptually it doesn't make a lot of sense. Consider a bag of different colored marbles. And lets say you have two bags of marbles:

  1. Contains red, blue, green.
  2. Contains purple, red, yellow.

Is bag 1 < bag 2?

Even if you associate an order to the colors, say:

red < yellow < purple < blue < green

It is still difficult to say if one bag is less than than the other because internally the bag associates no order to the marbles. That is bag 1 could be output in any of 6 formats, which are all equivalent:

  1. red, blue, green
  2. red, green, blue
  3. blue, red, green
  4. blue, green, red
  5. green, red, blue
  6. green, blue, red

None of the above six are less than any of the other. Indeed, they are all equal, no matter whether red < blue or blue < red. A bag is not a sequence ... it is an unordered sequence.

Historically the unordered containers also did not have equality operators. However it does make sense to ask if one bag contains the same colored marbles as another bag. And here the issue is one of efficiency. Eventually algorithms and proposals were presented to sway the committee to add equality comparisons for the unordered containers:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
  • So the committee doesn't follow Stepanov's (new?) idea that types that do not have a "natural total ordering" should at least have a "default total ordering"? What about pointers then? (Or maybe I'm confused because Regular originally didn't require LessThanComparable?) – dyp May 18 '15 at 01:32
  • 4
    No, the committee has never said that all types should have a default total ordering. This history goes back all the way to C++98 (the first C++ standard). `std::complex` has no total ordering. – Howard Hinnant May 18 '15 at 01:34
  • Note that if someone insists on doing comparisons between hash containers `L` and `R` which have the same `Key` and `Hash`, [one can use](http://stackoverflow.com/a/21688822/819272) `std::lexicographical_compare(begin(L), end(L), begin(R), end(R), [](auto const& kL, auto const& kR) { return Hash()(kL) < Hash()(kR); });` to order them based on their hash indices. – TemplateRex May 21 '15 at 06:58
  • @TemplateRex: Very true. Also note that if one does that, it likely won't be consistent with the container's `operator==`. For example with two containers with an identity hash and number of buckets greater than 2, `{1, 2, 3}` will compare less than `{3, 2, 1}` with your algorithm, and these two containers will also compare equal to each other according to `operator==` for the unordered containers. Working example: http://melpon.org/wandbox/permlink/nTFuLjB8z69KI58w – Howard Hinnant May 21 '15 at 14:40
  • hm, the identity hash is a bit degenerate, but I get your point. Any hard hash collision will break the consistency between equality and less. I had tested it with only small samples and nice hashes, and underestimed the deviousness that hardcore library writers should anticipate :) – TemplateRex May 21 '15 at 18:52