STL-Map Speicherbedarf ??

Artchi

Was heißt "irgendwo"??? Wie hast du das "irgendwo" festgestellt? Dann wäre es kein "irgendwo" mehr, sondern ein bekannter Ort, oder?

Wie DEINE verwendete map-Implementierung genau funktioniert, kann dir doch hier keinder erklären, ohne den Source zu kennen. Der C++-Standard macht Vorgaben zum Verhalten und Interface einer map. Wie sie implementiert wird (und somit Speicher verbraucht) ist dem Implementierer überlassen... solange er sich an den Standard hält.

1. Ist das natürlich implementierungsabhängig.
Bei meiner STL (VC8) ist die sizeof(map<int,int*) 28
2. Wie hast Du denn gemessen wieviel auf dem Heap allokiert wird?

3. Kucken wir mal auf die implementierung...
Meine map ist als baum implementiert.
da hab ich eine Klasse Node.
Dieser wird wohl in die "map" eingefügt werden.
Er hat die member.
PointerAufLinks 4 Byte
PointerAufRechts 4 Byte
PointerAufVater 4 Byte
Color 1 Byte --> siehe rotschwarz baum bei google oder so
isRoot 1 Byte
value_type 4 + 4 8 Byte

Komme dann auf 22 Byte, was ungefähr Deinem Wert fürs einfügen entspricht.

Laplace

he templäd,
das ist mal ne gute antwort.

"irgendwo": Application Verifier ist das tool mit dem ich sehen kann, wieviel bytes auf dem heap allokiert werden. aber eigentlich geht es auch nicht um das wo, sondern um das warum.

aber das hat sich jetzt ja geklärt.
templäd: habe ähnliche struktur als implementation.
werde sizeof() auch noch testen.

Frage
warum beim instanzieren 2 x 24 byte (bzw. bei dir templäd 22 byte) ??
bei insert() verstehe ich das jetzt.

+gruß

inp

edit:
hab meinen vorigen beitrag entfernt (hat nicht zum thema gepasst).

templäd schrieb:

Color 1 Byte --> siehe rotschwarz baum bei google oder so
isRoot 1 Byte

1 byte pro node verschwendet für isRoot, hätte man auch einfach als 3. farbe kodieren können. oder?

hmmmm schrieb:

1 byte pro node verschwendet für isRoot, hätte man auch einfach als 3. farbe kodieren können. oder?

Ja hätte man.
Das ist eine gute Antwort auf die Frage "Wann wird optimiert?"
Da das die Implementierung für den 8er compiler von Microsoft ist, wäre eine Kodierung von isRoot in color nur verwirrend, da es keinen Bezug zu Color gibt und man bei Windows (auch CE) im Normalfall nicht nach einem Byte kuckt.

PS: Bitte keine Diskussion über die anderen Verwirrungen in den STL Implemntierungen

CStoll

hmmmm schrieb:

templäd schrieb:

Color 1 Byte --> siehe rotschwarz baum bei google oder so
isRoot 1 Byte

1 byte pro node verschwendet für isRoot, hätte man auch einfach als 3. farbe kodieren können. oder?

Ja, und dieses Byte würde dann sowieso im Padding untergehen

@Laplace: Womöglich benötgt die map für den Anfang zwei Dummy-Elemente, auf die begin() und end() verweisen können.

CStoll schrieb:

@Laplace: Womöglich benötgt die map für den Anfang zwei Dummy-Elemente, auf die begin() und end() verweisen können.

Ja, denke das ist es !
Habe schon danach gegoogelt. Aber zum Thema "Instanzieren einer STL-Map" bzw. "Erzeugen einer STL-Map" oder ähnlichen Anfragen finde ich leider nichts.
Auch die MSDN gibt mir keine Info darüber.

@CStoll: hast du dokumente in denen ich das Verhalten beim Erzeugen einer Map
nachlesen kann. Also muss eben mit Sicherheit wissen, wofür die Allokationen sind- auch wenn ich deiner Meinung bin.
Oder hast du einen Tip, wie ich diese "Theorie" überprüfen kann?

+gruß

Jester

Ja, gibt nen ganz einfachen Trick: Schau in der Implementierung nach, was da im Konstruktor gemacht wird.

CStoll

Wie die map<> implementiert werden soll, steht nicht im Standard (der stellt nur bestimmte Forderungen an die Bedeutung und das Laufzeitverhalten ihrer Methoden), also können solche Details je nach Implementation anders aussehen. Der einzige Weg, das sicher zu erkennen, ist wohl ein Blick in die <map>.

Zur Ansicht mal ein Ausschnitt aus der MSVC-Version:

template<class _K, class _Ty, class _Pr = less<_K>, class _A = allocator<_Ty> >
class map
{
public:
  ...
  typedef _Tree<_K, value_type, _Kfn, _Pr, _A> _Imp;
  ...
  explicit map(const _Pr& _Pred = _Pr(), const _A& _Al = _A())
    : _Tr(_Pred, false, _Al) {}
  ...
protected:
  _Imp _Tr;
};

template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
class _Tree
{
  ...
public:
  explicit _Tree(const _Pr& _Parg, bool _Marg = true, const _A& _Al = _A())
    : allocator(_Al), key_compare(_Parg), _Multi(_Marg)
    {_Init(); }
  ...
protected:
  void _Init()
  {
    _Nil = _Buynode(0, _Black);
    _Isnil(_Nil) = true;
    _Left(_Nil) = 0, _Right(_Nil) = 0;
    _Head = _Buynode(_Nil, _Red);
    _Lmost() = _Head, _Rmost() = _Head;
    _Size = 0;
  }
  ...
};

(Wie man sieht, legt er zwei Nodes an, die als _Nil (vermutlich Kennung für "Not in List") und _Head (Wurzelelement) eingetragen werden)

templäd schrieb:

Da das die Implementierung für den 8er compiler von Microsoft ist, wäre eine Kodierung von isRoot in color nur verwirrend, da es keinen Bezug zu Color gibt

das ist doch kein argument. dann ist es eben kein red-black tree, sondern ein red-black-green tree, bei dem root immer grün ist. das ist genauso viel oder wenig verwirrend wie rot und schwarz für die nodes. außerdem interessieren den benutzer implementierungsdetails doch eh nicht.

CStoll schrieb:

(Wie man sieht, legt er zwei Nodes an, die als _Nil (vermutlich Kennung für "Not in List") und _Head (Wurzelelement) eingetragen werden)

Danke CStoll !
Deine Antworten haben mir sehr geholfen.
Hab die map<> mir jetzt nochmal genauer angeschaut. Ist identisch zu deiner.

Bin froh, dass das jetzt vom tisch ist!
+gruß

CStoll

Nur am Rande: Das da oben ist vermutlich nur eine Möglichkeit, einen Binärbaum umzusetzen (aber wenn du auch mit MSVC arbeitest, stehen die Chancen hoch, daß du die selbe Implementierung verwendest). Wenn du das Programm unter einem anderen System compilierst, könnte sich auch der Speicherbedarf ändern (sowohl für die Nodes selber als auch für die drumherum benötigten Zusatzdaten).