Wie kann ich eine schnelle Karte mit mehreren Schlüsseln implementieren?

Question

Ich bin auf der Suche nach einem C++ assoziative Karte Container-Typ, die ich mehrere Schlüssel Lookups auf durchführen können. Die Karte muss konstante Zeit Lookups haben, aber es ist mir egal, ob es geordnet oder ungeordnet ist. Sie muss nur schnell sein.

Ich möchte zum Beispiel einen Haufen von std::vector Objekte in einer Karte mit einer int und eine void* als Nachschlageschlüssel. Sowohl die int y el void* müssen übereinstimmen, damit mein Vektor abgerufen werden kann.

Gibt es bereits einen solchen Container? Oder muss ich meinen eigenen entwickeln? Wenn ja, wie könnte ich ihn implementieren? Ich habe versucht, eine boost::unordered_map in einem anderen boost::unordered_map aber ich habe mit dieser Methode noch keinen Erfolg gehabt. Vielleicht werde ich Pershing diese Methode fortsetzen, wenn es keinen einfacheren Weg gibt.

Answer 1

Ständiges Nachschlagen erfordert eine Hash-Map. Sie können die boost::unordered_map (oder tr1). Der Schlüssel wäre der kombinierter Hash des int und des void-Zeigers.

Answer 2

Wenn Sie keinen Boost verwenden möchten, können Sie versuchen map< int, map<void*, vector> > . Die Suchvorgänge sind jedoch O(log(map size)).

Answer 3

Seit C++11 können Sie auch eine std::unordered_map da es Ihren Anforderungen recht gut zu entsprechen scheint:

Eine ungeordnete Karte ist ein assoziativer Container, der Schlüssel-Wert-Paare mit eindeutigen Schlüsseln enthält. Das Suchen, Einfügen und Entfernen von Elementen hat eine durchschnittliche Komplexität bei konstanter Zeit.

Für die Kombination Ihrer int y void* zu einem einzigen Schlüssel zusammenfassen, können Sie mit std::pair .

Damit die ungeordnete Karte mit dem Paar funktioniert, müssen Sie eine geeignete Hash-Funktion angeben. Um das folgende Beispiel kurz zu halten, verwende ich eine handgefertigt Kombination aus std::hash<> Funktionsaufrufe innerhalb einer Lambda-Ausdruck . Falls diese Funktion Leistungsprobleme verursacht, sollten Sie einen anspruchsvolleren Hash erstellen.

Sie haben den Inhalt Ihrer Vektoren nicht angegeben, also habe ich int der Einfachheit halber. Sie können die Lösung jedoch an jeden beliebigen Vektorinhalt anpassen. Alles in allem könnte Ihr Code wie folgt aussehen:

using Key = std::pair<int, void*>;
auto hash = [](const Key & k) {
    return std::hash<int>()(k.first) * 31 + std::hash<void*>()(k.second);
};
std::unordered_map<Key, std::vector<int>, decltype(hash)> um(8, hash);

Code auf Ideone

Answer 4

Sie könnten verwenden boost::multi_index .

(obwohl ich denke, was Sie tatsächlich wollen, ist ein Typ zu verwenden, die sowohl die void* und die ganze Zahl als Schlüssel zu Ihrer Karte enthält, und nur die Rohdaten für beide zu vergleichen, um den Vergleichsoperator für die Karte bereitzustellen)