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

Question

I've got a std::vector which I need to sort by selected algorithms for certain operations, but to maintain its original state (e.g. items ordered by when they were entered) the rest of the time.

Obviously I can use std::copy to create a temporary vector and sort that, but I'm wondering if there's a better way, possibly by timestamping the items entered.

Cheers

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

You can create another vector to store the indices. Here is the code:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    vector<int> numbers = {50,30,20,10,40};
    vector<int> indexOfNumbers;
    
    for(int i = 0; i < numbers.size(); i++)
    {
        indexOfNumbers.push_back(i); 
    }
    // Now, indexOfNumbers = [0,1,2,3,4]

    std::sort(
        indexOfNumbers.begin(), indexOfNumbers.end(), 
        [numbers](int leftIndex, int rightIndex) 
        { 
            return numbers[leftIndex] < numbers[rightIndex]; // sort in ascending order
        }
    );
    // After sorting, indexOfNumbers = [3, 2, 1, 4, 0]

    // Access the sorted elements
    cout << "Accessing the sorted elements : ";
    for(int i = 0; i < numbers.size(); i++)
    {
        cout << numbers[indexOfNumbers[i]] << " ";
    }
    // prints numbers in sorted order i.e. [10,20,30,40,50]
   return 0;
}

Source: Made slight modification according to Tyrer's answer (https://stackoverflow.com/a/47537314)