Why are there *three* constructor calls when inserting an item intoa map<>?

[=?ISO-8859-1?Q?Szabolcs_Horv=E1t?=]

Consider the attached example program: an object of type 'A' is inserted
into a 'map<int, A> m;'. Why does 'm[0];' call the copy constructor of
'A' twice in addition to a constructor call?

The constructors and copy constructors in 'A' report when they are
called. 'whoami' is just a unique identifier assigned to every object of
type 'A'. The output of the program is:

constructor 0
constructor 1
copy cons 2 from 1
copy cons 3 from 2
destructor 2
destructor 1
assignment 3 from 0
destructor 0
destructor 3

I would expect one constructor call to be sufficient for creating an
object inside the map. Why is it necessary to copy twice the initially
created object?

I'd expect the following output:

constructor 0
constructor 1
assignment 1 from 0
destructor 0
destructor 1

(I tried this with both g++ and the digital mars compiler.)

-- Szabolcs

-----

#include <iostream>
#include <map>

using namespace std;

int counting_As = 0;

class A {
int whoami;
public:
A() {
whoami = counting_As++;
cout << "constructor " << whoami << endl;
}
~A() {
cout << "destructor " << whoami << endl;
}
A(const A &p) {
whoami = counting_As++;
cout << "copy cons " << whoami << " from " << p.whoami << endl;
}
A & operator = (const A &p) {
cout << "assignment " << whoami << " from " << p.whoami << endl;
return (*this);
}
};

int main() {
map<int, A> m;
A a;
m[0] = a;
return 0;
}

 

[loufoque]

I would expect one constructor call to be sufficient for creating an
object inside the map. Why is it necessary to copy twice the initially
created object?

I'd expect the following output:

constructor 0
constructor 1
assignment 1 from 0
destructor 0
destructor 1

You need to copy it at least one time to put it into the map, otherwise
your container doesn't contain anything, it just references an object on
automatic memory (the stack).
I don't know why it copies it two times though.

 

[=?ISO-8859-1?Q?Szabolcs_Horv=E1t?=]

You need to copy it at least one time to put it into the map, otherwise
your container doesn't contain anything, it just references an object on
automatic memory (the stack).
I don't know why it copies it two times though.

Actually you need no copy constructor calls at all, because operator []
in map already creates an object with a default value ('constructor 1'
in the output), so the assignment ('assignment 1 from 0') should be
sufficient.

What I don't understand whether these copy constructor calls are a
necessity (they are present in at least two STL implementations); could
map<> work without them?

 

[lancediduck]

Consider the attached example program: an object of type 'A' is inserted
into a 'map<int, A> m;'. Why does 'm[0];' call the copy constructor of
'A' twice in addition to a constructor call?

int main() {
map<int, A> m;
A a;
m[0] = a;
return 0;
}

This behavior is implementation dependent, and not all compiler setting
or library implementation will give you the same results. That said,
using operator[] for first insertions on the associative containers is
not terribly efficient. It goes something like this.

V& map:perator[K const&i]{
iterator _ret= this->find(i);
if(_ret==this->end()){//not found
V _tmp; //constructor 1
// map stores std:air<const K,V> under the hood
std:air _ins(i,_tmp); // copy construct 2 from 1
_ret=this->insert(_ins); // copy construct 3 from 2
//insert returns where it placed the copy
}
V& _valret=_ret->second;// the V part of the pair
return _valret;
//destructor 2
//destrutor 1
}
Now you have number 0 (the A a) and number 3 alive. And this is why you
now see assigment from 0 to 3.
Hope that helps

 

[Victor Bazarov]

Consider the attached example program: an object of type 'A' is
inserted into a 'map<int, A> m;'. Why does 'm[0];' call the copy
constructor of 'A' twice in addition to a constructor call?

Indexing operator on a map inserts a default-constructed object,
then calls assignment on it. Insertion of a default-constructed
object can cause a copy to be created. Step through all the
functions that

m[0] = a;

cause to be called, and you will see. BTW, it should give you
the idea that using the indexing operator to insert something in
a map is not the best idea. 'std::map' has 'insert' member for
that purpose.

The constructors and copy constructors in 'A' report when they are
called. 'whoami' is just a unique identifier assigned to every object
of type 'A'. The output of the program is:

constructor 0
constructor 1
copy cons 2 from 1
copy cons 3 from 2
destructor 2
destructor 1
assignment 3 from 0
destructor 0
destructor 3

I would expect one constructor call to be sufficient for creating an
object inside the map. Why is it necessary to copy twice the initially
created object?

I'd expect the following output:

constructor 0
constructor 1
assignment 1 from 0
destructor 0
destructor 1

(I tried this with both g++ and the digital mars compiler.)

-- Szabolcs

-----

#include <iostream>
#include <map>

using namespace std;

int counting_As = 0;

class A {
int whoami;
public:
A() {
whoami = counting_As++;
cout << "constructor " << whoami << endl;
}
~A() {
cout << "destructor " << whoami << endl;
}
A(const A &p) {
whoami = counting_As++;
cout << "copy cons " << whoami << " from " << p.whoami <<
endl; }
A & operator = (const A &p) {
cout << "assignment " << whoami << " from " << p.whoami <<
endl; return (*this);
}
};

int main() {
map<int, A> m;
A a;
m[0] = a;
return 0;
}

V

 

[Pete C]

int main() {
map<int, A> m;
A a;
m[0] = a;
return 0;
}

This behavior is implementation dependent, and not all compiler setting
or library implementation will give you the same results.

The Standard (23.3.1.2) says that map:perator[] :
Returns: (*((insert(make_pair(x, T()))).first)).second
I'm not sure how to interpret this: does it mandate the implementation,
or does it just specify that the return value should be "equivalent to"
that expression?

