Speicherzuweisung in STL C++

Question

Ich bin ein wenig verwirrt über Speicher Neuzuordnung in STL C++. Zum Beispiel weiß ich, wenn ich eine vector deklariere und Elemente in sie zurückschiebe, wird der Vektor irgendwann eine Neuzuweisung von Speicherplatz benötigen und alle vorhandenen Elemente in diese kopieren. Für verknüpfte Listen ist keine Neuzuweisung erforderlich, da die Elemente nicht nacheinander im Stapel gespeichert werden und jedes Element einen Zeiger verwendet, um auf das nächste Element zu zeigen.

Meine Frage ist, wie ist die Situation für andere STL in C++? zum Beispiel string, map, unordered_map? Müssen sie neu zugeordnet werden?

Answer 1

(Disclaimer: alle konkreten Datenstrukturen hier angegebenen können von der Norm nicht erforderlich, aber sie sind nützlich, sich daran zu erinnern, die Regeln zu etwas Konkretes zu helfen Link)

std::string ~ = std::vector; Es ist ein dynamisches Array. Wenn Sie Elemente an seinem Ende halten, wird es Ihre Elemente irgendwann neu zuweisen.

std::list: Jedes Element ist ein neuer verknüpfter Listenknoten, daher findet keine Neuzuweisung statt, wo immer Sie das neue Element einfügen.

std::deque: Es besteht in der Regel aus mehreren Seiten von Elementen; Wenn eine Seite voll ist, wird eine neue Seite zugewiesen und der Liste der Seiten hinzugefügt. Aus diesem Grund findet niemals eine Neuzuordnung Ihrer Elemente statt und Ihre Elemente werden niemals bewegt, wenn Sie am Anfang oder am Ende etwas schieben.

std::map/std::multimap/std::set/std::multiset: In der Regel ein Binärbaum, jedes Element ist für sich allein reserviert; Es werden keine Neuzuweisungen vorgenommen.

std::unordered_map//std::unordered_set/std::unordered_multiset: eine Hash-Tabelle; Wenn die Tabelle voll genug ist, findet eine erneute Speicherung und Neuzuweisung statt.