C++ list removal

Community Forums/General Help/C++ list removal

JoshK(Posted 2011) [#1]
Is there any way to get fast removal of an object from a list in C++, like BMX has? The C++ list erase function wants an iterator, which makes no sense. If you remove an element from a list, the position of all the elements after it will change.


beanage(Posted 2011) [#2]
http://www.cplusplus.com/reference/stl/list/remove/


JoshK(Posted 2011) [#3]
That would have to iterate through the entire list to remove an element.


beanage(Posted 2011) [#4]
Is there a faster version bmx has? Or are you talking about TLink::remove?


JoshK(Posted 2011) [#5]
Yep.

Unless anyone has any other ideas I am going to have to do my own linkages in each class that needs them:

entity->next
entity->prev


Yan(Posted 2011) [#6]
The C++ list erase function wants an iterator, which makes no sense. If you remove an element from a list, the position of all the elements after it will change.

list::erase - Return value: A bidirectional iterator pointing to the new location of the element that followed the last element erased by the function call, which is the list end if the operation erased the last element in the sequence.


??

Last edited 2011


JoshK(Posted 2011) [#7]
http://www.cplusplus.com/reference/stl/list/erase/

Parameters
All parameters are of member type iterator, which in list containers are defined as a bidirectional iterator type.

position
Iterator pointing to a single element to be removed from the list.
first, last
Iterators specifying a range within the list container to be removed: [first,last). i.e., the range includes all the elements between first and last, including the element pointed by first but not the one pointed by last.


So you provide the position in the list of the item you want removed. How can you find this position without iterating through the list? If you store a position when the item is added to the list, it will be invalidated if another item is removed from the list.


skidracer(Posted 2011) [#8]
1. You can add the same object to a list multiple times.

2. In common scenario objects in lists require removal during iteration of the list, hence iterator pointer is modified and returned by erase

3. http://www.cplusplus.com/reference/stl/list/remove/ - your comment to this link makes no sense

4. to learn C++ buy and read Stroustrup's book http://www2.research.att.com/~bs/3rd.html

Last edited 2011


beanage(Posted 2011) [#9]
your comment to this link makes no sense

So.. what?

Last edited 2011


skidracer(Posted 2011) [#10]
Oops, wrong end of the stick, sry.


beanage(Posted 2011) [#11]
Since you seem to be the C++ Expert in the house, could you explain in a C++-Newbish way what the C++ std::list Equivalent of a TLink is, please? Because, you know, I have no idea.


skidracer(Posted 2011) [#12]
Isn't a TLink basically an instance of an ::iterator?

So you provide the position in the list of the item you want removed. How can you find this position without iterating through the list? If you store a position when the item is added to the list, it will be invalidated if another item is removed from the list.


No, an iterator is not based on position, it is a reference to an instance of an object pointer in a list, and is not invalidated when other items are added or removed from the list. I think of them as pointers with list scope.

The main problem is that any iterators that reference the object you are removing from a list become invalidated.

I prefer to use a deleteme flag in objects and then have only one place in the program where the object list is already being iterated where objects are actually removed and destroyed.

Last edited 2011


*(Posted 2011) [#13]
why not use a Vector for that sort of thing then you can just call Vector[ the one I want to get rid of].erase :)


JoshK(Posted 2011) [#14]
why not use a Vector for that sort of thing then you can just call Vector[ the one I want to get rid of].erase :)

Vectors are arrays. If you have a large array and remove an element somewhere in the middle, the entire memory following that element has to be copied. The advantage of lists is elements can be added and removed quickly, but it is slower to access a single element at any arbitrary position, so you usually iterate through the list operating on each element.

Last edited 2011


Kryzon(Posted 2011) [#15]
If you don't find the answer you are looking for, try at GameDev.NET. Lovely people there too; many are C++ experts.


JoshK(Posted 2011) [#16]
So what would you do, something like this?:

list.push_back(65)
iterator<int> it = list.end()
list.push_back(32)
list.remove(it)//removes 65


Azathoth(Posted 2011) [#17]
list.push_back(65)
list.push_back(32)
list.remove(65)


JoshK(Posted 2011) [#18]
We've been over this. Removing elements by value is slow.


beanage(Posted 2011) [#19]
Your code from #16 looks pretty solid, does it work?


JoshK(Posted 2011) [#20]
This appears to be the right way to do it:
//Declare the list, object, and link
list<Model*> list;
Model* model = new Model;
list<Model*>::iterator link;

//Add object to list and retrieve the link
list.push_front(this);
link = list.begin();

//Remove the link
list.erase(link);



beanage(Posted 2011) [#21]
Well, thats nice to know and clears things up, thanks.