ansaurus

Question

What's a good way of *temporarily* sorting a vector?

Answer 1

+15 A:

You could create a std::vector that holds all the indexes of the first vector. You could then sort the index-vector as you like. This should be fast and most importantly, doesn't mean you have to copy the first vector (which is probably more costly!).

monoceres 2010-02-22 17:33:05

+1 for fastest fingers, was posting more or less the same answer.

Binary Worrier 2010-02-22 17:36:13

I would have used an old fashioned malloc'd array of pointers and called qsort but this works too.

Joshua 2010-02-22 17:47:13

@Joshua: most of the time, this will work better -- qsort is usually quite a bit slower than std::sort.

Jerry Coffin 2010-02-22 18:02:41

I bet generating the vector of indices takes longer than copying the original vector!

2010-02-22 19:28:22

I'll take that bet, @Stingray. I get to provide the class we're storing in the vector. (In particular, I get to define the copy constructor and assignment operator.) I also get to choose how many of them we're storing. (Lots!)

Rob Kennedy 2010-02-22 20:33:46

@Rob: Sorry, I was assuming POD types...

2010-02-22 21:14:58

Sounds good, could you describe how to do that? Code example would help.

deworde 2010-02-23 16:12:06

Answer 2

+2 A:

Any given vector will be sorted in at most one way at any time.

There are two alternatives:

Copy to a temporary vector and sort that as desired. Unless the vector is very large and you've got limited space, this is almost certainly the best way. Even if you're concerned about performance, the cost of making a copy is going to be smaller than the cost of sorting, and if the cost of copying is significant the sorting's going to be a lot slower than the copying.

Alternatively, you could keep some way (the timestamp you mentioned?) of being able to sort the vector back to the original order. This is going to be slow, since you'd only want to do this if the vector was very large, but if you can't make a temporary vector this is the only way to do it.

David Thornley 2010-02-22 17:33:12

Copying could be expensive if it's not a vector of pointers, also depends on how the copy ctor is implmented.

Binary Worrier 2010-02-22 17:37:35

@Binary Worrier: I think David's point is that the sort operation on the vector does a bunch of copies when it's moving elements around. If the sort is O(n log n) adding an O(n) copy operation initially doesn't change the overall time complexity.

Michael Burr 2010-02-22 18:15:41

If copying is expensive, then sorting is more so. How do you expect to get a sorted vector without copying each element to its new place? (Actually, the copy constructor could be far more expensive than the assignment operator, in which case the proper thing to do is to fix the copy constructor. I'm not thinking of any case where the copy constructor should be that much more expensive.)

David Thornley 2010-02-22 18:18:08

By a) sorting a vector of pointers or b) indirectly sorting the vector by sorting an array/vector of ints that map to the positions of the objects in the original vector. No copying.

Binary Worrier 2010-02-22 22:11:52

Answer 3

A:

Whatever item you are sorting, you could wrap it in a structure that has multiple sort-fields.

struct someThing
{
    int sortOrder1;
    int sortOrder2;
    ...
    int sortOrderN;
    //payload data object here
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear

(or maybe add the sort orders to the base structure itself?)

Then when you need can calculate the different sort orders, and re-order your list depending on which sort-order you need.

FrustratedWithFormsDesigner 2010-02-22 17:33:57

Answer 4

+4 A:

If you don't mind a little bit of Boost you can use the MultiIndex library. See this answer from me where you'll find some example code.

Basically, it allows you to keep several "views" of the same data, each with a different order. In your case you'll be able to keep a "sequence" view, where the data is in order of insertion (like a vector) and a "sorted" view in which the data is sorted according to some criterion (like a map).

Manuel 2010-02-22 17:42:22

Answer 5

A:

I suggest storing smart pointers, to the original data, in each vector. std::vector allows you to supply different methods for sorting. Also, with smart pointers, they will be destroyed automatically when all references to the item are removed.

Thomas Matthews 2010-02-22 18:12:46

ansaurus

tags:

views:

answers:

What's a good way of temporarily sorting a vector?

related questions