Jump to content
  • Advertisement
Sign in to follow this  
noodleBowl

C++ Vectors: Sorting and removing specific items

Recommended Posts

I'm looking at a new approach for rendering stuff where basically I have this std::vector of renderables. At some point renderables are added to the vector and when it comes time to draw they're sorted and drawn. But I have a few fuzzy parts:

1. I know there is std::sort function where you can give a compare function, but its signature wants a bool. So what happens if the 2 objects I'm comparing are considered equal? I know in other languages they return 1 for greater then, 0 for equal, and -1 for less then

2. What's best/quickest way to remove a specific item from my std::vector<Renderables*>? Would it be better to have a map since I want to remove specific items? How would this effect sorting and traversing the map if this is the case?

 

Edited by noodleBowl

Share this post


Link to post
Share on other sites
Advertisement

std::sort wants a compare function that acts like the less-than operator. http://www.cplusplus.com/reference/algorithm/sort/

There are many different ways you could remove an item from a vector depending on whether you have to find it first, whether you want to preserve the order after removal, whether it's easier for you to just create a new vector with a copy of only the elements you don't want to keep, etc.

Share this post


Link to post
Share on other sites
6 hours ago, noodleBowl said:

2. What's best/quickest way to remove a specific item from my std::vector<Renderables*>?

If you're doing sorting, you could mark them as the biggest, so they end up at the very end of the vector, where deletion is simpler.

Share this post


Link to post
Share on other sites
19 hours ago, noodleBowl said:

2. What's best/quickest way to remove a specific item from my std::vector<Renderables*>? Would it be better to have a map since I want to remove specific items? How would this effect sorting and traversing the map if this is the case?

Depends slightly on details.

If ordering is not important, the typical method is to swap with the tail then remove the tail. 

If ordering is important and the size is large enough that removing items is a concern, use another container. Several std::deque implementations use small segments that can be removed at a fairly small cost, it is only the cost to move the remaining portion of the sub-array.

Share this post


Link to post
Share on other sites
1 hour ago, frob said:

If ordering is not important, the typical method is to swap with the tail then remove the tail. 

I like the idea behind swapping with the end, but I'm not sure how you actually do that

Unless I'm missing something don't I still need to loop through the vector until I find my item to remove? Even then couldn't I just remove it at that point?

I guess when I read this I think of the find being auto handled somehow, so it just becomes a simple swap and erase

Edited by noodleBowl

Share this post


Link to post
Share on other sites
55 minutes ago, noodleBowl said:

I like the idea behind swapping with the end, but I'm not sure how you actually do that

auto it = std::find_if(v.begin(), v.end(), finder());
if (it != v.end())
{
  std::swap(*it, v.back());
  v.pop_back();
}

 

1 hour ago, noodleBowl said:

Unless I'm missing something don't I still need to loop through the vector until I find my item to remove? Even then couldn't I just remove it at that point?

I guess when I read this I think of the find being auto handled somehow, so it just becomes a simple swap and erase

Yes, you still need to find the item. The difference is that removing an element from the middle of a vector will force all the items after it to move up by 1, while removing the last element won't cause any shifting at all (since there's nothing after it).

Even though the operation is still O(n), there's no reason to perform the extra work if you know it can be avoided. This trick doesn't work for sorted data, but again there might be a better container option in that case. More information is always helpful :)

Share this post


Link to post
Share on other sites
13 minutes ago, noodleBowl said:

I like the idea behind swapping with the end, but I'm not sure how you actually do that

Unless I'm missing something don't I still need to loop through the vector until I find my item to remove? Even then couldn't I just remove it at that point?

I guess when I read this I think of the find being auto handled somehow, so it just becomes a simple swap and erase

Yes you need to find the item you want to remove.

If the vector is sorted you can use a binary search, otherwise you have to do a linear search.

Swapping the item to the end before removing it will make removal faster but after that the items are unsorted and finding further items then requires a linear search. You could remove the item and move all the following items down to keep the array sorted which makes subsequent searching faster but remove is slower. You could simply mark items as removed and leave them where they are,then the array stays sorted but at the expense of keeping the additional items around.

It's all trade offs and the most optimal solution depends on how many items you'll be working with, how often you need to add and remove items, etc.

 

Share this post


Link to post
Share on other sites
2 hours ago, Zipster said:

Even though the operation is still O(n), there's no reason to perform the extra work if you know it can be avoided. This trick doesn't work for sorted data, but again there might be a better container option in that case. More information is always helpful :)

1 hour ago, DerekB said:

It's all trade offs and the most optimal solution depends on how many items you'll be working with, how often you need to add and remove items, etc.

Definitely there are trade offs everywhere. Originally I was thinking a map, because I could remove items really fast. But then (i'm pretty sure) that means I loose out on my sorting. Unless I do something crazy like copy the map into a vector. But doing that every frame sounds pretty bad.

Just using a vector seems like my best bet (not sure if there is a better container or some combo like using a vector and a map together), because I can sort, which is my main goal. But I loose out on performance when I want to remove items and they will then become unsorted. I think the unsorted part is only an effect of the swap. If I were to remove an item at the point of finding it everything would have to just have to shift, but we would still be sorted. Not really sure why shifting a spot is such a hit to performance though

Just in to be super clear I'm looking at a dataset like this where 

Before the sort

//Unsorted
cubeRenderable    | { shader: 1, texture: NULL }
truckRenderable   | { shader: 2, texture: truckTexture }
enemyRenderable   | { shader: 3, texture: enemyTexture }
boatRenderable    | { shader: 2, texture: boatTexture }

After we sort, done when the vector of renderables is flagged as "dirty"

//Sorted. Sort by shader then by texture
cubeRenderable    | { shader: 1, texture: NULL }
truckRenderable   | { shader: 2, texture: truckTexture }
boatRenderable    | { shader: 2, texture: boatTexture }
enemyRenderable   | { shader: 3, texture: enemyTexture }

Removal of an item

TruckRenderable *truckRenderable;
RemoveRenderItem(truckRenderable);

//During the remove method the vector now looks like this. Before actual removal 
cubeRenderable    | { shader: 1, texture: NULL }
enemyRenderable   | { shader: 3, texture: enemyTexture }
boatRenderable    | { shader: 2, texture: boatTexture }
truckRenderable   | { shader: 2, texture: truckTexture }

//After actual removal. We are unsorted and will have to sort again
cubeRenderable    | { shader: 1, texture: NULL }
enemyRenderable   | { shader: 3, texture: enemyTexture }
boatRenderable    | { shader: 2, texture: boatTexture }

Maybe I'm just over complicating everything :(

Edited by noodleBowl

Share this post


Link to post
Share on other sites
10 minutes ago, noodleBowl said:

Maybe I'm just over complicating everything

To be honest I think you might be :)

The best bet is to do the simplest thing that works. Put all of your renderables into a vector, when you're ready to draw them sort the vector. Radix sort is commonly used in this scenario.

If you need to remove renderables which were previously added then just remove them from the vector.  You might as well use the swap and erase trick to avoid lots of needless memory shuffling. Unless you are removing a lot of renderables from a large collection the linear search for the renderable to remove will probably not be an issue.

You'll probably find that's good enough to ship.

Share this post


Link to post
Share on other sites

Don't remove things from the list. Throw the whole thing away after you've rendered it and build a new list from scratch next frame. 

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  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!