Algorithms for traversing a collection in sorted order without modifying the collection?

Let us say we have a collection like the following: {12, 10, 4, 5, 7}

I'd like to preserve the order of the collection so the indices will remain consistent but traverse the collection in a sorted order like so {12, 10, 7, 5, 4}.

What I've thought of is to make another collection of pointers to the elements and then sort the pointers.

What are your thoughts? Has an algorithm like this already been implemented in C++?

Edit: In my case, I have a vector<vector<doubl开发者_StackOverflow中文版e>> and I would like to traverse the outer-vector collection in non-increasing order based on the sum of the inner-vectors.

If you want to maintain both orders as an ongoing thing, while elements are added and removed, then you could use boost multi-index:

http://live.boost.org/doc/libs/1_34_0/libs/multi_index/doc/tutorial/basics.html#multiple_sort

This example from that page is pretty much what you want, except sorted in the opposite order:

multi_index_container<
  int,
  indexed_by<
    sequenced<>,           // sequenced type
    ordered_unique<identity<int> > // another index
  >
> s;

If you just want it as a one-off operation, your idea of sorting the pointers sounds fine. As a slight variant, you could create a vector of std::pair<int,size_t>, each pair consisting of a value followed by its index. Then sort the vector of pairs with std::sort and specify std::greater<std::pair<int,size_t> > as the comparator.

Edit:

Given your actual case, I would definitely advise sorting pairs, because that way you only have to compute the sum of each inner-vector once, and store it in the pair. If you were sorting just pointers/indexes, you'd have to calculate two sums for each comparison. so:

typedef vector<vector<double> >::const_iterator It;
typedef pair<double, It> Pair; 

vector<Pair> pairvec;
pairvec.reserve(input.size());

for (It it = input.begin(); it != input.end(); ++it) {
    // some people would split this over multiple lines
    pairvec.push_back(make_pair(accumulate(it->begin(), it->end(), 0.0), it));
}

sort(pairvec.begin(), pairvec.end(), greater<Pair>());

Then you can iterate over pairvec. Make It a non-const iterator if you need to.

One of the ways to do it (for a linked list) is to mentain two levels of pointers: one for original order, and the second for descending, like in

typedef struct node{
    int key;
    struct node* next;
    struct node* next_descending;
};

You could store the index values in an array, then write/adapt a sorting algorithm that sorts the index values based on what they index in the original array.

Not sure what your runtime/memory constraints are, but the most straightforward and practical solution IMHO is to simply insert all items from the std::vector into a std::multiset and just traverse the multiset from beginning to end. The overall runtime would be O(n*log(n)) and would require O(n) extra memory for the multiset.

#include <set>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> data;
    data.push_back(12);
    data.push_back(10);
    data.push_back(4);
    data.push_back(5);
    data.push_back(7);
    multiset<int> sorted(data.begin(), data.end());
    for (multiset<int>::iterator it=sorted.begin();it!=sorted.end();it++)
        cout<<*it<<" ";
    cout<<endl;

    for(vector<int>::iterator it=data.begin();it!=data.end();it++)
        cout<<*it<<" ";
    cout<<endl;
    return 0;
}