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

[Generic Usenet Account]

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

[Ivan Vecerina]

"Generic Usenet Account" <us****@sta.samsung.com> wrote in message
news:90************************@posting.google.com ...
| 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

[Gianni Mariani]

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.

[Gary Labowitz]

"Ivan Vecerina" <pl*****************@ivan.vecerina.com> wrote in message
news:bq**********@newshispeed.ch...

"Generic Usenet Account" <us****@sta.samsung.com> wrote in message
news:90************************@posting.google.com ...
| 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

[Unforgiven]

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

[Jon Bell]

In article <z5********************@comcast.com>,
Gary Labowitz <gl*******@comcast.net> 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 <jt*******@presby.edu> Presbyterian College
Dept. of Physics and Computer Science Clinton, South Carolina USA

[Gary Labowitz]

"Jon Bell" <jt*******@presby.edu> wrote in message
news:bq**********@jtbell.presby.edu...

In article <z5********************@comcast.com>,
Gary Labowitz <gl*******@comcast.net> wrote:

Does this mean that it is bad behavior to put an object into two differentcontainers, 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

[Generic Usenet Account]

jt*******@presby.edu (Jon Bell) wrote in message news:<bq**********@jtbell.presby.edu>...

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]

us****@sta.samsung.com (Generic Usenet Account) wrote in message news:<90*************************@posting.google.c om>...

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