Problems with C++ containers

Question

I have a std::list in a C++ program, which contains objects of a Class A. Lets say I have 10 objects in it. I have a reference to the 6th object stored, in another data structure say ref_6. Lets say I need to remove the 8th element from my list. To do this, I would use pop_front 8 times and store 8 objects in a vector and use push_front 7 times to insert the first 7 elements back in the list so now my resulting list would have 9 elemnts. Now i when i try to access the object stored in ref_6 , which was the 6th element , I cant do it. There is some garbage value in this reference. I am assuming that when i do a pop and a push, the memory location of the same object changes . How do I deal with this ?

Answer 1

Why would you erase things in such a manner? D: It's not a stack. The entire point (and only point*) of a list is that you can remove any element in constant time. (Though finding it is linear.)

Just do this:

typedef std::list<T> list_type;

list_type mylist; // populate it

list_type::iterator iter =  mylist.begin();
std::advance(iter, 8); // move to 8th item

mylist.erase(iter); // erase it

And no other iterators are invalidated. (Indeed, erasing an element invalidates any references to it.)

---

*You probably shouldn't even be using a list. Lists are nice when it comes to learning data structures, but they're pretty awful.

Answer 2

The list stores its elements in discontinous chunks of memory that get freed when the element is removed from the list. So the reference ( which is implemented simply as a pointer ) points to an element whose memory has been already freed.

Easier way to remove a given element from the list is to get the iterator pointing to it and use method

std::list::iterator = /*somehow get the iterator to the 8th element*/
yourList.erase(8th_element_iterator);

The first step ( getting the iterator to the 8th element ) can be done for example by getting the iterator of the begininning of the list and advancing it 7 positions forward:

std::list::iterator first_iter = yourList.begin();
std::list::iterator 8th_iter = std::advance(first_iter, 7);

Answer 3

Something smells fishy here... You are storing object of type T in a std::list<T> by value. You keep references to those objects in other places. Is that correct? If yes, I see several problems... Many manipulations of lists might invalidate stored references, since std::list<T> only guarantees a sequential order of values of elements of type T. If you want to store references to those elements in several places use std::tr1::shared_ptr<T> and std::list<std::shared_ptr<T> >. Then, you can safely remove or add (even reposition) elements in your list and the references kept in other places remain valid. Beware of storing std::list<T>iterators, the problem would be the same.

Answer 4

I am referring to your response. Sorry, I didn't get the account thing right... Please consider the following:

std::list<A> tList;
A tA;

tList.push_back(tA);
assert(&tA == &tList.back()); // boom!

A *tAPtr = &tList.front();

tList.erase(tList.front());
// try to access tAPtr:
tAPtr->Foo(); // boom! (probably)

The point is that instances of A are stored by value (= copied), so what you are doing is inherently unsafe. Use std::list<std::tr1::shared_ptr<A> > instead!