std :: map für kleine Sparse-Sammlungen

Question

Gegeben eine Struktur MyData, von der viele Instanzen existieren (ich würde sagen, mehrere Millionen höchstens), für jede Instanz muss ich ein Mitglied speichern, das Werte für bis zu 8 Schlüssel enthalten kann . Der Schlüssel wird immer ein int entfernter 0-7 sein, und die Werte werden immer ein 3D-Punkt von floats sein (nennen wir es Point3).

Bei maximaler wäre es enthalten:

Key | Value 
------------- 
0 | [x,y,z] 
1 | [x,y,z] 
2 | [x,y,z] 
3 | [x,y,z] 
4 | [x,y,z] 
5 | [x,y,z] 
6 | [x,y,z] 
7 | [x,y,z] 

in 99,9% der Fälle ist es jedoch 0 oder 1 Schlüssel-Wert-Paare enthalten, zB:

Key | Value 
------------- 
1 | [x,y,z] 

Wie kann ich den Speicher-Overhead, falls vorhanden, effizient zu bestimmen, um einen leeren oder einwertigen std::map<int, Point3> zu speichern, verglichen mit dem Speichern eines Arrays aus 8 Point3 (4 Bytes pro Float * 3 Werte * 8 Slots = 96 Bytes) und einem einzelnen BYTE mit Bits, für die Slots sinnvolle Werte enthalten?

Im Allgemeinen ist meine Frage Was ist der Speicheraufwand von einem leeren oder fast leeren std::map?

Answer 1

Der Speicheraufwand einer Karte ist nicht , die schlecht ist. Es sind typischerweise ein paar Wörter pro Knoten. Die Verwendung einer Karte wäre mit der Regel "keine vorzeitige Optimierung" definitiv in Ordnung.

Das heißt, wenn Sie optimieren, wird die Karte in der Liste der zu ersetzenden Datenstrukturen hoch sein. Aber an diesem Punkt können Sie alle verschiedenen Operationen profilieren, die Sie tatsächlich verwenden. Wie oft ändern sich die Schlüssel und/oder Werte? Das sind wichtige Informationen, die Sie vor der Optimierung wissen sollten.

[Bearbeiten] Wenn ich eine Struktur vorschlagen würde, wäre es ein Vektor von std::pair<int, Point3D>. Der Grund dafür ist, dass dies wahrscheinlich ausrichtungsfreundliche 16-Byte-Objekte ergibt. Ich würde mich nicht damit beschäftigen, die Schlüssel zu sortieren, weil das nur für die 0,1% -Knoten nützlich ist, die mehrere Schlüssel/Wert-Paare haben.

Answer 2

Werfen Sie einen Blick auf this Blogpost. Es gibt eine sehr gründliche Analyse der Speichernutzung verschiedener STL-Container (einschließlich std::map) und verschiedene Plattformen/Compiler werden berücksichtigt.

in den 64-Bit-STL, die (C++ 10 Visuelle) mit Visual Studio 2010 kommen:

---

Karte 32 Bytes für das Kartenobjekt verwendet, um sich, dann wird jede Karte Knoten 26 Bytes größer als die Größe des enthaltenen Objekts (wahrscheinlich 32 Bytes nach Berücksichtigung von Ausrichtung und Verschwendung). Die Anzahl der für eine Karte erforderlichen Karten Knoten ist 1 mehr als die Größe der Karte.