Algoritmos para atravesar una colección en orden ordenado sin modificar la colección?

Question

Digamos que tenemos una colección como la siguiente: {12, 10, 4, 5, 7}

me gustaría preservar el orden de la colección de modo que los índices seguirán siendo consistente, pero atravesar la colección en un orden clasificado como tal {12, 10, 7, 5, 4}.

Lo que he pensado es hacer otra colección de punteros a los elementos y luego ordenar los punteros.

¿Cuáles son sus pensamientos? ¿Ya se implementó un algoritmo como este en C++?

Editar: En mi caso, tengo una vector<vector<double>> y me gustaría para atravesar la colección exterior-vector en no creciente orden basado en la suma de los interno-vectores.

Answer 1

Si desea mantener ambos órdenes como algo continuo, mientras que se agregan y se quitan elementos, entonces se podría impulsar el uso de múltiples índice:

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

Este ejemplo de esa página es más o menos lo desea, a excepción ordenada en el orden inverso:

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

Si lo que desea es como una operación de una sola vez, su idea de clasificar los punteros suena bien. Como una pequeña variante, puede crear un vector de std::pair<int,size_t>, cada par consiste en un valor seguido de su índice. Luego, clasifique el vector de pares con std::sort y especifique std::greater<std::pair<int,size_t> > como el comparador.

Editar:

Dada su caso real, definitivamente aconsejaría clasificación pares, porque de esa manera es suficiente para calcular la suma de cada vector interior de una vez, y almacenarlo en la pareja. Si estuvieras clasificando solo punteros/índices, tendrías que calcular dos sumas para cada comparación. entonces:

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

Luego puede iterar sobre pairvec. Haga It un iterador no const si es necesario.

Answer 2

Una de las maneras de hacerlo (para una lista enlazada) es mentain dos niveles de punteros: uno para el orden original, y el segundo para el descendente, al igual que en

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

Answer 3

podría almacenar el índice valores en una matriz, luego escribe/adapta un algoritmo de clasificación que ordena los valores de índice según lo que indexan en la matriz original.

Answer 4

No está seguro de cuáles son sus limitaciones de tiempo de ejecución/memoria son, en mi humilde opinión, pero la solución más sencilla y práctica es simplemente insertar todos los elementos de la std::vector en un std::multiset y simplemente atravesar el multiset de principio a fin. El tiempo de ejecución general sería O (n * log (n)) y requeriría O (n) memoria adicional para el 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; 
}