C++ list removal
Community Forums/General Help/C++ list removal
| ||
| 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. |
| ||
| http://www.cplusplus.com/reference/stl/list/remove/ |
| ||
| That would have to iterate through the entire list to remove an element. |
| ||
| Is there a faster version bmx has? Or are you talking about TLink::remove? |
| ||
| 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 |
| ||
| 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 |
| ||
| 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. |
| ||
| 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 |
| ||
| your comment to this link makes no sense So.. what? Last edited 2011 |
| ||
| Oops, wrong end of the stick, sry. |
| ||
| 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. |
| ||
| 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 |
| ||
| 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 :) |
| ||
| 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 |
| ||
| If you don't find the answer you are looking for, try at GameDev.NET. Lovely people there too; many are C++ experts. |
| ||
| 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 |
| ||
| list.push_back(65) list.push_back(32) list.remove(65) |
| ||
| We've been over this. Removing elements by value is slow. |
| ||
| Your code from #16 looks pretty solid, does it work? |
| ||
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); |
| ||
| Well, thats nice to know and clears things up, thanks. |
   |