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.

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.

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.