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

Discussion in 'C++' started by awm129, Jul 24, 2009.

  1. awm129

    awm129 Guest

    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!
     
    awm129, Jul 24, 2009
    #1
    1. Advertising

  2. awm129 wrote:
    > [..]
    > 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Jul 24, 2009
    #2
    1. Advertising

  3. On Thu, 23 Jul 2009 19:12:06 -0700 (PDT), awm129 <>
    wrote:

    >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.
     
    Stephen Horne, Jul 24, 2009
    #3
  4. awm129

    tni Guest

    awm129 wrote:
    > 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).
     
    tni, Jul 24, 2009
    #4
  5. awm129

    awm129 Guest

    On Jul 24, 12:21 am, Stephen Horne <>
    wrote:
    > On Thu, 23 Jul 2009 19:12:06 -0700 (PDT), awm129 <>
    > wrote:
    >
    > >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.


    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, Jul 24, 2009
    #5
  6. awm129

    awm129 Guest

    On Jul 24, 12:43 am, tni <> wrote:
    > awm129 wrote:
    > > 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!
     
    awm129, Jul 24, 2009
    #6
  7. awm129 wrote:
    > [..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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Jul 24, 2009
    #7
  8. awm129

    tni Guest

    awm129 wrote:
    > 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).
     
    tni, Jul 24, 2009
    #8
  9. In message
    <>,
    awm129 <> writes
    >On Jul 24, 12:43 am, tni <> wrote:
    >> awm129 wrote:
    >>
    >> > 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.


    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.

    >Thanks all!


    --
    Richard Herring
     
    Richard Herring, Jul 27, 2009
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sheep
    Replies:
    1
    Views:
    397
    Sheep
    Aug 14, 2006
  2. magical_muggle

    Question about nested vectors/iterators

    magical_muggle, May 7, 2007, in forum: C Programming
    Replies:
    0
    Views:
    573
    magical_muggle
    May 7, 2007
  3. Replies:
    3
    Views:
    709
    Shadowman
    Mar 26, 2008
  4. Christopher

    reverse iterators and erasing

    Christopher, Feb 25, 2009, in forum: C++
    Replies:
    1
    Views:
    327
    Christopher
    Feb 26, 2009
  5. Guest
    Replies:
    0
    Views:
    461
    Guest
    Sep 14, 2005
Loading...

Share This Page