What happened when call std::map's operator[] or insert

Question

I have following code:

#include <functional>   // std::less
#include <map>
#include <iostream>
using namespace std;

class Key
{
public:
        Key() {cout << "Key Constructor" << endl;}
        ~Key() {cout << "Key Destructor" << endl;}
        Key(const Key& key) {cout << "Key Copy Constructor" << endl;}

        bool operator < (const Key& k1) {return true;}
};
int main()
{
        map<Key, int> mymap;
        Key k;

        cout << "operator[]"<<endl;
        mymap[k] = 1;

        map<Key, int> mymap2;
        cout << "insert"<<endl;
        mymap2.insert(std::make_pair(k, 1));
        cout << "=========" << endl;

}

And the output is:

$ g++ test.cpp -fpermissive
$ ./a.out
Key Constructor
operator[]
Key Copy Constructor
Key Copy Constructor
Key Destructor
insert
Key Copy Constructor
Key Copy Constructor
Key Copy Constructor
Key Copy Constructor
Key Destructor
Key Destructor
Key Destructor
=========
Key Destructor
Key Destructor
Key Destructor

Could anyone please explain why mymap[k] = 1; invoke 2 copy constructor and mymap2.insert(std::make_pair(k, 1)); invokes 4 copy constructor? and does that mean operator[] is much more efficient than insert?

Thanks.

Summary:

Thanks user 6502 and petersohn for your insight, I now guess the reason for the 2 extra copy constructor for insert is as below:

• make_pair is a function, it make a copy inside function first, and then return the copy - that is one extra copy
• make_pair(k, 1) will create a pair<Key, int>, but the required value_type is pair<const& Key, int>, the type conversion will cause another extra copy

So in case 2, if I use:

mymap2.insert(std::pair<const Key, int>(k, 1));

The number of copy constructors get called will be the same with operator[]

As 6502 noted, following claim has been changed hence not true anymore:

A call to this function(operator[]) is equivalent to: (*((this->insert(make_pair(x,mapped_type()))).first)).second

operator[] is implemented different to avoid extra copy introduced by make_pair()

Answer 1

The problem with insert is that make_pair will create a pair of the wrong type so the passed object will need a conversion to a proper pair type to be passed to insert.

Actually in a former version the C++ standard mandated map::operator[] to behave as insert (thus forcing an inefficient implementation). Later the text was relaxed allowing a better implementation.

Note anyway that for standard containers the elements are considered to be "values", i.e. the implementation is free to copy things around and you get no guarantees about how many copies will be made.

You can see the make_pair problem by changing the code to

    mymap2.insert(std::pair<const Key, int>(k, 1));

Longer explanation

The problem is that make_pair will create an std::pair<Key, int> value but insert signature wants instead a const std::pair<const Key, int>& (note that std::map::value_type is a pair with a const first element).

These two types are incompatible and unrelated so to be able to make the call another pair must be created copying both key and value and this is where an extra key duplication occurs.

Even if it could be apparently "logical" that a pair<X, Y> should be directly usable where pair<const X, Y> is expected this is not true in C++ and it's one of the logical problems of the const-correctness concept (it doesn't scale by composition).

Answer 2

It's because of make_pair. You have to copy k into the pair, plus there is an extra function call. Possibly the number of copies can be reduced by enabling optimization (I didn't try). However, if you do this, then you'll have exactly the same number of copies than with operator[]:

mymap2.insert(std::pair<const Key&, int>(k, 1));

In C++11 though, things start to get better. If you compile your code with C++11, then you'll get two copies with insert. Even better, if Key has a move constructor, you'll get one copy and one move for insert (while two copies with operator[]). If you use my line above in C++11, you'll even spare the move and only get one copy.

Interestingly, with operator[], I always get two copies, for which I don't know the exact reason.