Dlaczego wolałbym używać wektora do deque

86

Od

  1. oba są ciągłymi kontenerami pamięci;
  2. pod względem funkcji, deque ma prawie wszystko, co ma wektor, ale więcej, ponieważ bardziej wydajne jest wstawianie z przodu.

Dlaczego Whould ktoś preferuje std::vectorsię std::deque?

c++  stl  vector  deque 
— Leon
źródło
2
Implementacja Visual C ++ std::dequema bardzo mały maksymalny rozmiar bloku (~ 16 bajtów, jeśli dobrze pamiętam; może 32) i jako taka nie działa zbyt dobrze dla realistycznych aplikacji. deque<T>Gdzie sizeof(T) > 8(lub 16? To mała liczba) ma o tych samych charakterystyk, jako vector<T*>, gdzie każdy element jest przydzielane dynamicznie. Inne implementacje mają różne maksymalne rozmiary bloków, więc pisanie kodu, który ma stosunkowo takie same parametry wydajności na różnych platformach, jest trudne deque.
— James McNellis,
12
Deque nie jest kontenerem pamięci ciągłej.
— Mohamed El-Nakib
@ravil Nie, to jest duplikat, wskazujący na to pytanie.
1
Trudno w to uwierzyć, na pytanie z nieokreślonym rażącym błędem merytorycznym przy bilansie 34 głosów
— podkreślenie_d
2
@underscore_d, dlatego jest to pytanie. Inaczej historia, gdyby to była odpowiedź;)
— Assimilater

Odpowiedzi:

115

Elementy w a niedeque są ciągłe w pamięci; elementy są gwarantowane. Więc jeśli potrzebujesz współdziałać ze zwykłą biblioteką C, która potrzebuje ciągłych tablic, lub jeśli zależy Ci (bardzo) na lokalności przestrzennej, możesz preferować . Ponadto, ponieważ istnieje dodatkowa księgowość, inne operacje są prawdopodobnie (nieco) droższe niż ich odpowiedniki . Z drugiej strony, używanie wielu / dużych wystąpień może prowadzić do niepotrzebnej fragmentacji sterty (spowolnienia wywołań ).vectorvectorvectorvectornew

Ponadto, jak wskazano w innym miejscu w StackOverflow , jest więcej dobrej dyskusji tutaj: http://www.gotw.ca/gotw/054.htm .

— phooji
źródło
3
Wygląda na to, że link do „gdzie indziej” jest teraz martwy (z powodu umiaru?).
— esilk
37

Aby poznać różnicę, należy wiedzieć, w jaki sposób dequejest ogólnie wdrażany. Pamięć jest przydzielana w blokach o równych rozmiarach i są one połączone razem (jako tablica lub ewentualnie wektor).

Aby znaleźć n-ty element, należy znaleźć odpowiedni blok, a następnie uzyskać dostęp do elementu w nim zawartego. Jest to stały czas, ponieważ zawsze są to dokładnie 2 wyszukiwania, ale to wciąż więcej niż wektor.

vectordziała również dobrze z interfejsami API, które wymagają ciągłego bufora, ponieważ są to interfejsy API języka C lub są bardziej wszechstronne pod względem możliwości pobierania wskaźnika i długości. (W ten sposób możesz mieć wektor pod spodem lub zwykłą tablicę i wywołać API z bloku pamięci).

Gdzie dequema swoje największe zalety to:

  1. Podczas wzrostu lub zmniejszania kolekcji z dowolnego końca
  2. Kiedy masz do czynienia z bardzo dużymi rozmiarami kolekcji.
  3. Kiedy masz do czynienia z bools i naprawdę chcesz, aby boole, a nie bitset.

Drugi z nich jest mniej znany, ale dla bardzo dużych rozmiarów kolekcji:

  1. Koszt realokacji jest duży
  2. Narzut związany ze znalezieniem ciągłego bloku pamięci jest restrykcyjny, więc możesz szybciej zabraknąć pamięci.

