Are you sure you certainly need a vector?

If your elements are unique, you could use an std::set or std::map, which both offer sorting, you'd only have to roll your own compare-function.

-make a single linked list (one that uses a preallocated array, instead of just spitting the elements onto the heap)

-loop through your original vector and start adding the elements to the list(or pointers to the elements)

like:

for( vector size)

list_array = &(original_vector);

then start iterating through your list ....now not by using an array index, but normally with a list iterator. When you find the first element that is smaller/larger than your newly added element finish the insertion by setting the pointers.(as you normally insert an element into a linked list)

Now the slow part here is that for every newly added element you have to iterate through your list. You speed this up by saving the pointer(a list iterator basically) to every 50th or 100th element into a samaller array. ....so before you start iterating through the list, you loop through this smaller array to find the closest pointer(list iterator).

Probably Ive explained it in a crappy way but I used this to sort my models for the rendering queue and it was freakin fast.

Hi.
Currently I'm trying to find managable and efficient way for filling and sorting a std::vector.
The case is as follows:

Typedef struct Thing
{
int value_a;
int value_b;
int value_c;
}

std::vector<Thing> myThings;

Option 1:
- I randomly fill the vector
- sort the order of items in the vector based on value_b lowest to highest combined with value_c highest to lowest

How would I do that?

Option 2:
- fill the vector in the right order (sort the seperate source data earlier)

Option 2 is what I do at the moment.

My questions:
- is sorting existing content of a vector efficient versus refilling the whole vector?
In my case the content of the vector varies a lot, it contains visuble renderables of a frame in my 3d engine.
- do you know any good articles/ documentation on sorting vectors based on sorting items within in this case a struct?
- is a struct in this case the best way to go, or would you prefer making a hashing table and sort only that?

Is this a case of pre-mature optimization? Is your currently implementation running too slow, and have you identified it as the actual bottleneck of your rendering, by using profiling tools? Optimizing areas that aren't the bottleneck, while nice, usually isn't as effective as optimizing the actual bottlenecks.

Assuming this is actually actually a bottleneck, does the vector order really change every frame, or can you get by with resorting it only every other frame or every third frame? (Instant 50% or 66% saving off your bottleneck right there).

Is a known portion of the vector at a greater distance from the player, and less critical to be sorted properly?

Could you say, split the vector into two or more vectors, where one vector just contains the stuff that is within 50 feet of the player, and the other contains stuff that is greater than 50 feet away?

You could sort the 'near object' vector every frame, and use a continual bubble sort to gradually sort the 'far object' vector bit by bit every frame. If most your objects are at a distance, and objects at a distance are less likely to need to be resorted anyway, this might get you a decent performance gain without a serious cost to your visuals. If this is actually your bottleneck.

The benefit of bubble sort also means you can just swap the two adjacent elements instead of trying to find and re-insert them, which causes an avalanche of having to move other elements to make room.

(Note: You don't actually have to use two real vectors, that's just for explaining. The data can actually be in a single vector, but have a cutoff point)

Are you sure you certainly need a vector?

If your elements are unique, you could use an std::set or std::map, which both offer sorting, you'd only have to roll your own compare-function.

Well, if he's using the vector to store renderables, the benefits of vector's iteration might outway the benefits of map sort-when-inserting. Especially so if the OP properly leverages the benefits of vector elements being in contiguous memory, which OpenGL and DirectX take advantage of.

What of

std::sort (std::begin(/*vector name*/), std::end(/*vector name*/))

?

He's not asking how to sort an already filled vector. You need to learn to read a question before you attempt to answer it.