Your explanation is correct of course but I suspect that this
inefficiency is required by the standard.

 

[lancediduck]

int main() {
map<int, A> m;
A a;
m[0] = a;
return 0;
}

This behavior is implementation dependent, and not all compiler setting
or library implementation will give you the same results.

The Standard (23.3.1.2) says that map:perator[] :
Returns: (*((insert(make_pair(x, T()))).first)).second
I'm not sure how to interpret this: does it mandate the implementation,
or does it just specify that the return value should be "equivalent to"
that expression?

Your explanation is correct of course but I suspect that this
inefficiency is required by the standard.

That it is equivalent to that expression. I dont know why the standard
is so terse - it almost looks more like LISP than C++ with all those
parens. The expanded version is easier to read, and no less difficult
for a complier to optimize.
The reason that results may differ, is that for one you could get MORE
copies in a conforming implementation. Or, perhaps that the tree used
needed to rebabalance on the insertion (most implementors choose to
implement map as an rbtree) and you would see different results. Also,
in some implementations, implementors play with move constructors --
they know that for some types they are going to make a copy and then
destroy it or otherwise overwrite it, so in a few cases, you can save a
copy.

 

[Earl Purple]

Consider the attached example program: an object of type 'A' is
inserted into a 'map<int, A> m;'. Why does 'm[0];' call the copy
constructor of 'A' twice in addition to a constructor call?

Indexing operator on a map inserts a default-constructed object,
then calls assignment on it. Insertion of a default-constructed
object can cause a copy to be created. Step through all the
functions that

m[0] = a;

cause to be called, and you will see. BTW, it should give you
the idea that using the indexing operator to insert something in
a map is not the best idea. 'std::map' has 'insert' member for
that purpose.

insert is checked so if you attempt to insert the same key twice, it
will ignore the 2nd insert. Of course the fastest is insert with hint.
If you're doing a one-time load and then subsequently just finds, a
sorted vector can be more efficient than map.

 

[Howard Hinnant]

Szabolcs Horvát wrote:

int main() {
map<int, A> m;
A a;
m[0] = a;
return 0;
}
This behavior is implementation dependent, and not all compiler setting
or library implementation will give you the same results.

The Standard (23.3.1.2) says that map:perator[] :
Returns: (*((insert(make_pair(x, T()))).first)).second
I'm not sure how to interpret this: does it mandate the implementation,
or does it just specify that the return value should be "equivalent to"
that expression?

Your explanation is correct of course but I suspect that this
inefficiency is required by the standard.

That it is equivalent to that expression. I dont know why the standard
is so terse - it almost looks more like LISP than C++ with all those
parens. The expanded version is easier to read, and no less difficult
for a complier to optimize.
The reason that results may differ, is that for one you could get MORE
copies in a conforming implementation. Or, perhaps that the tree used
needed to rebabalance on the insertion (most implementors choose to
implement map as an rbtree) and you would see different results. Also,
in some implementations, implementors play with move constructors --
they know that for some types they are going to make a copy and then
destroy it or otherwise overwrite it, so in a few cases, you can save a
copy.

Fwiw, I don't currently see a conforming way to reduce the number of
copies below two:

You need a copy of the default constructed element in order to form the
pair<key,value>. There's no way to construct a pair with just a copy of
the key, and default construct the value in place. And then that pair
must be copy constructed because that is the only interface available to
allocator::construct (which needs to construct from a copy), which the
map is supposed to use.

If move semantics comes to pass in C++0X, then for expensive A's, the
following will (usually) help:

class A {
int whoami;
public:
A() {
whoami = counting_As++;
cout << "constructor " << whoami << endl;
}
~A() {
cout << "destructor " << whoami << endl;
}
A(const A &p) {
whoami = counting_As++;
cout << "copy cons " << whoami << " from " << p.whoami << endl;
}
A(A &&p) {
whoami = counting_As++;
cout << "move cons " << whoami << " from " << p.whoami << endl;
}
A & operator = (const A &p) {
cout << "assignment " << whoami << " from " << p.whoami << endl;
return (*this);
}
};

constructor 0
constructor 1
move cons 2 from 1
move cons 3 from 2
destructor 2
destructor 1
assignment 3 from 0
destructor 0
destructor 3

The move constructor is allowed to transfer resources from the source
object to construct itself (like auto_ptr "copy").

-Howard

 

[lancediduck]

Fwiw, I don't currently see a conforming way to reduce the number of
copies below two:
The move constructor is allowed to transfer resources from the source
object to construct itself (like auto_ptr "copy").

-Howard

I had just finished reading
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2006/n2027.html when
I wrote this, and I was hoping that some platform actually implemented
it. Also, inside the guts of STLPort, move constructors are used for
some optimizations like this, when it involves other std defined types.
I dont think that this particular optimization is made, but my
understanding is that even though the standard seemingly writes out the
steps needed to implement the function, the intent is that behavior of
these steps is preserved, if not exactly the sequence.

 

[lancediduck]

Fwiw, I don't currently see a conforming way to reduce the number of
copies below two:
The move constructor is allowed to transfer resources from the source
object to construct itself (like auto_ptr "copy").

-Howard

I had just finished reading
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2006/n2027.html when
I wrote this, and I was hoping that some platform actually implemented
it. Also, inside the guts of STLPort, move constructors are used for
some optimizations like this, when it involves other std defined types.
I dont think that this particular optimization is made, but my
understanding is that even though the standard seemingly writes out the
steps needed to implement the function, the intent is that behavior of
these steps is preserved, if not exactly the sequence.