Sortieren mit Bewertungsliste

Also ich habe zwei getrennte Vektoren und möchte den einen sortieren und den anderen gleich mit (also sozusagen den einen so umsortieren wie dass der andere sortiert wird). Als Code kann man sich das so vorstellen:

vector<incompareable_t> data;
vector<int> values;
sort(values.begin(), values.end());

Und am Ende soll data so geordnet sein wie Values umsortiert wurde. Beispiel:

data = {a, b, c};
values = {2, 1, 3};
sort
data == {b, a, c};

Das soll bestenfalls generisch umsetzbar sein, da ich das an verschiedenen Stellen im Programm mit verschiedenen Typen brauche. Ebenso soll es ohne zusätzlichen Speicher auskommen, dynamischen Speicher allozieren ist langsam.

Meine Ideen:
- Pseudo-Iterator schreiben, der einen Proxy beim Dereferenzieren zurückgibt, der sich bezüglich dem value-Vector vergleichen lässt, der aber beim Swappen die Elemente beider Vectoren swappt.
- Eigenen Sortieralgorithmus implementieren und möglicherweise Performancedefizite hinnehmen.

Übersehe ich eine offensichtliche und gute Lösung für dieses Problem?

Nathan

Ja, es gibt eine ganz simple Lösung:

std::vector<std::pair<int, incomperable_t>> vector;
std::sort(vector.begin(), vector.end(), [](std::pair<...> a, std::pair<...b>){return a.first < b.first;});

Da steht doch:

Abwärtskompatibel schrieb:

Ebenso soll es ohne zusätzlichen Speicher auskommen, dynamischen Speicher allozieren ist langsam.

Bei deiner Variante brauche ich den doppelten Speicher und muss erstmal alle Daten umkopieren.

volkard

Eventuell könnte so ein kleines Index-Sort passen.
http://www.c-plusplus.net/forum/316543-full

Nexus

Boost.Range oder Boost.Iterator hat eventuell auch was. Ich dachte zuerst an zip_iterator , bin mir aber nicht sicher, ob man damit sortieren kann.

Nathan

Abwärtskompatibel schrieb:

Da steht doch:

Abwärtskompatibel schrieb:

Ebenso soll es ohne zusätzlichen Speicher auskommen, dynamischen Speicher allozieren ist langsam.

Bei deiner Variante brauche ich den doppelten Speicher und muss erstmal alle Daten umkopieren.

Ich ging davon aus, dass du die Daten die ganze Zeit so speicherst...