How does STL map know, that map contains a given element?

Question

In question Using char as key in stdmap there is advised to use custom compare function/functor:

struct cmp_str
{
   bool operator()(char const *a, char const *b)
   {
      return std::strcmp(a, b) < 0;
   }
};

map<char *, int, cmp_str> BlahBlah;

This allows map to detect if key A is less than key B. But for example map<>::find() returns end if element is not found, and iterator to it if it is found. So map knows about equivalence, not only less-than. How?

juanchopanza · Accepted Answer · 2012-09-08T17:53:28.650

The equality condition for two keys a and b are that a<b and b<a are both false. The map itself is commonly implemented as a balanced binary tree^*, so the less-than comparison is used to traverse the map from the root node until the matching element is found. When searching for a key k, less-than comparison is used until the first element for which the comparison is false is found. If the inverse comparison is also false, k has been found. Otherwise, k is not in the map. The map only uses the less-than comparison to this purpose.

Note also that std::set uses exactly the same mechanism, the only difference being that each element is it's own key.

^* strictly speaking, the C++ standard does not specify that std::map be a balanced binary tree, but the complexity constraints it places on operations such as insertion and look-up mean that implementations chose structures such as red-black tree.

@LokiAstari that is what I said on the footnote. – juanchopanza Sep 08 '12 at 17:52 — juanchopanza, Sep 08 '12 at 17:52

score 3 · Answer 2 · answered Sep 08 '12 at 14:44

3

Equivalence/operator== can be expressed as a function of operator<:

bool operator==(T left, T right) {
  return !(left < right) && !(right < left);
}

answered Sep 08 '12 at 14:44

JoeG

12,994
1
38
63

True, although `std::map` does not require the equality operator, only a less-than comparison. – juanchopanza Sep 08 '12 at 14:47
@juanchopanza: Yes because you can get equality from less. The point is you still need an equality test even if it is not explicit. You can get the quality test because the requirements for `<` is a strict weak ordering thus guaranteeing that you can do equivalence testing using the above algorithm. – Martin York Sep 08 '12 at 17:49

score 3 · Answer 3 · answered Sep 08 '12 at 15:00

This is because the comparator of the map must implement a strict weak ordering, such as <.

One of the mathematical properties of such a relation is Antisymmetry, which states that for any x and y, then not (x < y) and not (y < x) implies x == y.

Therefore, after finding the first element not to compare smaller than the key you are searching for, the implementation simply checks if that element compares greater, and it's neither smaller nor greater, then it must be equal.

How does STL map know, that map contains a given element?

3 Answers3

Linked