Dlaczego std :: stack domyślnie używa std :: deque?
Ponieważ jedyną operacją wymaganą do użycia kontenera w stosie są:
z powrotem()push_back ()pop_back ()Dlaczego domyślny kontener dla niego jest deque zamiast wektora?
Czy ponowny przydział deque nie daje bufora elementów przed frontem (), więc push_front () jest wydajną operacją? Czy te elementy nie są marnowane, ponieważ nigdy nie zostaną użyte w kontekście stosu?
Jeśli nie ma narzutu na używanie deque w ten sposób zamiast wektora, dlaczego domyślne dla priority_queue wektora nie jest również deque? (priority_queue wymaga front (), push_back () i pop_back () - zasadniczo takie same jak dla stosu)
Zaktualizowano na podstawie odpowiedzi poniżej:
Wydaje się, że sposób, w jaki deque jest zwykle implementowany, to tablica o zmiennej wielkości z tablicami o stałym rozmiarze. To sprawia, że rośnie szybciej niż wektor (który wymaga realokacji i kopiowania), więc dla czegoś takiego jak stos, który polega na dodawaniu i usuwaniu elementów, deque jest prawdopodobnie lepszym wyborem.
priority_queue wymaga intensywnego indeksowania, ponieważ każde usunięcie i wstawienie wymaga uruchomienia pop_heap () lub push_heap (). Prawdopodobnie sprawia to, że wektor jest lepszym wyborem, ponieważ dodanie elementu i tak jest ciągle amortyzowane.