Schnelle Karte Implementierung in C++

Question

Ich habe eine funktionierende Implementierung nun, dass die Karten Schlüssel von Bereichen, etwa so:

class Range { 
public: 
    Range(int from, int to = -1) : _from(from), _to(to >= 0 ? to : from) {} 
    bool operator < (const Range& item) { 
     return _to < item._from; 
    } 
    bool operator == (const Range& item) { 
     return item._from >= _from && item._to <= _to; 
    } 
private: 
    int _from, _to; 
}; 

typedef std::map<Range, MappedType> my_map_type; 

Coole Sache dabei ist, dass ich tun kann:

my_map_type m; 
m[Range(0, 20)] = Item1; 
m[Range(30,40)] = Item2; 

my_map_type::iterator it = m.find(15); 
assert(it->second == Item1); 
it = m.find(40); 
assert(it->second == Item2); 
it = m_find(25); 
assert(it == m.end()); 

Aber ich brauche eine schnellere Kartenimplementierung als Std :: Karte. Einfügungen sind in Ordnung, um langsam zu sein, aber Funde müssen wirklich schnell sein. Versucht boost :: unordered_map aber ich kann es nicht mit Bereich Klasse (obwohl ich boost :: hash_value für Range-Objekte implementiert haben) zu arbeiten. Ein finden kehrt nichts (und Operator == nicht einmal während eines finden, die ich seltsam finden genannt wird)

Ideen?

Answer 1

Sie können dies nicht mit einer Hash-Tabelle, Ihre Definition von operator== kann nicht mit einer Hash-Funktion kompatibel sein: In Ihrem Code Range(10, 20) == Range(15, -1), aber es gibt keine Möglichkeit, eine Hash-Funktion den gleichen Hash zurückgeben kann.

Im Allgemeinen müssen Hash und Gleichheit kompatibel sein: x == y muss implizieren hash(x) == hash(y). Natürlich ist das Gegenteil nicht der Fall.

Sie benötigen also eine vergleichsbasierte Struktur, wie die baumbasierte map. Anstatt einen defekten operator== zu verwenden, der Ihnen Probleme bereiten könnte, können Sie einen korrekten Gleichheitskomparator definieren und map::lower_bound verwenden, der genau das tut, was Sie versuchen zu tun.

Wenn es zu langsam für Sie ist, können Sie einen sortierten Vektor verwenden und std::lower_bound verwenden. Die Suchzeit ist O (log n), was asymptotisch der gleiche ist wie std::map, aber in der Praxis viel schneller (kein Zeiger jagen, bessere Lokalität). Es hat jedoch eine lineare Aktualisierungszeit (Einfügen/Löschen).

Andernfalls sollten Sie sich spezialisierte Strukturen wie interval trees ansehen, aber sie sind nicht in der STL implementiert (vielleicht Boost?).

Jedenfalls ist der implizite Konstruktor Range(int) irreführend und potenziell schädlich. Sie sollten es als explicit deklarieren und anstelle von find(40) beispielsweise find(Range(40)) verwenden.

Answer 2

Was Sie versuchen, wird nicht funktionieren, ob mit std::map oder einem anderen Container. Ihre operator < und operator == entsprechen nicht den traditionellen Anforderungen für diese Operatoren:

• Wenn a == b und a == c, dann b == c: in Ihrer Situation, [1,2] == [0,100] und [98,99] == [0,100] aber offensichtlich [1,2] != [98,99].
• Wenn a < b wahr ist, dann ist b < a falsch: In Ihrer Situation ist [2,4] < [1,3] wahr, aber [1,3] < [2,4] ist auch wahr.

So, Ihre std::map Implementierung wird auch in einigen Situationen fehlschlagen.

Nicht nur das, aber std::map wird nur einen Bereich zurückgeben, während erwartet werden konnte, dass ein bestimmtes Element innerhalb mehrerer Bereiche in der Karte sein könnte.

Wenn Sie sicher, dass keiner der Bereiche übernehmen überlappen, dann die Bereiche allein auf der Grundlage ihrer from Wert sortieren, verwenden upper_bound den Bereich mit den larges from kleiner als der Wert für Sie suchen, zu extrahieren und vergleichen mit, dass Bereich to um festzustellen, ob es eine tatsächliche Übereinstimmung ist.

Answer 3

Sie verwenden std :: map <> die normalerweise als rot-schwarzer Baum implementiert ist. boost :: multi_index container bietet auch einen rot-schwarzen, baumbasierten Container, aber mit komprimierten Knoten (kleiner um die Größe eines Zeigers), also wird er schneller sein als std :: map <> wegen der kleineren Arbeitsmenge.

Eine weitere Option ist die Verwendung eines Hash, so dass einige von Ihnen, wenn keine Hash-Kollisionen auftreten, O (1) sind.