# 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 on other sites

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 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 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 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 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 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 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 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 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.

## Create an account

Register a new account

1. 1
2. 2
Rutin
19
3. 3
4. 4
frob
14
5. 5

• 12
• 9
• 17
• 16
• 9
• ### Forum Statistics

• Total Topics
632596
• Total Posts
3007323

×