Algorithmen zum Überqueren einer Sammlung in sortierter Reihenfolge, ohne die Sammlung zu ändern?

Question

Lassen Sie uns sagen, dass wir eine Sammlung wie die folgende haben: {12, 10, 4, 5, 7}

Ich mag würde die Ordnung der Sammlung zu bewahren, so werden die Indizes konsistent bleiben, aber die Sammlung in sortierter Reihenfolge wie so {12, 10, 7, 5, 4} durchqueren.

Was ich gedacht habe ist, eine andere Sammlung von Zeigern zu den Elementen zu machen und dann die Zeiger zu sortieren.

Was sind Ihre Gedanken? Wurde ein solcher Algorithmus bereits in C++ implementiert?

Edit: In meinem Fall habe ich ein vector<vector<double>> und ich mochte die Außen-Vektor-Sammlung in nicht-Erhöhung um auf der Summe der inneren Vektoren basierend zu durchqueren.

Answer 1

Wenn Sie beide Aufträge als laufende Sache halten wollen, während Elemente hinzugefügt und entfernt werden, dann könnte man Multi-Index steigern verwenden:

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

Dieses Beispiel von dieser Seite ist ziemlich viel, was Sie wollen, außer sortierter in umgekehrter Reihenfolge:

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

Wenn Sie es einfach als Betrieb Einmal wollen, Ihre Idee, die Zeiger der Sortierung klingt gut. Als eine leichte Variante könnten Sie einen Vektor von std::pair<int,size_t> erstellen, wobei jedes Paar aus einem Wert besteht, auf den der Index folgt. Dann sortiere den Vektor der Paare mit std::sort und spezifiziere std::greater<std::pair<int,size_t> > als Komparator.

Edit:

Ihr konkreter Fall gegeben, würde ich auf jeden Fall Paare beraten Sortierung, weil auf diese Weise nur einmal die Summe jeden inneren Vektor berechnen muß, und speichern Sie es in dem Paar. Wenn Sie nur Zeiger/Indizes sortieren würden, müssten Sie für jeden Vergleich zwei Summen berechnen. also:

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

Dann können Sie über Pairvec iterieren. Machen Sie einen non-const Iterator, wenn Sie müssen.

Answer 2

Eine der Möglichkeiten, es zu tun (für eine verkettete Liste) ist zwei Ebenen von Zeigern auf mentain: eine für die ursprüngliche Reihenfolge, und die zweite für absteigend, wie in

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

Answer 3

Sie den Index speichern könnte Werte in einem Array, dann schreibe/passe einen Sortieralgorithmus an, der die Indexwerte basierend auf dem sortiert, was sie im ursprünglichen Array indexieren.

Answer 4

nicht sicher, was Ihre Laufzeit/Speichereinschränkungen, aber die einfachste und praktischste Lösung IMHO ist, einfach alle Elemente einfügen aus den std::vector in ein std::multiset und durchqueren nur die multiset von Anfang bis Ende. Die Gesamtlaufzeit wäre O (n * log (n)) und würde O (n) zusätzlichen Speicher für die multiset erfordern.

#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; 
}