Czy std :: set przechowuje obiekty w pamięci w sposób ciągły?

16

Czy std::setprzechowuje obiekty w ciągłej pamięci std::vector?

Nie udało mi się tego znaleźć w Internecie, cppreference nie wspomina o szczegółach przydzielania pamięci. Ale nie rozumiem, dlaczego nie może używać ciągłej pamięci, stąd moje pytanie.

c++ set stdset mfnx
źródło
5
Przeczytaj set::insertwymagania: en.cppreference.com/w/cpp/container/set/insert „... Żadne iteratory lub referencje nie są unieważniane ...”, więc nie można dokonać ponownego przydzielenia, gdy trzeba je rozwinąć tak jak std::vectorrobi.
Richard Critten
Wydajność: musisz zmierzyć (w zależności od funkcji skrótu ) dla swojego przypadku użycia patrz: channel9.msdn.com/Events/Build/2014/2-661 od 45:48
Richard Critten
4
Zobacz także boost :: flat_set .
Caleth
1
Czy masz na myśli „ciągły” jak w „jak iteracja zestawu, obiekty są przechowywane w ciągłych lokalizacjach pamięci”, czy jak w „wszystkie obiekty są przechowywane w jednym dużym kawałku pamięci (ale w dowolnej kolejności)”?
Pablo H
1
Zasadniczo, gdy pojawia się pytanie „czy pojemnik A jest taki sam jak pojemnik B”, odpowiedź brzmi „nie”, w przeciwnym razie byłby tylko pojemnik A (bo jaki byłby cel posiadania pojemnika B?). Nie dotyczy to oczywiście adapterów do kontenerów , ale std::setnie jest to jedna z tych rzeczy, co jest tutaj kluczem.
Wyścigi lekkości na orbicie

Odpowiedzi:

25

Czy std :: set przechowuje obiekty w ciągłej pamięci, takie jak std :: vector?

Nie ma gwarancji, że tak będzie. Również w praktyce nie jest to możliwe z powodu wymagań kontenera. Dlatego nie, nie przechowuje obiektów w ciągłej pamięci.

Nie rozumiem, dlaczego nie mógł użyć ciągłej pamięci

Odniesienia do elementów zestawu muszą pozostać ważne po wstawieniu do niego, a także po usunięciu (z wyjątkiem odniesień do usuniętego elementu). To wymaganie jest niezgodne z ciągłą pamięcią.

O ile mi wiadomo, zrównoważone drzewo wyszukiwania jest jedyną strukturą danych, którą można wdrożyć std::set.

eerorika
źródło
Może wyciąć przestrzeń dla węzłów drzew z dużych, ciągłych kawałków, na wypadek gdyby to właśnie oznaczało OP. (Ale żadne unieważnienie iteratora wyklucza insertkopiowanie wszystkich węzłów do nowego większego bloku, aby ograniczyć go tylko do jednego bloku, w przypadku niepowodzenia lokalnego przeniesienia lub (typowy dla C ++) alokator nie obsługuje takiego ponownego przeniesienia.)
Peter Cordes
15

Nie jest to wyraźnie wykluczone, choć pewne ograniczenia std::setuniemożliwiają korzystanie z ciągłej pamięci.

Na przykład set::insertma złożoność logarytmiczną, ale vector::insertwymaga złożoności liniowej, aby przetasować wpisy. Również set::insertnie unieważnia iteratory. Oba wymagania nie mogą być spełnione przy pomocy pamięci ciągłej.

idclev 463035818
źródło