1

When trying to find out why my program was buggy, I found that:

In a std::map, the keys are compared using the less-than operator < when performing a search.

(from std::map find not working in C++).

Does anybody know why the map uses the < operator and not the == operator when performing a search?

GSerg
  • 76,472
  • 17
  • 159
  • 346
GtN
  • 57
  • 4
  • 4
    Because a search with `<` is logarithmic, but a search with `==` would be linear. The whole point of `std::map` is its `O(log N)` access complexity. – Igor Tandetnik Apr 26 '20 at 14:09
  • 1
    Have you ever played that guessing game, pick a number from 1 to 100? Your first question is going to be, is your number less than 50, not is your number equal to 50. – john Apr 26 '20 at 14:13

2 Answers2

1

Because std::map is sorted, you can take advantage of the fact that all elements that are less than x are located before x, and all elements that are greater are located after x. This means that you can do binary search to find an element, which is much more effective than linear search (i.e. just looking through each element in sequence).

For instance, effectively looking for the number 55 in a colletion could look something like this:

 1 1 2 3 5 8 13 21 34 55 89 144
[          ^                   ]  8 is too low

 1 1 2 3 5 8 13 21 34 55 89 144
            [      ^           ]  34 is too low

 1 1 2 3 5 8 13 21 34 55 89 144
                     [   ^     ]  89 is too high

 1 1 2 3 5 8 13 21 34 55 89 144
                     [^ ]         55 is a match!

This has complexity O(log n), while just comparing with == has complexity O(n). In other words, finding an element in a map of a million elements needs only around log2(106) &approx; 20 comparisons, while if we were comparing with == it would need around 106 comparisons, a huge difference for large collections.

Frxstrem
  • 38,761
  • 9
  • 79
  • 119
0

The thing which puzzles you most may be this statement in the link you refered to:

I have created a hash map

However, this is incorrect. std::map is a tree map which is typically implemented by red-black tree.

Now your question basically turns to a data structure problem.

red-black tree is a kind of binary search tree, every node in which has the following properties:

  • the left son of the node is less than the current node
  • the right son of the node is greater than the current node

Note that I used "less" or "greater" only to let you understand. More pricisely, given a binary predicate p used to organize the tree which satisfys the requirements of strict weak ordering, we assume the current node is N, then:

  • p(N, N->left) is true
  • p(N, N->right) is false

So now you are at the top of the tree, to find the correct node, you need to keep comparing the value you have with the current node and decide which direction you should go.

And you may ask why == is not necessary, that's because when a predicate p satisfys the requirement of strict weak ordering, the following two expressions are equivalent(Not precise, but at lease the part we concerned about is equivalent):

A. !(p(A, B) || p(B, A))

B. A == B

you can ask yourself, when A is not less than B and B is not less than A, what's the relationship between A and B?

con ko
  • 1,368
  • 5
  • 18