Speichert std :: set Objekte zusammenhängend im Speicher?

16

Gefällt es std::set, Objekte im zusammenhängenden Speicher zu speichern std::vector?

Ich konnte dies nicht im Web finden, cppreference erwähnt keine Details zur Speicherzuweisung. Aber ich kann nicht verstehen, warum es kein zusammenhängendes Gedächtnis verwenden konnte, daher meine Frage.

c++ set stdset mfnx
quelle
5
Lesen Sie die set::insertAnforderungen: en.cppreference.com/w/cpp/container/set/insert "... Keine Iteratoren oder Referenzen werden ungültig gemacht ...", sodass keine Neuzuweisung möglich ist, wenn eine Erweiterung std::vectorerforderlich ist.
Richard Critten
Leistung: Sie müssen für Ihren Anwendungsfall messen (abhängig von Ihrer Hashing-Funktion), siehe: channel9.msdn.com/Events/Build/2014/2-661 von 45:48
Richard Critten
4
Siehe auch boost :: flat_set .
Caleth
1
Meinen Sie "zusammenhängend" wie in "Während die Menge iteriert wird, werden Objekte an zusammenhängenden Speicherorten gespeichert" oder wie in "Alle Objekte werden in einem großen Speicherblock (aber in beliebiger Reihenfolge) gespeichert"?
Pablo H
1
Wenn Sie sich fragen, ob Container A mit Container B identisch ist, lautet die Antwort im Allgemeinen "Nein", andernfalls würde es nur Container A geben (denn was wäre der Zweck, Container B zu haben?). Dies gilt nicht für Container - Adapter natürlich, aber std::setist nicht eines dieser Dinge, die hier der Schlüssel ist.
Leichtigkeitsrennen im Orbit

Antworten:

25

Speichert std :: set Objekte im zusammenhängenden Speicher wie std :: vector?

Es gibt keine Garantie dafür. Auch in der Praxis kann es aufgrund der Anforderungen des Containers nicht. Daher nein, es werden keine Objekte im zusammenhängenden Speicher gespeichert.

Ich kann nicht verstehen, warum es keinen zusammenhängenden Speicher verwenden konnte

Verweise auf Elemente des Satzes müssen beim Einfügen sowie beim Löschen gültig bleiben (mit Ausnahme von Verweisen auf das gelöschte Element). Diese Anforderung ist nicht mit dem zusammenhängenden Speicher kompatibel.

Soweit ich weiß, ist ein ausgeglichener Suchbaum die einzige Datenstruktur, die implementiert werden kann std::set.

Eerorika
quelle
Es könnte Platz für Baumknoten aus großen zusammenhängenden Stücken schaffen, falls das OP dies bedeutete. (Aber keine Iterator-Ungültigmachung schließt das insertKopieren aller Knoten in einen neuen größeren Block aus, um ihn auf nur einen Block zu beschränken, falls die direkte Neuzuweisung fehlschlägt oder (typisch für C ++) der Zuweiser eine solche Neuzuweisung nicht unterstützt.)
Peter Cordes
15

Es wird nicht explizit ausgeschlossen, obwohl bestimmte Einschränkungen std::setes unmöglich machen, zusammenhängenden Speicher zu verwenden.

Zum Beispiel set::inserthat logarithmische Komplexität, während vector::insertlineare Komplexität erforderlich ist, um seine Einträge zu mischen. Auch set::insertmacht Iteratoren nicht ungültig. Beide Anforderungen können mit einem kontinuierlichen Speicher nicht realisiert werden.

idclev 463035818
quelle