Dlaczego std :: stack domyślnie używa std :: deque?

91

Ponieważ jedyne operacje wymagane do użycia kontenera w stosie to:

  • plecy()
  • push_back ()
  • pop_back ()

Dlaczego domyślny kontener jest dla niego deque zamiast wektorem?

Czy deque realokacje nie dają bufora elementów przed front (), aby push_front () było wydajną operacją? Czy te elementy nie są marnowane, ponieważ nigdy nie będą używane w kontekście stosu?

Jeśli nie ma narzutu za użycie deque w ten sposób zamiast wektora, dlaczego domyślnym ustawieniem Priority_queue jest również wektor, który nie jest deque? (Priority_queue wymaga front (), push_back () i pop_back () - zasadniczo to samo, co dla stosu)


Zaktualizowano na podstawie poniższych odpowiedzi:

Wydaje się, że sposób, w jaki zwykle implementuje się deque, to tablica o zmiennej wielkości zawierająca tablice o stałym rozmiarze. To sprawia, że ​​rośnie szybciej niż wektor (co wymaga ponownej alokacji i kopiowania), więc w przypadku czegoś takiego jak stos, który polega na dodawaniu i usuwaniu elementów, deque jest prawdopodobnie lepszym wyborem.

Priority_queue wymaga silnego indeksowania, ponieważ każde usunięcie i wstawienie wymaga uruchomienia pop_heap () lub push_heap (). To prawdopodobnie sprawia, że ​​wektor jest tam lepszym wyborem, ponieważ dodanie elementu i tak jest nadal amortyzowane na stałe.

Greg Rogers
źródło
1
Rozumowanie w twojej „aktualizacji” nie jest całkiem poprawne. vector zwykle dodaje i usuwa elementy z końca szybciej niż deque. deque jest szybszy do powiększania pamięci , a nie do wypychania elementów.
Mooing Duck

Odpowiedzi:

75

Wraz ze wzrostem kontenera realokacja wektora wymaga skopiowania wszystkich elementów do nowego bloku pamięci. Wyhodowanie deque przydziela nowy blok i łączy go z listą bloków - nie są wymagane żadne kopie.

Oczywiście, jeśli chcesz, możesz określić, że ma być używany inny kontener zapasowy. Więc jeśli masz stos, o którym wiesz, że nie wzrośnie zbytnio, powiedz mu, aby używał wektora zamiast deque, jeśli takie jest twoje preferencje.

Michael Burr
źródło
1
Ale kiedy lista wskaźników do bloków rośnie, lista ta musi czasami zostać ponownie przydzielona, ​​tak jak wektor; asymptotycznie, jakikolwiek wzrost wydajności jest w najlepszym przypadku stałym czynnikiem. A manipulacja iteratorami potrzebna do poprawnego wykonania operacji push i pop jest znacznie bardziej skomplikowana std::dequeniż w przypadku std::vector, a operacje te będą prawdopodobnie używane znacznie częściej niż realokacje. Trudno mi uwierzyć, std::dequeże std::vectorw praktyce kiedykolwiek pobije .
Marc van Leeuwen
@Michael Burr: W takim razie dlaczego nie użyć list, dlaczego deque?
bappak
@MarcvanLeeuwen, jeśli chodzi o ciebie, mówisz, że trudno ci uwierzyć ... czy mógłbyś zająć jasne stanowisko? czy masz na myśli, że teraz wierzysz, std::dequeże masz szansę pokonać std::vectorw praktyce, czy też nadal w to wątpisz? dzięki.
aafulei
@fleix Nie rozumiem, dlaczego jest tak ważne, czy osobiście łatwiej mi wierzyć, że std::dequebędzie to równie dobre, jak std::vectorw praktycznych zastosowaniach. Ale bez względu na to, co jest warte, z mojego osobistego doświadczenia wynika, że ​​potrzebuję struktur danych stosu i kolejki nie do jednego dużego i kluczowego zadania, ale do wielu małych okazji, które można spryskać przez mój kod. W związku z tym bardziej zależy mi na zachowaniu na małych niż na dużych; i deque świeci tam szczególnie matowo. Wolę nie używać żadnych, ale (samodzielnie wdrażanych) list połączonych pojedynczo. Ale Twój przebieg może się różnić.
Marc van Leeuwen
12

Zobacz Guru Tygodnia 54 Herba Suttera, aby zapoznać się z względnymi zaletami wektorów i deque, w których każdy by się nadawał.

Wyobrażam sobie, że niespójność między Priority_queue i queue jest po prostu taka, że ​​zaimplementowali je różni ludzie.

James Hopkin
źródło
2
Priority_queue w rzeczywistości nie używa push / pop_front, a odwołania do elementów innych niż pierwszy są unieważniane przez operacje na stosie. Zatem żadna z zalet deque nie miałaby zastosowania, w przeciwieństwie do zwykłej kolejki.
Potatoswatter
9
Ponadto priority_queuemusi pozostać posortowany, więc wyższy koszt losowego dostępu deque::iteratorjest bardziej problematyczny.
Potatoswatter
1
@Potatoswatter: priority_queuema zachowany "magiczny porządek", nie jest posortowany. Jednak twój punkt widzenia jest ważny.
Mooing Duck