# C++ Vectors: Sorting and removing specific items

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

## Recommended Posts

Just now, Hodgman said:

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.

Yeah, I wondered why the fascination with removing, then I thought maybe it's an occlusion culling pass after first adding everything in the frustum or something. (Personally I'd tackle that by using my occlusion cull to filter the first vector and add things that are not occluded to a new collection, but if @noodleBowl has a need to remove things from the vector then my advice is just do it and worry about performance if it's too slow.)

##### Share on other sites
1 hour ago, noodleBowl said:

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.

std::map is sorted by key, however you would only use this if you need a sorted associative container (which you don't).

1 hour ago, noodleBowl said:

Not really sure why shifting a spot is such a hit to performance though

It's not that it's a hit to performance per se (especially if the items in the vector have move semantics), but rather that in certain cases you can avoid the shift completely, so why bother doing it?

24 minutes ago, Hodgman said:

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.

Agreed. And if you just clear the vector, you'll be able to re-use the memory too.

##### Share on other sites
21 hours ago, Hodgman said:

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.

Not to hijack this thread (hopefully this contributes to the discussion topic), but is that generally always the best option? I'm using a very similar system to OP (vector<Renderable*>), and sorting using insertion sort on every push_back() to enforce draw order. I thought about discarding and re-populating renderables every frame, but I assumed the cost of sorting the entire array every frame was much more expensive than insertion sort on insert + std::erase(std::remove_if()) on removal. I guess I'll just have to run some performance tests and see for myself.

##### Share on other sites
3 minutes ago, cmac said:

Not to hijack this thread (hopefully this contributes to the discussion topic), but is that generally always the best option? I'm using a very similar system to OP (vector<Renderable*>), and sorting using insertion sort on every push_back() to enforce draw order. I thought about discarding and re-populating renderables every frame, but I assumed the cost of sorting the entire array every frame was much more expensive than insertion sort on insert + std::erase(std::remove_if()) on removal. I guess I'll just have to run some performance tests and see for myself.

The performance differences will depend on your game and how many objects get created and destroyed all the time, as well as how much your camera moves.

In my engine I do exactly what @Hodgman says, I just build up the draw list from scratch each frame for each camera that renders.  Then I sort.  I dont assume that my draw list will stay mostly the same, in fact I optimize that stuff for worst cases, because those are the cases where you need most performance.  So I assume that the camera will be moving around and that there's a lot of stuff happening, i.e. a lot of objects being created and destroyed... which means that per-camera draw list will be changing a lot.

BTW I also keep my components in contiguous arrays, so iterating through all mesh components (for example) isnt so bad because the caches and prefetcher will help you out.  If you have stuff all over memory, with your rendering data intermingled with other stuff... then the performance will suffer.

##### Share on other sites
1 hour ago, cmac said:

but I assumed the cost of sorting the entire array every frame was much more expensive than insertion sort on insert + std::erase(std::remove_if()) on removal. I guess I'll just have to run some performance tests and see for myself.

This is what I was thinking! But I guess this makes sense if you are doing a lot of creating and destroying like @0r0d mentions

1 hour ago, 0r0d said:

BTW I also keep my components in contiguous arrays, so iterating through all mesh components (for example) isnt so bad because the caches and prefetcher will help you out.  If you have stuff all over memory, with your rendering data intermingled with other stuff... then the performance will suffer.

Can you elaborate more on this? The part about If you have stuff all over memory, with your rendering data intermingled with other stuff

Example if I have a set up roughly like this does this mean everything is all over?

//Vector of renderables. This is the list we will actually look at and traverse when rendering

//Vector of created shaders. Used to keep track of the shaderes that have been created. Exists in a ShaderManager class

//Vector of loaded textures. Used to keep track of the textures that have been created. Exists in a TextureManager class
truckTexture | { width: 64, height: 64, comPointer: 9 }
enemyTexture | { width: 64, height: 64, comPointer: 10 }
boatTexture  | { width: 64, height: 64, comPointer: 11 }

I kind of feel like it does, but I'm not really sure cause of the pointers and well I have never really taken a hard look at how memory management/cache works

Edited by noodleBowl

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5

• 9
• 12
• 16
• 26
• 10
• ### Forum Statistics

• Total Topics
633769
• Total Posts
3013756
×