schnellere Alternative zu STL std :: map

Question

Ich habe eine Datenstruktur:

typedef std::pair<boost::shared_ptr<X>, boost::shared_ptr<X> > pair_ptr; 
std::map< pair_ptr, int > 

, die ich in einem iterativen Prozess verwenden. In jeder Iteration muss ich kopieren, um die std :: map zu kopieren und möglicherweise eine Kopie zu zerstören. Allerdings kann die std :: map groß werden, über 100k Elemente. Dies verlangsamt das Programm erheblich. Ich habe den Bediener definiert < als:

inline bool operator<(const pair_ptr& a, const pair_ptr& b) 
    { 
    return (a.first < b.first) or 
     (a.first == b.first and a.second < b.second); 
    } 

Ich verwende den std :: map Copykonstruktor und destructor. Gibt es eine schnellere Alternative?

Answer 1

Sie haben eine große Auswahl - und wir können Design-Alternativen vorschlagen, haben aber nicht genug Informationen, um sie für Sie zu erstellen.

Hier sind drei Dinge, die Sie tun können:

1. Können Sie den Schlüssel ein Zeiger auf die Paare (und stellen Sie den Vergleich entsprechend), so dass die Paare selbst (mit zwei refcnt'd PTRs) muss nicht kopiert werden?

2. In jeder Iteration - benötigen Sie die erwartete Einfüge-/Löschzeit? Wenn Sie mit O(n) Einfügung/Löschung leben können, dann können Sie einen sortierten Vektor als Container anstelle einer Karte verwenden? (. Damit Sie zuteilen/frei, die Behälter in einem Schuss statt zuteilen/Frei viele kleine Baumknoten) (Denken Sie daran: ein std::map ist nicht die einzige Datenstruktur, die Sie suchen in, auch nicht die einzige std:: Daten Struktur. Alle durchsuchbaren Datenstrukturen arbeiten, nur wählen denjenigen, der die entsprechende Komplexität garantiert hat, modulo Ihre Kenntnis des „Konstanten“ (zB ist Heapzuordnung teuer), für Ihren Anwendungsfall.)

3. Können Sie (Sie) die Lebensdauern der beiden Dinge verwalten, die der Schlüssel auf unabhängig von der Karte zeigt, und diesen iterativen Prozess? Wenn so können Sie einen Schlüssel eines Paares nackter Zeiger haben, die schneller als ref cnt'd Zeiger auf die Erstellung der neuen Karte bei jedem Iterator sein wird. Sie können einen separaten Satz von ref cnt'd Zeiger auf alle Ihre Sachen haben, und verwalten Sie die Lebensdauer dieser Objekte dort.

Diese können auch kombiniert werden. Nur ein paar Ideen, um loszulegen.