Welcher sortierte STL-Container ist für das schnelle Einfügen und Suchen mit einem speziellen Schlüssel zu verwenden?

Question

Ich habe einige Daten mit einem Schlüssel, der mit jedem Datenelement verbunden ist. Der Schlüssel besteht aus zwei Teilen: nennen wir sie color und id. Ich möchte den Container nach Farbe iterieren, um das Rendering zu beschleunigen, und ich möchte auch Elemente im Container allein nach der ID finden.

Ich habe versucht, std::map für diesen Zweck mit einem Schlüssel zu verwenden

class MyKey {
public:
  int color;
  int id;
  bool operator<(...)
  bool operator==(...)
};

Aber ich kann keinen <-Operator zur Verfügung stellen, der die Daten nach Farbe sortiert hält und gleichzeitig map::find erlaubt, nur mit der ID zu arbeiten (d.h. keine Informationen über die Farbe).

Ich möchte, dass sowohl die Einfüge- als auch die Suchoperationen schnell sind (z. B. O(log(n)).

Irgendwelche Ideen, welche Art von Container ich verwenden könnte, um dies zu implementieren?

Answer 1

Das Beispiel anpassen aquí von Boost.Multi_index auf der Grundlage der folgenden Änderungen:

typedef multi_index_container<
    MyKey,
    indexed_by<ordered_unique<identity<MyKey> >,
    ordered_non_unique<member<MyKey,int,&MyKey::color> >
  > 
> DataSet;

Answer 2

Versuchen Sie Boost.BiMap, das ist eine Karte mit 2 Ansichten.

Ansonsten gibt es die kompliziertere Boost.MultiIndex.

Answer 3

Wenn Sie lieber etwas Eigenes schreiben möchten, als Boost zu verwenden (was meiner Meinung nach dumm ist), können Sie eine Klasse erstellen, die zwei Karten enthält. Eine für die Zuordnung von Farbe und die andere für die Zuordnung von ID. Die Map-Werte wären Zeiger. Sie definieren für Ihre neue Klasse die Operationen insert und find. Das Einfügen würde new eine Datenstruktur und fügen den Zeiger in beide Maps ein. Die Suchoperationen würden das Element je nach Bedarf mit einer der beiden Maps finden. Bei Lösch-/Entfernvorgängen ist es etwas komplizierter: Sie müssen die Datenstruktur über eine Map nachschlagen und sie dann aus beiden Maps entfernen, indem Sie wahrscheinlich die Daten in der Datenstruktur verwenden, um den anderen Map-Eintrag zu finden.