Dlaczego std :: deque nie jest wektorem z pamięcią zarezerwowaną przed indeksem 0?

Question

O ile rozumiem, motywem deque jest zapewnienie kontenerowi o swobodnym dostępie z wydajnym push_front.

Powszechnie wymieniane zalety wektora w porównaniu do deque obejmują szybsze przechodzenie i at(), ale głównie jego kompatybilność z C, ponieważ gwarantuje przyległą pamięć. Deque nie, ponieważ jest zbiorem fragmentów pamięci, z których każda ma wiele wartości.

Jestem zdezorientowany. Dlaczego deque nie jest zbudowany jak wektor, ale z pamięcią zarezerwowaną przed indeksem 0 oprócz pamięci zarezerwowanej po indeksie size-1? Zapewniłoby to pamięć ciągłą, umożliwiłoby wydajną push_front, a nawet uniknęłoby dodatkowego pośrednictwa podczas dereferencji iteratorów.

Aby zminimalizować przesuwanie podczas wstawiania, zawarte wartości do przesunięcia zależą od punktu wstawienia. Jeśli wstawiasz w indeksie n przed size()/2, pozostały wartości przesunięcia do n. W przeciwnym razie przesuń w prawo wartości po n.

Czego mi brakowało, jest tak ważne, że deque to zbiór tablic wartości, a nie jeden wielki zestaw?

Answer 1

According to Wikipedia, to, co opisujesz, jest rzeczywiście jedną z możliwych implementacji, przynajmniej w ogóle.

Jednak standard C++ narzuca wymagania, które zasadniczo uniemożliwiają to jako implementację dla std::deque; [deque.modifiers] states:

Wstawienie na każdym końcu deque ... nie ma wpływu na ważność odniesień do elementów deque.

(dzięki @BenjaminLindley!)