vector push_back deletes objects

[cronusf]

Whenever I add an object to a vector, the destructors of all the
previous objects in the vector get called. Why? It seems a push_back
would just copy the object to add to the next free slot in the vector,
and leave all the other objects alone. The only time I could see this
is if the vector needs to add more memory, but this shouldn't happen
with every push_back call.

Test app:

#include <iostream>
using namespace std;

struct Location
{
Location();
Location(int a, int b);
~Location();

void show();

int x;
int y;
};

Location::Location()
{
x = 0 ;
y = 0 ;
}

Location::Location(int a, int b)
{
x = a ;
y = b ;
}

Location::~Location()
{
cout << "*** Location " << x << " , " << y
<< " destructor called *** " << endl << endl ;
}

void Location::show()
{
cout << "( " << x << " , " << y << " ) " ;

}

#include <iostream>
#include <vector>
using namespace std ;

int main()
{
vector<Location> Vec; // to store route

Location L[5] ; // Location array

// add co-ords to Location array
for ( int i = 0 ; i < 5 ; ++ i )
{
L.x = i ;
L.y = i ;
}

cout << endl << "Pushing .. " << endl ;

for ( unsigned int i = 0 ; i < 5 ; ++ i )
{
cout << endl << "Pushing .. " ;
L.show() ;
cout << endl ;
cout << "Vec push back start " << endl ;
Vec.push_back( L ) ;
cout << "Vec push back end " << endl ;
}

cout << endl << "Leaving prog .. " << endl << endl ;
}

 

[crimaniak]

Whenever I add an object to a vector, the destructors of all the
previous objects in the vector get called.  Why?  It seems a push_back
would just copy the object to add to the next free slot in the vector,
and leave all the other objects alone.  The only time I could see this
is if the vector needs to add more memory, but this shouldn't happen
with every push_back call.

It _happens_ with every push_back. If you don't want vector
reallocation at every push_back, call Vec.reserve().
Calculate before pushing if you can how much elements you need or
just reserve 2*current_size elements every time you reach limit.

 

[Rolf Magnus]

It _happens_ with every push_back.

It _can_ happen with every push_back, but doesn't have to.

If you don't want vector reallocation at every push_back, call
Vec.reserve().
Calculate before pushing if you can how much elements you need or
just reserve 2*current_size elements every time you reach limit.

Most implementations of push_back already do something like that, but that's
not required by the C++ standard.

 

[Alf P. Steinbach]

* Rolf Magnus:

It _can_ happen with every push_back, but doesn't have to.


Most implementations of push_back already do something like that, but that's
not required by the C++ standard.

push_back is required to have amortized constant complexity, and that implies
that it's required to "do something like that".


Cheers,

- Alf

 

[James Kanze]

It _can_ happen with every push_back, but doesn't have to.

It can't happen with every push_back. As Alf said, std::vector
requires push_back to have amortized constant complexity, which
effectively means exponential growth (in practice, multiplying
by 1.5 or 2).

Most implementations of push_back already do something like
that, but that's not required by the C++ standard.

It is.

I fully instrumented his code:
#define TRACE(f) std::cout << "Location:" #f << " (" << this << ")
\n"
then TRACE(ctor), TRACE(copy), TRACE(dtor) and TRACE(asgn) in
the normal constructor, the copy constructor, the destructor and
the assignment operator, to see what was going on. The number
of copies very definitely depends on the compiler (or the
library implementation---I'm not sure which), but with the
Microsoft compiler, you get an extra copy in the push_back, I
don't know why. The destructor he's seeing is of this copy.

FWIW: when trying to analyse this sort of thing, do instrument
all "special" functions, and output the address when you do so
(to distinguish instances, even copies). I've even considered
creating a base class which does this, e.g.:

struct Traced
{
Traced() { TRACE(ctor); }
Traced(Traced const& ) { TRACE(copy); }
~Traced() { TRACE(dtor); }
Traced& operator=(Traced const& ) { TRACE(asgn); return
*this; }
};

It will help a lot in understanding. The standard allows extra
copies in a lot of places, and different compilers do different
things; unless you've instrumented all of the big four, with
output of the address, it's pretty much impossible to follow
what's happening.

--

 

[cronusf]

It is.

I fully instrumented his code:
    #define TRACE(f) std::cout << "Location:" #f << " (" << this << ")
\n"
then TRACE(ctor), TRACE(copy), TRACE(dtor) and TRACE(asgn) in
the normal constructor, the copy constructor, the destructor and
the assignment operator, to see what was going on.  The number
of copies very definitely depends on the compiler (or the
library implementation---I'm not sure which), but with the
Microsoft compiler, you get an extra copy in the push_back, I
don't know why.  The destructor he's seeing is of this copy.

I was thinking of a copy being made, but that should just be one
destructor per push_back. But if the vector has say 3 elements
already in it, and you do a push_back, those 3 elements get
destructed, which seems very strange. I am using VC++ 2008.

 

[James Kanze]

I was thinking of a copy being made, but that should just be one
destructor per push_back.

It should be as many destructors as there are copies, minus one (the
object which remains in the vector). When the vector grows, all of
the
existing elements must be copied (and thus destroyed in the old
image).

Looking at the addresses in my traces, I can see that when pushing
(1,1), the copy constructor and the destructor is called on the
element
constructed when pushing (0,0). When pushing (2,2), destructors are
called on both of the new elements created when pushing (1,1). When
pushing (3,3), VC++ grows the array again---g++ doesn't. When pushing
(4,4), both grow the array again. (Off hand, I'd guess that VC++ is
using 1.5 as a multiplier, and g++ 2.0.) And VC++ has one extra copy
per push_back. (I've not looked at the generated code to see where or
why.)

Other compilers may give still other results. The standard only
requires that the average number of copies per push_back be more or
less
constant over a large number of push_back, and independent of the size
of the array; in other words, if you grow the array from 100 to 200,
or
from 1000 to 2000, you should have roughly 10 times more copies
(because
10 times more push_back) in the second case.

But if the vector has say 3 elements already in it, and you do a
push_back, those 3 elements get destructed, which seems very strange.
I am using VC++ 2008.

All that means is that the internal implementation has to grow the
memory when you go from 3 elements to 4.

I'll admit that this behavior surprises me a little; I would have
imagined that implementations would set some sort of minimum non-zero
size, to avoid having so many copies when the array size is small.
But
apparently neither g++ nor VC++ do. The algorithm seems to be a
simple:
new_size = max(old_size+n, k*old_size);
where n is the number of elements being inserted (1 in the case of
push_back), and k is an implementation defined constant (2 in the case
of g++, 1.5 in the case of VC++), rather than the
new_size = max(m, old_size+n, k*old_size);
that I would have used (with m a minimum---something like 8 or 16,
probably).