erasing from vectors with iterators, what is going on here?

[awm129]

I seem to be confused. I understand the implications of erasing an
element in the middle of vector and what that means for existing
iterators, but I'm not sure where this behavior is coming from.
Consider the following program and output:

#include <iostream>
#include <ostream>
#include <vector>

using namespace std;


class Element
{
public:
Element() : m_var(1){};
~Element();
int m_var;
};

inline ostream& operator<<( ostream& ss, const Element& e )
{
return ss << "0x" << &e.m_var;
}

inline ostream& operator<<( ostream& ss, const
vector<Element>::iterator& e )
{
return ss << *e;
}

Element::~Element()
{
cout << " deleting: " << *this << endl;
}

int main()
{
vector<Element> vec;
vector<Element>::iterator itr;

// add three elements
itr = vec.insert( vec.end(), Element() );
cout << "added: " << itr << endl;
itr = vec.insert( vec.end(), Element() );
cout << "added: " << itr << endl;
itr = vec.insert( vec.end(), Element() );
cout << "added: " << itr << endl;

// print them all out
for( itr = vec.begin(); itr != vec.end(); ++itr )
{
cout << "in the vector: " << itr << endl;
}

// remove the middle Element
// the erase seems to be removing the wrong element...
itr = vec.begin() + 1;
cout << "erasing: " << itr << endl;
vec.erase( itr );

return 0;
}


OUTPUT:

deleting: 0x0012FD90
deleting: 0x0012FF28
added: 0x003660B0
deleting: 0x003660B0
deleting: 0x0012FD90
deleting: 0x0012FF14
added: 0x0036618C
deleting: 0x00366188
deleting: 0x0036618C
deleting: 0x0012FD90
deleting: 0x0012FF00
added: 0x003661D8
in the vector: 0x003661D0
in the vector: 0x003661D4
in the vector: 0x003661D8
erasing: 0x003661D4
deleting: 0x003661D8


Shouldn't the last two lines be the same memory address?! Its like
erase is removing the element AFTER the iterator I'm giving it. I
feel really dumb, what am I missing here?

I intend to rewrite this using stl algorithm (remove_if and friends)
but I need to understand what is going on here first. Thanks!

 

[Victor Bazarov]

[..]
Shouldn't the last two lines be the same memory address?! Its like
erase is removing the element AFTER the iterator I'm giving it. I
feel really dumb, what am I missing here?

The erase does not delete the actual element, it shifts all elements
after the erased one up, and then deletes the last one. It uses
assignment (probably) to shift the elements.

Try tracking not only default construction and destruction, but also the
copy construction and assignment.

I intend to rewrite this using stl algorithm (remove_if and friends)
but I need to understand what is going on here first. Thanks!

Do you need to understand it, really? Don't you trust the library
implementors and compiler writers?

V

 

[Stephen Horne]

Shouldn't the last two lines be the same memory address?! Its like
erase is removing the element AFTER the iterator I'm giving it. I
feel really dumb, what am I missing here?

Consider the following array/vector...

0 1 2 3 4 5 6 7
A B C D E - - -

We have allocated a bit too much memory (common in std::vector), so we
have some memory slots reserved that don't contain properly
constructed - the "-" elements. This distinction is only important for
non-POD types, but your elements are non-POD (you have destructors
etc).

If we erase the item at subscript 2, what happens is...

1. We shift down the items from subscripts 3 upwards...

a. Copy from subscript 3 to subscript 2...

0 1 2 3 4 5 6 7
A B D D E - - -
^--^

b. Copy from subscript 4 to subscript 3...

0 1 2 3 4 5 6 7
A B D E E - - -
^--^

2. We destroy the unwanted item at the end - hidden in the libraries,
there's a destructor call.

0 1 2 3 4 5 6 7
A B D E - - - -
^

In other words, when you ask for the item at subscript 2 to be erased,
it actually gets overwritten as higher-up items get shifted down. The
shifting isn't really moving objects, just assigning values. The
array-slot that gets destructed is the one containing the instance we
no longer want.

If you're coming from Java or C#, you may be confused by the fact that
C++ puts the objects themselves in the std::vector - not references to
those objects. In Java and C#, IIRC, erasing an element from a
variable-length array only copies references around - not the objects
themselves.

If you want that behaviour in C++, you use a vector of pointers or a
vector of smart pointer class instances.

 

[tni]

I seem to be confused. I understand the implications of erasing an
element in the middle of vector and what that means for existing
iterators, but I'm not sure where this behavior is coming from.
Consider the following program and output:
>
[...]
>
erasing: 0x003661D4
deleting: 0x003661D8


Shouldn't the last two lines be the same memory address?!
No.

Its like erase is removing the element AFTER the iterator I'm giving it.

Normally, erase simply copies everything after the element(s) being
erased down (using the assignment operator) and then deletes the last
element(s).

 

[awm129]

Consider the following array/vector...

  0  1  2  3  4  5  6  7
  A  B  C  D  E  -  -  -

We have allocated a bit too much memory (common in std::vector), so we
have some memory slots reserved that don't contain properly
constructed - the "-" elements. This distinction is only important for
non-POD types, but your elements are non-POD (you have destructors
etc).

If we erase the item at subscript 2, what happens is...

