• Advertisement
Sign in to follow this  

Sorting an std vector

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a stl vecor of objects (Objects) that i'd like to sort according to their x positions. but since many of the objects dont't move from frame to frame i thought that it's be faster to save a different vector (MovedObjects) of all the objects that move, then to sort Objects i'd remove all the objects in MovedObjects from Objects, sort then, and then merge them back in. Can anyone show me how to do that using std commands? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
All that removing from and merging to a vector will probably cost you much more than simply sorting the whole thing (remember, all the elements following the inserted/removed one must be moved). If profiling tells you that the sorting is a bottleneck in your code (which it almost certainly is not), you might try bubblesort which, although in general case slower than std::sort, is very fast if the vector is already almost sorted.

Another option might be storing your objects in a std::multiset which will take care of the ordering automatically, and has a very fast (logarithmic) insertion/removal. But as I said, do profile first, then optimize based on what the profile tells you.

Share this post


Link to post
Share on other sites
This can be done in-place by using stable_partition to separate the objects that moved from the objects that didn't move, sort to sort the ones that moved, and then inplace_merge to merge them back together.

itr i = stable_partition(start, end, not(object_moved));
sort(i, end, object_x_position);
inplace_merge(start,i,end);

Where object_moved is a predicate that returns true if an object has moved.

Doing this with multiple vectors (not in-place) would be a bit trickier since I think it would require doing some stuff that the STL doesn't provide algorithms for. In either case there's going to be a lot of copying going on.

You could also implement an insertion sort, since insertion sorts do well with lists that are already mostly sorted.

I doubt that these methods will do much better than a std::sort, if they even do better at all.

If a lot of objects never move then it could be better to permanently keep such objects on a separate list.

Share this post


Link to post
Share on other sites
Good grief.

1) Yeah, don't worry about this. Just call std::sort.

2) If you're really concerned about using a sort that handles almost-sorted things well, don't use bubble sort. Use insertion sort. Oh wait, std::sort already does that past a threshold. Yeah, just use std::sort.

3) In case it wasn't clear, just call std::sort.

Share this post


Link to post
Share on other sites
If your object positions don't vary too much per frame, consider using a sorting algorithm that runs in O(n) in the case where the vector is already sorted. That way, if only a few objects have moved, the sorting finishes quite quickly still.

If you have profiled that sorting is the biggest performance killer, try some other sorting algorithm. I sort my particle systems using a small variation of Cocktail(shuffle, bidirectional bubble) sort on the CPU, which I profiled to be faster in my case than std::sort or my implementation of insertion sort or quicksort.

But if sorting is not the performance issue, don't waste your production time thinking about it, just use std::sort as already mentioned. Using several vectors and merging sounds like suboptimal.

Share this post


Link to post
Share on other sites
Be aware that sorting any STL container involves a lot of copying. If the object has an involved copy-constructor, this could mean a big performance penalty.

Unfortunately, the only general solution is to change the program's design, often making the switch to a container (in your case, vector) of pointers to objects.

A compromise, which sometimes removes the need to rewrite, is to provide a custom allocator so that the sort creates binary copies of the objects (without allocating/deallocating memory or creating/destroying resource). This is safe insofar as the sort only permutes the elements, meaning that reference counts remain unchanged. However, hidden monsters lurk within, so tread carefully.

Admiral

Share this post


Link to post
Share on other sites
Interestingly, the MSVC2005 standard library implementation of std::sort uses a combination of quick sort, heap sort and insertion sort.

Of more immeaditate interest is that it also uses a mixture of std::iter_swap (in the quicksort) and assignment(in the insertion sort) to move objects around. Therefore, it should be possible to improve on the MSVC2005 std::sort in the case that objects are expensive to copy, but cheap to swap, by using a sort can be implemented as swaps rather than assignments instead of insertion sort.

However, really don't obsess to much about it if you're trying to make a game. I only give this kind of thing a second thought because it interests me, not because I think it will realistically be useful.



Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
Be aware that sorting any STL container involves a lot of copying.


Not std::list :)

Quote:
If the object has an involved copy-constructor, this could mean a big performance penalty.


