Sign in to follow this  
graveyard filla

best container for fast delete's?

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 this post


Link to post
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.

to add an object:

objects[usedObjectCount] = newobjectptr;
usedObjectCount++;

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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!

Share this post


Link to post
Share on other sites
With vectors, and deques, remove and remove_if actually move the elements that match to the end of the container. It then returns an iterator to the new end of the container. So the items haven't actually been removed at all. In order to erase them, you just do:

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

Now, this is different than the list remove, which actually does remove the elements from the list.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this