Why are there three comparisons to add a second map element?

user_3880254 0
Viewed 65

When I run the following code (with a line commented out) I get no output (no comparisons are made). But the moment I uncomment the last line I get three lines of output (three comparisons are made). When a second item is added, 1-2 comparisons is understandable, but why a third?

#include <map>
#include <iostream>

using namespace std;

class MyType
{
  public :
  int a;
  MyType():a(0){}
};

bool operator<(const MyType &lhs, const MyType &rhs)
{
  cout<<"operator < is called\n";
  return lhs.a < rhs.a;
}

int main()
{
  MyType T1,T2;
  T1.a = 100;
  T2.a = 33; 
  
  map<MyType,int> Test;

  Test[T1] = 10; 
  //Test[T2] = 20; --> #Uncomment this line for getting 3 lines of "operator < is called"

}

The output with the line uncommented:

operator < is called
operator < is called
operator < is called

How did it end up in printing three strings from zero with just one extra key got added?

MyCodeOnline

Here are the addresses of lhs and rhs:

0x56365ea45e90
0x7ffe3c4cd47c
operator < is called
0x7ffe3c4cd47c
0x56365ea45e90
operator < is called
0x56365ea462d0
0x56365ea45e90
operator < is called
stdmap insert c++
2 Answers

In a visual studio debug build it generates a lot of extra code in the standard library to catch various bugs.

In the case of std::map after inserting a new value it checks that the comparator correctly returns false for comp(key, key) and therefore implements the required strict weak ordering.

If you switch to a release build there are only 2 comparisons as you'd expect.

I presume what's happening in libstdc++ is that Test[T2] = 20 has to perform four operations:

  1. Check whether T2 already exists
  2. Insert a new element for T2
  3. Return a reference to the new element
  4. Assign the value of the new element to 20

I'm guessing libstdc++ hasn't optimised step 1 and 2 to reuse the comparisons. If you use insert to insert elements into the map only 2 comparisons are performed (this should be more efficient in all standard libraries even if they manage to not generate extra calls to the comparator):

Test.insert(std::make_pair(T2, 20));
user_54943700

I'm basing this answer on the libstdc++ gcc implementation of a map which uses a RB tree as the underlying storage.

When using operator[] to insert in to a map, it will do two things: First, it will see if it can find the existing element in the map and secondly will add/update the element to the new value.

  1. The find operation is the first use of operator<

  2. The next use is when inserting in to the underlying RB tree. Again, the first operation is to check to see whether the new node value is equal to the node already in the tree.

  3. The second operation, is then where to place the new node relative to the previous node.

This is in contrast to the map emplace or insert operations, which will not do the find operation and will skip straight to inserting the node in to the underlying tree.

user_58276900
Related