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

Attune

You don't get them in C++11 mode so why not remove all the rvalue-ref functions from the question entirely? The question is obviously not affected by them. – Sized

I expect this is a QoI thing inside libstdc++ and guess that it would take some doing to pointlessly determine precisely what's going on. – Sized

@LightnessRacesinOrbit They are there because the question is not affected by them, in contradiction to the earlier answer. – Attune

It's generally a good idea, when you want to know the effect of Variable A, not to introduce an unnecessary and irrelevant Variable B. – Sized

The answer you point to is misleading at best. The Foo presented in that question has a user provided copy constructor & copy assignment operator, which will suppress implicit declaration of their move special member function counterparts, so Foo will never be moved, even in -std=c++11 mode, which is what the answer seems to suggest is happening. Moreover, libc++ produces the same output in C++03 and C++11 modes, so it is a QoI issue. As Lightness says, to figure out what's going on will involve digging through the libstdc++ implementation. – Polyandrist

Sure, so the earlier question is wrong. Not sure why you have to make this question a bad question just because they got it wrong. Include a link to the other question, mention that it is wrong and why in an appendix. Making it central to your question just adds noise. I get that is why you asked the question: but why is background info, not central info. – Danger

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[])

Rhynchocephalian

As far as I can tell, C++03 didn't change the effects of map::operator[] compared to C++98. – Rhynchocephalian

Thanks, that was interesting and thorough. In c++11, the wording of effects seems to be what is in LWG 334. – Attune

@Attune Yes, I stopped a bit early there. I've included the C++11 wording now. It was also quite interesting to dig into gcc's git history! Luckily, I remembered there was some LWG issue related to operator[], so finding LWG 334 wasn't too difficult. – Rhynchocephalian

As a small follow up do you happen to know if anything was done about the following comment in LWG 334? "We may also wish to have a blanket statement somewhere in clause 17 saying that we do not intend the semantics of sample code fragments to be interpreted as specifing exactly how many copies are made. " – Attune

@Attune Sorry, I don't know. I can't find anything similar in C++14's §17, though. I guess they've (currently) resolved it by making the specification of individual functions more abstract (just like map::operator[]). – Rhynchocephalian

@Attune See also open-std.org/JTC1/SC22/WG21/docs/lwg-defects.html#98 – Rhynchocephalian