STL Question: Safe to use elements after erasing them from the collection?

Discussion in 'C++' started by Generic Usenet Account, Dec 5, 2003.

  1. To settle the dispute regarding what happens when an "erase" method is
    invoked on an STL container (i.e. whether the element is merely
    removed from the container or whether it also gets deleted in the
    process), I looked up the STL code. Erase certainly does not delete
    the memory associated with the element. However, it appears that the
    destructor on the element is invoked. I wonder why it has to be this
    way. In my opinion, this renders the element extremely risky to use
    after it has been "erased" from the collection.


    stl_list.h
    ....
    iterator erase(iterator position) {
    link_type next_node = link_type(position.node->next);
    link_type prev_node = link_type(position.node->prev);
    prev_node->next = next_node;
    next_node->prev = prev_node;
    destroy_node(position.node);
    return iterator(next_node);
    }
    ....

    void destroy_node(link_type p) {
    destroy(&p->data);
    put_node(p);
    }
    ....


    stl_construct.h
    ....
    template <class T>
    inline void destroy(T* pointer) {
    pointer->~T(); // KPB Note:- we are explicitly
    // invoking the destructor,
    // but we are not performing
    // the delete operation
    }
    ....


    Any insights into this would be welcome.

    Regards,
    KP Bhat
    Generic Usenet Account, Dec 5, 2003
    #1
    1. Advertising

  2. "Generic Usenet Account" <> wrote in message
    news:...
    | To settle the dispute regarding what happens when an "erase" method is
    | invoked on an STL container (i.e. whether the element is merely
    | removed from the container or whether it also gets deleted in the
    | process), I looked up the STL code.
    | Erase certainly does not delete the memory associated with the element.
    Most containers (excluding std::vector) may release the memory associated
    with items that have been removed using the erase member function.
    However, many implementations will keep a cache of previously
    allocated nodes, to speed-up later addition of new elements.

    | However, it appears that the
    | destructor on the element is invoked. I wonder why it has to be this
    | way. In my opinion, this renders the element extremely risky to use
    | after it has been "erased" from the collection.
    According to the standard, the destructor of the erased elements
    *must* be called. It is not uncommon for code to rely on the
    deterministic destruction of the items being erased.
    Attempting to access items that have been erased leads to undefined
    behavior. Even if they were not destroyed immediately, hopefully
    the memory they occupy would be recycled at some point. So it
    wouldn't be safe to access the erased items either way.

    | void destroy_node(link_type p) {
    | destroy(&p->data);
    | put_node(p);
    | }
    I would guess that 'put_node()' is used by this implementation
    to store the node into a list of nodes that can be recycled.

    | stl_construct.h
    | ...
    | template <class T>
    | inline void destroy(T* pointer) {
    | pointer->~T(); // KPB Note:- we are explicitly
    | // invoking the destructor,
    | // but we are not performing
    | // the delete operation
    | }
    The allocated memory includes the item itself and the
    prev/next links of the list nodes. It may also be part
    of an array of nodes that have been allocated as a chunk,
    to optimize performance.
    The memory storage itself will typically be freed or
    recycled at a later point in time...


    I hope this helps,
    Ivan
    --
    http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form
    Brainbench MVP for C++ <> http://www.brainbench.com
    Ivan Vecerina, Dec 5, 2003
    #2
    1. Advertising

  3. Re: STL Question: Safe to use elements after erasing them from thecollection?

    Generic Usenet Account wrote:
    > To settle the dispute regarding what happens when an "erase" method is
    > invoked on an STL container (i.e. whether the element is merely
    > removed from the container or whether it also gets deleted in the
    > process), I looked up the STL code. Erase certainly does not delete
    > the memory associated with the element. However, it appears that the
    > destructor on the element is invoked. I wonder why it has to be this
    > way. In my opinion, this renders the element extremely risky to use
    > after it has been "erased" from the collection.

    ....
    >
    > Any insights into this would be welcome.


    From the perspective of the container's client, you don't know if a
    delete or calling the destructor is used and you should not know.

    I suspect that the container is using a caching mechanism to speed up
    the case where objects are destroyed and re-created in succession. But
    the client should not care.
    Gianni Mariani, Dec 5, 2003
    #3
  4. "Ivan Vecerina" <> wrote in message
    news:bqqd6o$ord$...
    > "Generic Usenet Account" <> wrote in message
    > news:...
    > | To settle the dispute regarding what happens when an "erase" method is
    > | invoked on an STL container (i.e. whether the element is merely
    > | removed from the container or whether it also gets deleted in the
    > | process), I looked up the STL code.
    > | Erase certainly does not delete the memory associated with the element.
    > Most containers (excluding std::vector) may release the memory associated
    > with items that have been removed using the erase member function.

    <<snip>>
    > According to the standard, the destructor of the erased elements
    > *must* be called. It is not uncommon for code to rely on the
    > deterministic destruction of the items being erased.
    > Attempting to access items that have been erased leads to undefined
    > behavior. Even if they were not destroyed immediately, hopefully
    > the memory they occupy would be recycled at some point. So it
    > wouldn't be safe to access the erased items either way.


    Does this mean that it is bad behavior to put an object into two different
    containers, or is that even possible?
    (Forgive me for asking, but in Java it works differently. I was hoping it
    worked similarly in C++.)
    --
    Gary
    Gary Labowitz, Dec 5, 2003
    #4
  5. Generic Usenet Account

    Unforgiven Guest

    Gary Labowitz wrote:
    > Does this mean that it is bad behavior to put an object into two
    > different containers, or is that even possible?
    > (Forgive me for asking, but in Java it works differently. I was
    > hoping it worked similarly in C++.)


    It would seem to be me that the object being destructed is the list *node*
    that contains the object you put in it, not the actual object. The latter
    would be impossible, because it can be an intrinsic type (that has no
    destructor to call) or a pointer or copied object or whatever. And in the
    case of pointers, it's not the list's responsibility to take care of object
    lifetime anyway. That's always the responsibility of whoever called new.

    --
    Unforgiven

    "Most people make generalisations"
    Freek de Jonge
    Unforgiven, Dec 5, 2003
    #5
  6. Generic Usenet Account

    Jon Bell Guest

    In article <>,
    Gary Labowitz <> wrote:
    >
    >Does this mean that it is bad behavior to put an object into two different
    >containers, or is that even possible?


    It's not even possible. When you "put an object into a container", you
    are actually putting a *copy* of the object into the container, invoking
    the copy constructor of the object's class.

    To prevent the copying, you can store a *pointer* to the object into a
    suitably-declared container (e.g. vector<foo*> instead of vector<foo>),
    but in that case, erasing the pointer has no effect on the object itself.

    --
    Jon Bell <> Presbyterian College
    Dept. of Physics and Computer Science Clinton, South Carolina USA
    Jon Bell, Dec 5, 2003
    #6
  7. "Jon Bell" <> wrote in message
    news:bqqgk4$f42$...
    > In article <>,
    > Gary Labowitz <> wrote:
    > >
    > >Does this mean that it is bad behavior to put an object into two

    different
    > >containers, or is that even possible?

    >
    > It's not even possible. When you "put an object into a container", you
    > are actually putting a *copy* of the object into the container, invoking
    > the copy constructor of the object's class.
    >
    > To prevent the copying, you can store a *pointer* to the object into a
    > suitably-declared container (e.g. vector<foo*> instead of vector<foo>),
    > but in that case, erasing the pointer has no effect on the object itself.


    Ah, so. And, of course. Java operates only like the latter (only it's a
    reference variable). No problem. Thanks.
    --
    Gary
    Gary Labowitz, Dec 5, 2003
    #7
  8. (Jon Bell) wrote in message news:<bqqgk4$f42$>...

    > It's not even possible. When you "put an object into a container", you
    > are actually putting a *copy* of the object into the container, invoking
    > the copy constructor of the object's class.
    >
    > To prevent the copying, you can store a *pointer* to the object into a
    > suitably-declared container (e.g. vector<foo*> instead of vector<foo>),
    > but in that case, erasing the pointer has no effect on the object itself.



    Jon Bell is absolutely right. I am attaching some source code that I
    wrote to test out the STL behavior with this posting. My apologies if
    I am breaking the netiquette of this group.

    Here are my findings....

    · If the collection stores values rather than pointers (e.g.
    list<Class_XYZ>), a copy of the entity is dynamically created, using
    the copy constructor, and stored in the collection

    · If the collection stores pointers rather than values (e.g. list<
    Class_XYZ*>), the entity itself is stored

    · If the collection stores values rather than pointers, upon invoking
    erase(), the copy of the entity (that was stored in the collection)
    gets deleted (using delete, since the destructor gets invoked). The
    original entity is left untouched

    · If the collection stores pointers rather than values, upon invoking
    erase(), the entity is merely removed from the collection but does not
    get deleted


    In other words....
    1) erase() merely removes an element from a collection, and does not
    free up the associated memory

    2) If the entity is an object, it is copied with the copy constructor
    and deleted with the destructor.

    3) If the entity is a pointer, the pointer is copied by value and the
    storage for the pointer is subsequently released. Releasing the
    pointer does not affect the pointed-to object.


    Regards,
    KP Bhat


    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Element.h~~~~~~~~~~~~~~~~~~~~~~~~~~~
    #include <time.h>
    #include <iostream.h>

    class Element
    {
    public:
    Element(time_t i, char x[])
    {
    m_attr = i;
    strcpy(m_label, x);

    cout << "CTOR:: Element " << dec << m_attr << ", Pointer " << hex
    << this << ", " << m_label << endl;

    }

    Element(const Element& elem)
    {
    m_attr = elem.m_attr;
    strcpy(m_label, elem.m_label);

    cout << "COPY-CTOR:: Element " << dec << m_attr << ", Pointer " <<
    hex
    << this << ", " << m_label << endl;
    }

    ~Element()
    {
    cout << "DTOR:: Element " << dec << m_attr << ", Pointer " << hex
    << this << ", " << m_label << endl;
    }

    void display()
    {
    cout << ctime(&m_attr);
    }

    void printAddress() const
    {
    cout << hex << this << endl;
    }

    bool operator<(const Element& elem) const
    {
    bool retVal = (m_attr < elem.m_attr);
    return retVal;
    }

    protected:
    time_t m_attr;
    char m_label[80];
    };


    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Main.cpp~~~~~~~~~~~~~~~~~~~~~~~~~~~
    #include "Element.h"

    #ifdef VECTOR
    #include <vector>
    #elif defined LIST
    #include <list>
    #elif defined DEQUE
    #include <deque>
    #elif defined SET
    #include <set>
    #elif defined MULTISET
    #include <multiset.h>
    #endif


    void
    main()
    {
    #ifdef VECTOR
    cout << "Vector test\n\n";
    #elif defined LIST
    cout << "List test\n\n";
    #elif defined DEQUE
    cout << "Deque test\n\n";
    #elif defined SET
    cout << "Set test\n\n";
    #elif defined MULTISET
    cout << "Multiset test\n\n";
    #endif

    Element elem1(132, "VALUE");
    Element elem2(232, "VALUE");
    Element elem3(332, "VALUE");

    Element *elem4 = new Element(432, "POINTER");
    Element *elem5 = new Element(532, "POINTER");
    Element *elem6 = new Element(632, "POINTER");

    Element elem7(732, "VALUE --- will store address in Ptr
    collection");
    Element elem8(832, "VALUE --- will store address in Ptr
    collection");
    Element elem9(932, "VALUE --- will store address in Ptr
    collection");

    Element *elem10 = &elem7;
    Element *elem11 = &elem8;
    Element *elem12 = &elem9;

    cout << endl;

    #ifdef VECTOR
    vector<Element> collElem;
    vector<Element*> collElemPtr;

    vector<Element>::iterator valueItor;
    vector<Element*>::iterator pointerItor;

    cout << "Inserting elements in collection-1\n";
    collElem.push_back(elem1);
    collElem.push_back(elem2);
    collElem.push_back(elem3);
    cout << "Inserted elements in collection-1\n\n";

    cout << "Inserting elements in collection-2\n";
    collElemPtr.push_back(elem4);
    collElemPtr.push_back(elem5);
    collElemPtr.push_back(elem6);
    collElemPtr.push_back(elem10);
    collElemPtr.push_back(elem11);
    collElemPtr.push_back(elem12);
    cout << "Inserted elements in collection-2\n\n";

    #elif defined LIST
    list<Element> collElem;
    list<Element*> collElemPtr;

    list<Element>::iterator valueItor;
    list<Element*>::iterator pointerItor;

    cout << "Inserting elements in collection-1\n";
    collElem.push_back(elem1);
    collElem.push_back(elem2);
    collElem.push_back(elem3);
    cout << "Inserted elements in collection-1\n\n";

    cout << "Inserting elements in collection-2\n";
    collElemPtr.push_back(elem4);
    collElemPtr.push_back(elem5);
    collElemPtr.push_back(elem6);
    collElemPtr.push_back(elem10);
    collElemPtr.push_back(elem11);
    collElemPtr.push_back(elem12);
    cout << "Inserted elements in collection-2\n\n";

    #elif defined DEQUE
    deque<Element> collElem;
    deque<Element*> collElemPtr;

    deque<Element>::iterator valueItor;
    deque<Element*>::iterator pointerItor;

    cout << "Inserting elements in collection-1\n";
    collElem.push_back(elem1);
    collElem.push_back(elem2);
    collElem.push_back(elem3);
    cout << "Inserted elements in collection-1\n\n";

    cout << "Inserting elements in collection-2\n";
    collElemPtr.push_back(elem4);
    collElemPtr.push_back(elem5);
    collElemPtr.push_back(elem6);
    collElemPtr.push_back(elem10);
    collElemPtr.push_back(elem11);
    collElemPtr.push_back(elem12);
    cout << "Inserted elements in collection-2\n\n";

    #elif defined SET
    set<Element> collElem;
    set<Element*> collElemPtr;

    set<Element>::iterator valueItor;
    set<Element*>::iterator pointerItor;

    cout << "Inserting elements in collection-1\n";
    collElem.insert(elem1);
    collElem.insert(elem2);
    collElem.insert(elem3);
    cout << "Inserted elements in collection-1\n\n";

    cout << "Inserting elements in collection-2\n";
    collElemPtr.insert(elem4);
    collElemPtr.insert(elem5);
    collElemPtr.insert(elem6);
    collElemPtr.insert(elem10);
    collElemPtr.insert(elem11);
    collElemPtr.insert(elem12);
    cout << "Inserted elements in collection-2\n\n";


    #elif defined MULTISET
    multiset<Element> collElem;
    multiset<Element*> collElemPtr;

    multiset<Element>::iterator valueItor;
    multiset<Element*>::iterator pointerItor;

    cout << "Inserting elements in collection-1\n";
    collElem.insert(elem1);
    collElem.insert(elem2);
    collElem.insert(elem3);
    cout << "Inserted elements in collection-1\n\n";

    cout << "Inserting elements in collection-2\n";
    collElemPtr.insert(elem4);
    collElemPtr.insert(elem5);
    collElemPtr.insert(elem6);
    collElemPtr.insert(elem10);
    collElemPtr.insert(elem11);
    collElemPtr.insert(elem12);
    cout << "Inserted elements in collection-2\n\n";
    #endif


    cout << "\n\nTraversing collElem collection (collection-1)" << endl;
    for(valueItor = collElem.begin(); valueItor != collElem.end();
    valueItor++)
    {
    cout << "The object pointer is ";
    valueItor->printAddress();
    }
    cout << "Traversed collElem collection (collection-1)" << endl;

    cout << "\n\nTraversing collElemPtr collection (collection-2)" <<
    endl;
    for(pointerItor = collElemPtr.begin(); pointerItor !=
    collElemPtr.end();
    pointerItor++)
    {
    Element* elemPtr = *pointerItor;
    cout << "The object pointer is ";
    elemPtr->printAddress();
    }
    cout << "Traversed collElemPtr collection (collection-2)" << endl;


    cout << "\n\nErasing collElem collection (collection-1)" << endl;
    collElem.erase(collElem.begin(), collElem.end());
    cout << "Erased collElem (collection-1) entirely\n\n" << endl;

    cout << "\n\nErasing collElemPtr collection (collection-2)" << endl;
    collElemPtr.erase(collElemPtr.begin(), collElemPtr.end());
    cout << "Erased collElemPtr (collection-2) entirely\n\n" << endl;

    return 0;
    }
    Generic Usenet Account, Dec 21, 2003
    #8
  9. (Generic Usenet Account) wrote in message news:<>...
    >
    > Here are my findings....
    >
    > · If the collection stores values rather than pointers (e.g.
    > list<Class_XYZ>), a copy of the entity is dynamically created, using
    > the copy constructor, and stored in the collection
    >
    > · If the collection stores pointers rather than values (e.g. list<
    > Class_XYZ*>), the entity itself is stored
    >
    > · If the collection stores values rather than pointers, upon invoking
    > erase(), the copy of the entity (that was stored in the collection)
    > gets deleted (using delete, since the destructor gets invoked). The
    > original entity is left untouched
    >
    > · If the collection stores pointers rather than values, upon invoking
    > erase(), the entity is merely removed from the collection but does not
    > get deleted
    >
    >
    > In other words....
    > 1) erase() merely removes an element from a collection, and does not
    > free up the associated memory
    >
    > 2) If the entity is an object, it is copied with the copy constructor
    > and deleted with the destructor.
    >
    > 3) If the entity is a pointer, the pointer is copied by value and the
    > storage for the pointer is subsequently released. Releasing the
    > pointer does not affect the pointed-to object.
    >



    For base classes with a virtual method, it is a safer bet to go with a
    collection of pointers rather than a collection of instances, as the
    following code snippet shows:

    //~~~~~~~~~~~~~~~~~~~ Code snippet begins ~~~~~~~~~~
    #include <iostream.h>
    #include <list.h>

    class Base
    {
    protected:
    int i;

    public:
    Base(int m){ i = m;}
    int get_i(){return i;}
    virtual int xyz(){return i;} // Returns the value of the base
    // class attribute
    };

    class Derived : public Base
    {
    protected:
    int j;

    public:
    Derived(int m, int n):Base(m){j=n;}
    int get_j(){return j;}
    int xyz(){return j;} // Returns the value of the derived
    // class attribute
    };

    typedef list<Base> BaseList;
    typedef list<Base>::iterator BaseIterator;
    typedef list<Derived> DerivedList;
    typedef list<Derived>::iterator DerivedIterator;

    typedef list<Base*> BasePtrList;
    typedef list<Base*>::iterator BasePtrIterator;
    typedef list<Derived*> DerivedPtrList;
    typedef list<Derived*>::iterator DerivedPtrIterator;


    main()
    {
    Derived *d[5];

    for(int k1 = 0; k1 < 5; k1++)
    {
    d[k1] = new Derived(k1, 2*k1);
    // The base attribute ('i') has value 0 through
    4
    // The derived attribute value ('j') is double
    that
    }

    // Instance collection declarations
    BaseList bcollection;
    BaseIterator biter, beol;
    DerivedList dcollection;
    DerivedIterator diter, deol;


    // Pointer collection declarations
    BasePtrList bpcollection;
    BasePtrIterator bpiter, bpeol;
    DerivedPtrList dpcollection;
    DerivedPtrIterator dpiter, dpeol;

    for(int k2 = 0; k2 < 5; k2++)
    {
    //Insert elements in base collection
    bcollection.insert(bcollection.begin(), *d[k2]);

    //Insert the SAME elements in the derived collection
    dcollection.insert(dcollection.begin(), *d[k2]);

    //Insert elements in base-ptr collection
    bpcollection.insert(bpcollection.begin(), d[k2]);

    //Insert the SAME elements in the derived-ptr collection
    dpcollection.insert(dpcollection.begin(), d[k2]);
    }

    cout << "** Instance-collection behavior **\n";
    // Iterate through the base collection and execute the
    // virtual method "xyz()" on each element
    cout << "Base collection:" << endl;
    beol = bcollection.end();
    for(biter=bcollection.begin(); biter != beol; biter++)
    cout << " get_i()=" << (*biter).get_i() << ", xyz()="
    << (*biter).xyz() << endl;

    // Iterate through the derived collection and execute the
    // virtual method "xyz()" on each element. Since we entered
    // the exact same elements in both lists, the EXPECTED output
    // is the same as before.
    //
    // Check out for yourself ;-(
    //
    cout << "Derived collection:" << endl;
    deol = dcollection.end();
    for(diter=dcollection.begin(); diter != deol; diter++)
    cout << " get_i()=" << (*diter).get_i() << ", xyz()="
    << (*diter).xyz() << endl;

    cout << "The exact same elements were entered in both
    collections.\n"
    << "Is the output the same in both the cases?\n";

    cout << "\n\n** Pointer-collection behavior **\n";
    // Iterate through the base-pointer collection and execute the
    // virtual method "xyz()" on each element
    cout << "Base-pointer collection:" << endl;
    bpeol = bpcollection.end();
    for(bpiter=bpcollection.begin(); bpiter != bpeol; bpiter++)
    cout << " get_i()=" << (*bpiter)->get_i() << ", xyz()="
    << (*bpiter)->xyz() << endl;

    // Iterate through the derived-pointer collection and execute the
    // virtual method "xyz()" on each element. Since we entered
    // the exact same elements in both lists, the EXPECTED output
    // is the same as before.
    //
    // No surprises this time around :-(
    cout << "Derived-pointer collection:" << endl;
    dpeol = dpcollection.end();
    for(dpiter=dpcollection.begin(); dpiter != dpeol; dpiter++)
    cout << " get_i()=" << (*dpiter)->get_i() << ", xyz()="
    << (*dpiter)->xyz() << endl;

    cout << "The exact same elements were entered in both
    collections.\n"
    << "Is the output the same in both the cases?\n";

    }

    //~~~~~~~~~~~~~~~~~~~ Code snippet ends ~~~~~~~~~~

    Regards,
    KP Bhat
    Generic Usenet Account, Jan 3, 2004
    #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. Owen Brydon

    Erasing map elements by iterator

    Owen Brydon, Oct 15, 2003, in forum: C++
    Replies:
    5
    Views:
    6,585
    Andrew Koenig
    Oct 16, 2003
  2. Øyvind Isaksen
    Replies:
    1
    Views:
    965
    Øyvind Isaksen
    May 18, 2007
  3. Krzysztof Poc

    erasing from stl list

    Krzysztof Poc, Jan 18, 2010, in forum: C++
    Replies:
    10
    Views:
    554
    Krzysztof Poc
    Jan 22, 2010
  4. A B
    Replies:
    5
    Views:
    470
    Juha Nieminen
    Nov 18, 2010
  5. A B
    Replies:
    5
    Views:
    595
Loading...

Share This Page