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

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

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

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.