CODEWITHSUNDEEP
c++c++11
Ashutosh
Ashutosh

Reputation: 131

Understanding std::map::find

I am trying to learn how to use std::map with functions. I am a bit confused about how std::map::find works in this regard. Here is a simple code where I use a Lambda function along with map.

auto Lambda = [](const int&a, const int& b) {
 cout << "\n Inside lambda \n";
 return a < b;
 };

std::map<int, int, decltype(Lambda)> expt(Lambda);
expt[1] = 2;
expt[10] = 12;
auto search1 = expt.find(1);
auto search10 = expt.find(10);
if(search1 != expt.end()) {
    std::cout << "Found " << search1->first << " " << search1->second << '\n';
}
else {
    std::cout << "Not found\n";
}

Here is the output that I get:

Inside lambda
Inside lambda
Inside lambda
Inside lambda
Inside lambda
Inside lambda
Inside lambda
Found 1 2

I am a bit confused about how find actually works in this case. Why do I get 7 calls of the lambda function even though I just have 2 keys in my map?

Upvotes: 7

Views: 430

Answers (2)

K. Kirsz
K. Kirsz

Reputation: 1420

Let me try to tackle this:

The point here is: you provide the definition of '<' operation only in map constructor. Map needs to perofrm the '<=' operation and it apparently does it like this:

bool le(left, rigth){
  return (left<right) and not (rigth<left);
}

so it it is sometimes enough to do just one <, and sometimes 2 are required for a single operation on map.

  1. The first 2 comparisons are caused by the insertion operation. The map algorithm has to decide if the new element is <= the existing one. It performs 2 < comparisons in order to find out (new<old and old>new). (Notice that if you insert 10 first, and then 1, you will only get one comparison, since the first of them new<old would yield the unambigous result (true)).
  2. The first find executes the lambda 2 times for the same reason. The first check < returns false, so it needs to do the second one, with the swapped arguments to learn if the values are equal or not.
  3. Once again, same story...

Upvotes: 2

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

operator < cannot tell you that two things are equal in one go. You need to call both x < y and y < x in order to verify that x == y. So each time map actually finds a key, it compares the argument and the found key twice, once normally and once swapped around.

This accounts for double occurrence of lambda(1,1) and lambda(10,10).

As for lambda(10,1) and lambda(1,10) when inserting an element with the key of 10, this is needed because map may have to call comparison twice also when it fails to find a key (swap order of insertions to see that).

Upvotes: 5

Related Questions