Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL Question: Safe to use elements after erasing them from the collection?

Reply
Thread Tools

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

 
 
Generic Usenet Account
Guest
Posts: n/a
 
      12-05-2003
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
 
Reply With Quote
 
 
 
 
Ivan Vecerina
Guest
Posts: n/a
 
      12-05-2003
"Generic Usenet Account" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ...
| 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


 
Reply With Quote
 
 
 
 
Gianni Mariani
Guest
Posts: n/a
 
      12-05-2003
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.

 
Reply With Quote
 
Gary Labowitz
Guest
Posts: n/a
 
      12-05-2003
"Ivan Vecerina" <(E-Mail Removed)> wrote in message
news:bqqd6o$ord$(E-Mail Removed)...
> "Generic Usenet Account" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) ...
> | 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


 
Reply With Quote
 
Unforgiven
Guest
Posts: n/a
 
      12-05-2003
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


 
Reply With Quote
 
Jon Bell
Guest
Posts: n/a
 
      12-05-2003
In article <(E-Mail Removed)>,
Gary Labowitz <(E-Mail Removed)> 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 <(E-Mail Removed)> Presbyterian College
Dept. of Physics and Computer Science Clinton, South Carolina USA
 
Reply With Quote
 
Gary Labowitz
Guest
Posts: n/a
 
      12-05-2003
"Jon Bell" <(E-Mail Removed)> wrote in message
news:bqqgk4$f42$(E-Mail Removed)...
> In article <(E-Mail Removed)>,
> Gary Labowitz <(E-Mail Removed)> 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


 
Reply With Quote
 
Generic Usenet Account
Guest
Posts: n/a
 
      12-21-2003
http://www.velocityreviews.com/forums/(E-Mail Removed) (Jon Bell) wrote in message news:<bqqgk4$f42$(E-Mail Removed)>...

> 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;
}
 
Reply With Quote
 
Generic Usenet Account
Guest
Posts: n/a
 
      01-03-2004
(E-Mail Removed) (Generic Usenet Account) wrote in message news:<(E-Mail Removed) 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
STL - erasing from a set A B C++ 5 11-19-2010 08:17 PM
STL - erasing from a set A B C++ 5 11-18-2010 08:08 AM
erasing from stl list Krzysztof Poc C++ 10 01-22-2010 09:11 AM
Conditional erasing elements from list - in a loop Tescobar C++ 12 07-25-2005 03:14 AM
Erasing map elements by iterator Owen Brydon C++ 5 10-16-2003 04:40 PM



Advertisments