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 ?
4 Answers
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.
4 Comments
cyrux
So this way , the list size (memory start and memory end locations) remains as is , its just that one element is removed/invalidated. isnt it ?
Baiyan Huang
I am curious of your comments on list usage in real life ---- It is in STL for its reasons, as you said: insert or remove any element in constant time
GManNickG
@cyrux: Yes, the linked list will remove that element only, the others are valid. @Dbger: The standard library includes it because it's such a common data structure, and because it does have its uses. But those uses are few; your main operation would basically be iterating through the container and removing elements frequently, and doing that frequently. The terrible cache-coherence it has along with linear access times make it very slow in practice; even if you erase something from the middle semi-often, a
vector/deque will perform better because of locality.
sellibitze
"list...they're pretty awful". I dunno. I find the guarantees std::list makes w.r.t. iterator validity, O(1) complexities etc pretty nice.
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);
Comments
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.
1 Comment
cyrux
you say that I am holding object of type T by value, but in the stl_list the push_front has this prototype void push_front(const value_type& __x). So isnt this holding reference, is this same as value. Also, in the other place when i said i hold reference, i was actually using pointers and that i believe was causing the problem. So you say that if I used list of shared_ptr , then I can remove and add elements and my references to these elements would work fine. Does this hold if I change the ordering of elements in list, like use pop_front to get element and then push_back ?
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!
