Algorithms for moving a collection in sorted order without changing the collection?

Question

Let's say we have a kit similar to the following: {12, 10, 4, 5, 7}

I would like to preserve the order of the collection so that the indices remain consistent but cross the collection in sorted order, for example {12, 10, 7, 5, 4}.

What I thought was to make another set of pointers to elements, and then sort the pointers.

What are your thoughts? Does such an algorithm already implemented in C ++?

Edit: In my case, I have vector<vector<double>>, and I would like to traverse the collection of the outer vector in non-decreasing order based on the sum of the inner vectors.

Answer 1

, , boost-index:

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

, , :

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

, , . std::pair<int,size_t>, , . std::sort std::greater<std::pair<int,size_t> > .

Edit:

, , . /, . :

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>());

. It -const-, .

Answer 2

( ) , : , ,

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

Answer 3

, / , , .

Answer 4

Not sure what your runtime / memory limits are, but the simplest and most practical IMHO solution is to simply insert all the elements from std::vectorin std::multisetand just go multisetfrom start to finish. The total execution time will be O (n * log (n)) and will require O (n) additional memory for 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;
}