Spurious copies in c++03 libstdc++ vs c++11

Question

Consider this code:

#include <iostream>
#include <string>
#include <map>

using namespace std;

class Foo
{
public:
   Foo() : _x(0) 
   {
       cout << "Default" << endl;
   }
   Foo(int a) : _x(a)
   {
      cout << "Param" << endl;
   }

   Foo(Foo const &foo) :
      _x(foo._x)
   {
      cout << "Copy" << endl;
   }

   Foo& operator=(Foo const &foo)
   {
      cout << "Assignment" << endl;
      _x = foo._x;
      return *this;
   }

   int get(void)
   {
      return _x;
   }

private:
   int _x;
};

int main(int argc, char *argv [])
{
   std::map<int, Foo> foos;

   Foo a_foo(10);

   foos[100] = a_foo;

   return 0;
}

Compiled in gcc with -std=c++11 and you get the output,

Param
Default
Assignment

Remove -std=c++11, then you get,

Param
Default
Copy
Copy
Assignment

with c++11

without

libc++ example producing the superior output in c++03 mode

Where are the two extra copies coming from?

They are related to calling the subscript operator, not the assignment. (They remain if you remove the assignment.) To me they don't seem to be needed, even in a pre-C++11 world, as the libc++ example shows.

This was originally motivated by looking at this question

Answer 1

This is LWG 334:

The C++03 Standard mandates the following effects for operator[] ([lib.map.access]p1):

Returns: (*((insert(make_pair(x, T()))).first)).second.

---

libstdc++ implements the insertion used by operator[] (in the case where the key doesn't exist yet) as follows in C++03 mode:

 __i = insert(__i, value_type(__k, mapped_type()));

__i is the insertion point, it is computed as

iterator __i = lower_bound(__k);

__k is the parameter of operator[].

The creation of the temporary value_type(__k, mapped_type()) causes the first copy (from mapped_type() into the value_type pair). The second copy is the result of insert, which copies the value_type pair into an actual node.

The original version from 1997 is:

return (*((insert(value_type(k, T()))).first)).second;

which is almost to the letter of the Standard (which didn't even exist back then!). The last time it was changed significantly was in 1998. Prior to that, it used:

__i = insert(__i, value_type(__k, _Tp()));

The commit message says this was to

Update to SGI STL 3.11.

---

Earlier versions of the SGI STL (1995) did indeed specify map::operator[] in the same way as the C++03 Standard:

For a map m and key k, m[k] is semantically equivalent to (*((m.insert(make_pair(k, T()))).first)).second .

SGI STL v2.03 (1997) had already switched to using value_type instead of make_pair. And as gcc's commit log suggests, SGI STL's implementation changed again between v3.0 (also 1997) and v3.11 (1998) from insert(value_type(.. to the form still present in libstdc++ using lower_bound and only creating the pair if the key doesn't exist yet.

---

So one could say that libstdc++ implements the first proposed resolution of LWG 334 (value_type instead of make_pair). This isn't exactly what happened, though, looking at its history. It's simply following SGI STL. libc++ doesn't strictly conform to C++03 in this respect.

---

libstdc++'s C++11 version of the same operator uses a custom emplacement function. The C++11 Standard's specification of map::operator[] follows the proposed resolution of LWG 334:

Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.

(where x is the parameter of operator[])