Kiedy w przeszłości miałem do czynienia z dużymi kolekcjami i przeniosłem się z modelu ciągłego do modelu blokowego, byliśmy w stanie przechowywać około 5 razy większą kolekcję, zanim skończyła się pamięć w systemie 32-bitowym. Dzieje się tak częściowo dlatego, że podczas ponownego przydzielania w rzeczywistości konieczne było przechowywanie starego bloku, a także nowego, zanim skopiował elementy.

Powiedziawszy to wszystko, możesz mieć kłopoty z std::dequesystemami używającymi „optymistycznej” alokacji pamięci. Chociaż jego próby zażądania dużego rozmiaru bufora w celu ponownej alokacji vectortestamentu prawdopodobnie zostaną w pewnym momencie odrzucone przez a bad_alloc, optymistyczny charakter osoby dokonującej alokacji prawdopodobnie zawsze spełni żądanie o mniejszy bufor, o który wnioskuje dequea, co prawdopodobnie spowoduje system operacyjny, aby zabić proces, aby spróbować zdobyć trochę pamięci. Ktokolwiek wybierze, może nie być zbyt przyjemny.

Rozwiązaniem w takim przypadku jest ustawienie flag na poziomie systemu, aby zastąpić optymistyczną alokację (nie zawsze wykonalne) lub nieco bardziej ręczne zarządzanie pamięcią, np. Za pomocą własnego alokatora sprawdzającego użycie pamięci lub podobnych. Oczywiście nie idealny. (Co może odpowiedzieć na twoje pytanie, jak preferować wektor ...)

— Dojną krową
źródło
29

Wielokrotnie zaimplementowałem zarówno wektor, jak i deque. deque jest znacznie bardziej skomplikowany z punktu widzenia implementacji. Ta komplikacja przekłada się na więcej kodu i bardziej złożony kod. Więc zazwyczaj zobaczysz trafienie rozmiaru kodu, gdy wybierzesz deque zamiast wektora. Możesz również doświadczyć niewielkiego spadku szybkości, jeśli twój kod używa tylko rzeczy, w których wektor się wyróżnia (tj. Push_back).

Jeśli potrzebujesz podwójnej kolejki, deque jest zdecydowanym zwycięzcą. Ale jeśli robisz większość swoich wstawek i wymazań z tyłu, wektor będzie wyraźnym zwycięzcą. Jeśli nie masz pewności, zadeklaruj swój kontener za pomocą typedef (aby łatwo było przełączać się tam iz powrotem) i dokonaj pomiaru.

— Howard Hinnant
źródło
3
Pytanie - czy komisja rozważała dodanie hybrydy tych dwóch (powiedzmy „talii”) do C ++? (tj. podwójnie zakończona vector.) Napisałem implementację, do której link znajduje się poniżej w mojej odpowiedzi . Może być równie szybki, vectorale ma znacznie szersze zastosowanie (np. Podczas tworzenia szybkiej kolejki).
— user541686
5

std::dequenie ma gwarantowanej pamięci ciągłej - i często jest nieco wolniejszy w przypadku dostępu indeksowanego. Deque jest zwykle implementowany jako „lista wektorów”.

— Erik
źródło
14
Nie sądzę, aby „lista wektorów” była poprawna: rozumiałem, że większość implementacji była „wektorem wskaźników do tablic”, chociaż zależy to od twojej definicji „listy” („listę” czytam jako „lista połączona , „co nie spełniałoby wymagań dotyczących złożoności.)
— James McNellis
2

Według http://www.cplusplus.com/reference/stl/deque/ , „w przeciwieństwie do wektorów, deques nie mają gwarancji posiadania wszystkich swoich elementów w ciągłych lokalizacjach pamięci, co eliminuje możliwość bezpiecznego dostępu za pomocą arytmetyki wskaźnikowej”.

Deques są nieco bardziej skomplikowane, po części dlatego, że niekoniecznie mają ciągły układ pamięci. Jeśli potrzebujesz tej funkcji, nie powinieneś używać deque.

