Ich habe eine Reihe von Daten, die in zwei Arrays aufgeteilt sind (nennen wir sie data und keys ). Das heißt, für jedes Objekt mit einem Index i kann ich auf die Daten für dieses Objekt mit data[i] und den Schlüssel für dieses Objekt mit keys[i] zugreifen. Ich kann diese Struktur nicht ändern (zB um Schlüssel und Daten in ein einzelnes Array zu verschachteln), weil ich das Array data an eine Bibliotheksfunktion übergeben muss, die ein bestimmtes Datenlayout erwartet.
Wie kann ich beide Arrays (vorzugsweise unter Verwendung von Standardbibliotheksfunktionen) nach dem Inhalt des keys -Arrays sortieren?
Es stellt sich heraus, dass Boost einen Iterator enthält, der ziemlich genau das tut, was paired_iterator von meine andere Antwort tut:
Dies scheint die beste Option zu sein.
Erstellen Sie einen Vektor von Objekten, die Indizes für die beiden Arrays enthalten. Definieren Sie operator< für dieses Objekt, um den Vergleich basierend auf keys[index] durchzuführen. Sortiere diesen Vektor. Wenn Sie fertig sind, gehen Sie durch diesen Vektor und fügen Sie Ihre ursprünglichen Objekte in die Reihenfolge ein, die von diesen Proxy-Objekten definiert wurde:
Hier ist eine Beispielimplementierung, die einen neuen Iteratortyp definiert, um eine paarweise Ansicht über zwei Sequenzen bereitzustellen. Ich habe versucht, Standards konform und korrekt zu machen, aber da der C ++ - Standard in seinen Details scheußlich komplex ist, bin ich mir fast sicher, dass ich gescheitert bin.
Ich werde sagen, dass dieser Code funktioniert, wenn er mit clang++ oder g++ erstellt wird.
Dieser Code wird nicht empfohlen für den allgemeinen Gebrauch, da er länger und weniger verständlich ist als die anderen Antworten und möglicherweise das gefürchtete 'undefinierte Verhalten' hervorruft.
Jedoch hat es den Vorteil eines konstanten Aufwands für Zeit und Platz, da es eine Sicht auf vorhandene Daten bietet, anstatt tatsächlich eine temporäre alternative Darstellung oder einen Permutationsvektor zu erstellen. Das offensichtlichste (für mich) Leistungsproblem mit diesem Code ist, dass einzelne Elemente der beiden Container während des Swap-Vorgangs kopiert werden müssen. Trotz einiger Versuche habe ich keine Möglichkeit gefunden, std::swap erfolgreich zu spezialisieren, so dass std::sort oder std::random_shuffle die Verwendung der standardmäßigen temporären Kopie-basierten Swap-Implementierung vermeidet. Es ist möglich, dass die Verwendung des C ++ 0x rvalue-Referenzsystems (siehe std::move und Jon Purdys Antwort) dies lösen könnte.
Dieses Problem hat mich wirklich zum Nachdenken gebracht. Ich habe eine Lösung gefunden, die einige C ++ 0x-Funktionen verwendet, um einen sehr STL-ähnlichen parallel_sort -Algorithmus zu erhalten. Um die Sortierung "in-place" durchzuführen, musste ich ein back_remove_iterator als Gegenstück zu back_insert_iterator schreiben, damit der Algorithmus aus demselben Container lesen und in denselben schreiben kann. Sie können diese Teile überspringen und direkt zu den interessanten Sachen gehen.
Ich habe es noch nicht mit Hardcore-Tests durchgestanden, aber es scheint in Bezug auf Zeit und Raum einigermaßen effizient zu sein, hauptsächlich wegen der Verwendung von std::move() , um unnötiges Kopieren zu verhindern.
Ich hoffe, das erweist sich als nützlich oder zumindest als unterhaltsam.