It has to be pretty involved indeed to outweigh the benefits of cache coherency, though, AFAIK.

Quote:
Unfortunately, the only general solution is to change the program's design, often making the switch to a container (in your case, vector) of pointers to objects.


That is what the boost::ptr_containers are for :)

Quote:
A compromise, which sometimes removes the need to rewrite, is to provide a custom allocator so that the sort creates binary copies of the objects (without allocating/deallocating memory or creating/destroying resource). This is safe insofar as the sort only permutes the elements, meaning that reference counts remain unchanged. However, hidden monsters lurk within, so tread carefully.


You know, I'm starting to think that the language doesn't really need move constructors as much as it needs better support for *swapping*. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
You know, I'm starting to think that the language doesn't really need move constructors as much as it needs better support for *swapping*. :)
A very interesting comment. I think I'll chew on that for a bit.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
Be aware that sorting any STL container involves a lot of copying. If the object has an involved copy-constructor, this could mean a big performance penalty.


Vectors and deques, yes. Lists, no. Sets and maps (and multisets and multimaps) are always sorted. tr1::unsorted_map and tr1::unsorted_set (which I believe are the same as boost::hash_map and boost::hash_set) can never be sorted.

All of which suggests another possible answer to the original question: rather than having a vector of objects, it might be better to use a set, as they will be sorted on insertion. Two things to mention: first, pushing back into a vector then std::sort-ing is often quicker than inserting into a set (depending on the cost of the copy constructor), though not always. Second, it sounds like the sort value for these objects can change over time, in which case a set would be inappropriate (the objects would have to be removed then re-inserted every time their sort value changed). So I mention this only as a possibility.

Finally, if copy constructors really do make std::sort too expensive (I suspect they wouldn't), the vector could store smart pointers to the objects instead of the objects themselves.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
You know, I'm starting to think that the language doesn't really need move
constructors as much as it needs better support for *swapping*. :)


Isn't that what overloading std::swap is for?

Share this post


Link to post
Share on other sites
Some of you are forgetting that he is using objets whose x positions change, and since x is the sort key, you don't want to use a container such as a set as it would require removal, modification, and reinsertion of each item. Each object shouldn't have to know that it is even in a set, which it would clearly need to know here.

The best thing would be to use a vector and an algorithm that works very well on almost sorted data. Obviously a good choice is std::sort, and if profiling suggests you need something faster, then an algorithm more suited to an almost sorted array could be implemented, such as Insertionsort.

There are plenty of other good algorithms for this purpose too. Inserting items into a splay tree for example, is another fast way (at least in terms of comparisons) of sorting almost sorted data, or data with obvious patterns. Unfortunately it takes quite a bit of extra RAM.
The thing is, you don't want to go to all that extra trouble of implementing something else if you already have an option with sufficient performance.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kylotan
Quote:
Original post by Zahlman
You know, I'm starting to think that the language doesn't really need move
constructors as much as it needs better support for *swapping*. :)


Isn't that what overloading std::swap is for?
Ah yes, but the syntax to call that isn't nearly as nice as
a = b;

If there was a swap operator, then things would be a whole lot different.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Quote:
Original post by Kylotan
Quote:
Original post by Zahlman
You know, I'm starting to think that the language doesn't really need move
constructors as much as it needs better support for *swapping*. :)


Isn't that what overloading std::swap is for?
Ah yes, but the syntax to call that isn't nearly as nice as
a = b;

If there was a swap operator, then things would be a whole lot different.


Indeed. Further, if we add a simple heuristic like "if there's a specialized swap for this object, it must be because swapping is faster than assigning or copying; therefore, if the RHS of an assignment of those objects is dead, do a swap instead", then we sidestep all that (N)RVO analysis business quite nicely, and potentially optimize in other contexts as well.

Of course, a move constructor would presumably perform a little better in general than a "swap construction" consisting of default-construction and a swap, but this seems like most of the gain for much less work. (Plus we don't have to hack around in the compiler to skip the dtor of the constructed-from, dead object; nor in the client code to clean up any old stuff in an assigned-to object, in the assignment case.)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement