Why C++ STL containers use "less than" operator< and not "equal equal" operator== as comparator?

Question

While implementing a comparator operator inside a custom class for std::map, I came across this question and couldn't see anywhere being asked.

Apart from the above question, also interested to know in brief, how operator< would work for std::map.

Origin of the question:

struct Address {
  long m_IPv4Address;
  bool isTCP;
  bool operator< (const Address&) const;  // trouble
};

Answer 1

std::map<K,D> needs to be able to sort. By default is uses std::less<K>, which for non-pointers uses <¹.

Using the rule that you demand the least you can from your users, it synthesizes "equivalence" from < when it needs it (!(a<b) && !(b<a) means a and b are equivalent, ie, neither is less than the other).

This makes it easier to write classes to use as key components for a map, which seems like a good idea.

There are std containers that use == such as std::unordered_map, which uses std::hash and ==. Again, they are designed so that they require the least from their users -- you don't need full ordering for unordered_ containers, just equivalence and a good hash.

As it happens, it is really easy to write a < if you have access to <tuple>.

struct Address {
  long m_IPv4Address;
  bool isTCP;
  bool operator< (const Address& o) const {
    return
      std::tie( m_IPv4Address, isTCP )
      < std::tie( o.m_IPv4Address, o.isTCP );
  }
};

which uses std::tie defined in <tuple> to generate a proper < for you. std::tie takes a bunch of data, and generates a tuple of references, which has a good < already defined.

---

¹ For pointers, it uses some comparison that is compatible with < where < behaviour is specified, and behaves well when < does not. This only really matters on segmented memory model and other obscure architectures.

Answer 2

Because std::map is a sorted associative container, it's keys need ordering.

An == operator would not allow to order multiple keys

You might be looking for std::unordered_map , which work has a hashtable. You can specify your own hash and equality operator functions :

explicit unordered_map( size_type bucket_count,
                    const Hash& hash = Hash(),
                    const KeyEqual& equal = KeyEqual(),
                    const Allocator& alloc = Allocator() );

Answer 3

With < you can order elements. If a < b then a should be placed before b in the collection.

You can also determine if two items are equivalent: if !(a < b) && !(b < a) (if neither object is smaller than the other), then they're equivalent.

Those two capabilities are all std::map requires. So it just expects its element type to provide an operator <.

With == you could determine equality, but you wouldn't be able to order elements. So it wouldn't satisfy the requirements of std::map.