(Wcześniej moja odpowiedź wskazywała na brak standaryzacji (z tego samego źródła, co powyżej, „deques mogą być implementowane przez określone biblioteki na różne sposoby”), ale w rzeczywistości dotyczy to prawie każdego standardowego typu danych bibliotecznych.)

— patrickvacek
źródło
5
std::dequejest nie mniej znormalizowany niż std::vector. Nie sądzę, aby wymagania dotyczące złożoności std::dequemożna było spełnić dzięki ciągłemu przechowywaniu.
— Jerry Coffin
1
Być może moje sformułowanie było słabe: chociaż prawdą jest, że standaryzacja nie jest dokładna, jak rozumiem, wektory są standaryzowane, aby były sekwencją koniugalną, a deki nie. Wydaje się, że jest to jeden decydujący czynnik.
— patrickvacek
1
@JerryCoffin: Których wymagań dotyczących złożoności dequenie można spełnić w przypadku ciągłego przechowywania?
— user541686
1
@Mehrdad: Szczerze mówiąc, nie pamiętam, co miałem na myśli. Ostatnio nie przyjrzałem się tej części normy na tyle, że czuję się komfortowo stwierdzając kategorycznie, że mój wcześniejszy komentarz był błędny, ale patrząc na to teraz, nie mogę też pomyśleć, jak by to było dobre.
— Jerry Coffin
3
@JerryCoffin: Wymagania dotyczące złożoności są w rzeczywistości trywialne: możesz przydzielić dużą tablicę i zacząć przesuwać sekwencję od środka na zewnątrz (wydaje mi się, że tak właśnie działa implementacja Mehrdada), a następnie ponownie przydzielić, gdy dojdziesz do końca. Problem z tym podejściem polega na tym, że nie spełnia ono jednego z wymagań deque, a mianowicie, że wstawienie na końcach nie unieważnia odniesienia do istniejących elementów. To wymaganie oznacza nieciągłą pamięć.
— Yakov Galka
0

Deque to kontener sekwencji, który umożliwia swobodny dostęp do swoich elementów, ale nie ma gwarancji ciągłego przechowywania.

— Sean
źródło
0

Myślę, że to dobry pomysł, aby wykonać test wydajności w każdym przypadku. I podejmij decyzję opierając się na tych testach.

Wolałbym std::dequeniż std::vectorw większości przypadków.

— George Gaál
źródło
1
Pytanie, czy którekolwiek można wydestylować spośród błędów rzeczowych i brakujących słów, brzmiało, dlaczego ktoś by wolał vector. Możemy wywnioskować, że dlaczego nie jest to następstwem. Stwierdzenie, że wolisz dequez nieznanych powodów od nieokreślonych testów, nie jest odpowiedzią.
— underscore_d
0

Z jednej strony wektor jest dość często po prostu szybszy niż deque. Jeśli w rzeczywistości nie potrzebujesz wszystkich funkcji deque, użyj wektora.

Z drugiej strony, czasami to robisz funkcje, które potrzebują wektor nie daje, w takim przypadku należy użyć deque. Na przykład wzywam każdego, aby spróbował przepisać ten kod bez użycia deque i bez ogromnej zmiany algorytmu.

— BenGoldberg
źródło
Faktycznie, na takich samych serii push_backi pop_backoperacji, deque<int>zawsze jest co najmniej 20% szybciej niż vector<int>w moich testów (GCC z O3). Myślę, że dlatego dequejest to standardowy wybór w przypadku std::stack...
— igel
-1

Zauważ, że pamięć wektorowa jest ponownie alokowana, gdy tablica rośnie. Jeśli masz wskaźniki do elementów wektorowych, staną się nieprawidłowe.

Ponadto, jeśli usuniesz element, iteratory staną się nieprawidłowe (ale nie „for (auto ...)”).

Edycja: zmieniono „deque” na „vector”

— Pierre
źródło
-1: Wstaw i usuń na początku lub na końcu NIE unieważnia odniesień i wskaźników do innych elementów. (Chociaż wstawianie i kasowanie w środku tak)
— Sjoerd
@Sjoerd Zmieniłem to na „wektor”.
— Pierre
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.