1.  We shift down the items from subscripts 3 upwards...

    a.  Copy from subscript 3 to subscript 2...

        0  1  2  3  4  5  6  7
        A  B  D  D  E  -  -  -
              ^--^

    b.  Copy from subscript 4 to subscript 3...

        0  1  2  3  4  5  6  7
        A  B  D  E  E  -  -  -
                 ^--^

2.  We destroy the unwanted item at the end - hidden in the libraries,
    there's a destructor call.

        0  1  2  3  4  5  6  7
        A  B  D  E  -  -  -  -
                    ^

In other words, when you ask for the item at subscript 2 to be erased,
it actually gets overwritten as higher-up items get shifted down. The
shifting isn't really moving objects, just assigning values. The
array-slot that gets destructed is the one containing the instance we
no longer want.

If you're coming from Java or C#, you may be confused by the fact that
C++ puts the objects themselves in the std::vector - not references to
those objects. In Java and C#, IIRC, erasing an element from a
variable-length array only copies references around - not the objects
themselves.

If you want that behaviour in C++, you use a vector of pointers or a
vector of smart pointer class instances.

Ah, this makes sense. And leads me to my next (real) question. The
real problem I'm facing involves a polymorphic pointer as a member of
these objects stored in the vector. How are the copies made in stl
vector? My special copy constructors that handle the pointer properly
don't seem to be called. Currently, when an item is erased from the
vector, an exact copy of my pointer is being deleted and causing the
remaining ones to be invalid. Do I need to overload operator=()? I
think a vector of pointers would solve all of this.

I can't write a sample program to illustrate the issue at the moment,
but I can post one later if the above description is insufficient.
Thanks!

 

[awm129]

I seem to be confused.  I understand the implications of erasing an
element in the middle of vector and what that means for existing
iterators, but I'm not sure where this behavior is coming from.
Consider the following program and output:

[...]

erasing: 0x003661D4
  deleting: 0x003661D8

Shouldn't the last two lines be the same memory address?!
No.

Its like erase is removing the element AFTER the iterator I'm giving it..

Normally, erase simply copies everything after the element(s) being
erased down (using the assignment operator) and then deletes the last
element(s).

Ok, so I do need to overload operator=(). However, if what I gather
from all the posts is correct, the destructor of the item I actually
want to erase is NOT guaranteed to be called. I need this destructor
to be called. Looks like I need to have a vector of pointers and
explicitly delete before erase. This should also save me from all
that copying. Thanks all!

 

[Victor Bazarov]

[..Stephen Horne's explanation..]

Ah, this makes sense. And leads me to my next (real) question. The
real problem I'm facing involves a polymorphic pointer as a member of
these objects stored in the vector. How are the copies made in stl
vector?

When? There are two ways to copy an object in C++: copy-construction
and copy-assignment. Make sure you correctly implement both.

> My special copy constructors that handle the pointer properly
don't seem to be called. Currently, when an item is erased from the
vector, an exact copy of my pointer is being deleted and causing the
remaining ones to be invalid. Do I need to overload operator=()?

You bet. Read up on "The Rule of Three".

> I
think a vector of pointers would solve all of this.

It might. And it can speed things up, too. But you're going to be
responsible for maintaining the objects' lifetime. std::vector of
pointers does not delete the objects when the pointers are removed. If
you need to correctly and automatically maintain the lifetime, you might
be better off with a vector of smart pointers (just don't use 'auto_ptr'
for that - it's not suited).

I can't write a sample program to illustrate the issue at the moment,
but I can post one later if the above description is insufficient.
Thanks!

V

 

[tni]

Ok, so I do need to overload operator=(). However, if what I gather
from all the posts is correct, the destructor of the item I actually
want to erase is NOT guaranteed to be called. I need this destructor
to be called. Looks like I need to have a vector of pointers and
explicitly delete before erase. This should also save me from all
that copying. Thanks all!

Looks like you have a design issue.

Anyway, you may also want to look at the Boost Pointer Containers:

http://www.boost.org/doc/libs/1_39_0/libs/ptr_container/doc/reference.html
http://www.boost.org/doc/libs/1_39_0/libs/ptr_container/doc/ptr_vector.html

ptr_vector will do what you want (so you don't need to do the delete
explicitly).

 

[Richard Herring]

In message

Ok, so I do need to overload operator=(). However, if what I gather
from all the posts is correct, the destructor of the item I actually
want to erase is NOT guaranteed to be called.

That's right. But its assignment operator _is_ called, to copy the
element ahead of it into its place, and that operator should take care
of "erasing" the old value. If it doesn't, you're going to have problems
everywhere your objects get copied, not just in vectors.

I need this destructor
to be called. Looks like I need to have a vector of pointers and
explicitly delete before erase.

No, you need to ensure that the copy constructor, assignment operator
and destructor behave consistently.

You might consider implementing the assignment operator using the
copy-and-swap idiom, which will ensure that assignment effectively
invokes the destructor on the old value and the copy constructor on the
new value.

This should also save me from all
that copying.

And give you the responsibility of managing the lifetime of all those
pointed-to objects. Not necessarily a good tradeoff.

Worry about the cost of copying when you've determined (by profiling)
that it really exists, not before.