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

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.

c++ stl containers

— Greg Rogers
źródło

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:

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

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

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

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

Ponadto priority_queuemusi pozostać posortowany, więc wyższy koszt losowego dostępu deque::iteratorjest bardziej problematyczny.

— Potatoswatter

@Potatoswatter: priority_queuema zachowany "magiczny porządek", nie jest posortowany. Jednak twój punkt widzenia jest ważny.

— Mooing Duck