• 11
• 9
• 10
• 9
• 10

# best container for fast delete's?

This topic is 4979 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

hi, in my engine i have a "master list" of all my objects which Update(). i store them all in a std::list. anyway, im constnatly adding things to this list and removing things from random positions. i figured a std::list was best for this situation. but i recently read that if i dont care about the order which they are stored (i dont), a std::vector is better. the trick is to put the items which are to be deleted in the back of the vector, then just pop_back(). is this true? if so, how exactly is it done? do i use 2 seperate vectors or something? just a little curiouse because things like this usually heavily effect performance. thanks for any help!

##### Share on other sites
One thing I did was to have an array of pointers. If I want to delete an object, I just move the last entry over the one I want to delete.

usedObjectCount--;
objects[deleteIndex] = objects[usedObjectCount];

While this will move an object over itself if it's the last entry, this isn't a big deal. There should be no negative side effects, and it sure beats throwing in an if statement.

objects[usedObjectCount] = newobjectptr;
usedObjectCount++;

##### Share on other sites
The usual trick when you don't care about the order is to swap the element you want to remove with the element at the last position. If you're just storing pointers to objects then thats just a pointer swap and dead fast. Then you can simply remove the last element, and since vectors are usually implemented as a dynamically growing array that just involves reducing the size of the container by one.

Personally I'd just bung them all in a set of some kind and leave it to do its thing. If it later turns up after profiling (and only if!) then you can think about doing some sneaky tricks.

##### Share on other sites
Well, if you use std::remove on your vector, or better yet, std::remove_if then it will return an iterator to the new end of the vector. From there you just do an erase on the vector. Of course, this works best if you just run the remove/remove_if once, and not once per element you want to remove. In the later case you would just use std::swap and swap the last item (end - 1) with the current and then pop_back.

##### Share on other sites
What Washu said. I can't image, though, that your container would have all of its objects that need erasing grouped together--would they be interspersed randomly throughout the container? If so, that's a lot of swaps. I'd think the list would be the way to go in this case. However, if by some magic on your side you'd be able to do a remove at the end of the container all in one contiguous chunk, vector should be faster.

edit: didn't even think about them being pointers. I swore I'd never post on Fridays anymore. Swapping should be dead fast, as the prior poster said, so remove/remove_if should serve you well.

edit2: one thing to be very careful about: if this container "owns" the pointers, you have to make sure you delete them before you use remove. remove may very well overwrite values in the "unused" portion of the vector, so you won't be able to recover the pointer after you remove it.

##### Share on other sites
hey guys, thanks for your replies.

im a little confused on exactly how to do this then.. you say to use remove or remove if, but this seems to just remove an item from a container.. wouldnt this be why im doing pop_back() ?? maybe an example would help... i was under the impresion i would swap() the to be deleted item with the back() item, then pop_back(), so where does remove come in? lastly, do you think this will definetly be faster then just using a std::list and removing from random spots? and yes, this is pointers im dealing with. thanks again!

myvec.erase(newend, myvec.end()); //newend is iterator returned from std::remove