Złożoność stl deque :: insert()

Question

dowiedziałem złożoność deque::insert() z C++ Standard 2003 (rozdział 23.2.1.3) w następujący sposób:

W najgorszym przypadku, wkładając jeden element w deque wymaga czasu liniowy w minimalnej odległości od punktu wstawienia do początku maski i odległości od punktu wstawienia do końca maski.

Zawsze rozumiem implementację stl deque jako zbioru porcji pamięci. W związku z tym wstawienie dotyczy tylko elementów w tej samej porcji pamięci, co pozycja wstawienia. Moje pytanie brzmi, co oznacza standard przez "liniowy w minimalnej odległości od punktu wstawienia do początku deque i odległość od punktu wstawiania do końca deque"?

Moje zrozumienie jest takie, że standard C++ nie wymusza określonej implementacji deque. Złożoność jest ogólnie najgorsza. Jednak w rzeczywistej implementacji w kompilatorach jest on liniowy względem liczby elementów w porcji pamięci, które mogą się różnić dla różnych rozmiarów elementów.

Innym domysłem może być to, że ponieważ insert() unieważni wszystkie iteratory, deque musi zaktualizować wszystkie iteratory. Dlatego jest liniowy.

Answer 1

std :: deque jest normalnie (zawsze?) Realizowany jako zbiór fragmentów pamięci, , ale zwykle nie wstawia zupełnie nowej porcji tylko po to, aby wstawić jeden nowy element w środku kolekcji . W takim przypadku narzędzie określi, czy punkt wstawiania znajduje się bliżej początku, czy końca, i przetasuje istniejące elementy, aby zrobić miejsce dla nowego elementu w istniejącej porcji. Doda tylko nową porcję pamięci na początku lub końcu kolekcji.

Answer 2

Liniowa liczba wstawianych elementów (kopia). Dodatkowo, w zależności od konkretnej implementacji biblioteki, dodatkowy liniowy czas do liczby elementów między pozycją a jednym z końców deque. Reference...

Answer 3

Twoje przypuszczenia są ... 99,9% prawdziwe. Wszystko zależy od rzeczywistej implementacji. To, co standard określa, to minimalny wymóg zarówno dla implementatorów (które nie mogą być standardowymi, jeśli nie pasują do specyfikacji), jak i użytkowników (które nie mogą spodziewać się "lepszych wyników" w przypadku pisania kodu niezależnego od implementacji).

Ideą specyfikacji jest porcja (a == jeden) niezainicjowanej pamięci, w której elementy są rozmieszczane wokół centrum ... aż do momentu, gdy będzie dla nich miejsce. Wstawianie w środku oznacza przesunięcie. Wstawianie z przodu lub z tyłu oznacza po prostu konstrukcję na miejscu. (gdy nie ma miejsca, dokonano realokacji) Indeksów i iteratorów nie można ufać po modyfikacji, ponieważ nie możemy założyć, co zostało przesunięte iw jakim kierunku.

Bardziej wydajna implementacja nie wykorzystuje pojedynczego fragmentu, ale wiele fragmentów do redystrybucji problemu "zmiany" i alokacji pamięci o stałej wielkości z podstawowego systemu (co ogranicza realokację i fragmentację). Jeśli kierujesz na jeden z nich, możesz spodziewać się lepszych wyników, w przeciwnym razie lepiej nie zakładać optymalizacji struktury.

Answer 4

Wydaje mi się, że lepiej posłużyć się schematem ... bawmy się sztuką ASCII!

Deque to zwykle układ porcji pamięci, ale wszystkie części przedniej i tylnej pamięci są pełne.Jest to konieczne, ponieważ deque jest RandomAccessContainer i dostać O (1) dostęp do dowolnego pojemnika, nie można posiadać numer nieograniczony pojemników, z którego można odczytać rozmiar:

bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; } 

T& operator[](size_t i) { 
    if (i < first.size) { return first[SIZE - i]; } 

    size_t const correctedIndex = i - first.size; 
    return buckets[correctedIndex/SIZE][correctedIndex % SIZE]; 
} 

operacje te są O (1) z powodu mnożenia/dzielenia!

W moim przykładzie przypuszczam, że porcja w pamięci jest pełna, gdy zawiera 8 elementów. W praktyce nikt nie powiedział, że rozmiar powinien zostać ustalony, tylko że wszystkie wewnętrzne wiadra będą miały ten sam rozmiar.

// Deque 
0:  ++ 
1: ++++++++ 
2: ++++++++ 
3: ++++++++ 
4: +++++ 

teraz powiedzieć, że chcemy wstawić w indeksie 13. To spada gdzieś w wiadrze oznaczonego 2. Istnieje kilka strategii możemy myśleć o:

• przedłużyć wiadro 2 (tylko)
• wprowadzić nową wiadro przed lub po 2 i przetasować tylko kilka elementów

ale te dwie strategie naruszałyby niezmiennego, że wszystkie „wewnętrzny” wiadra mają taką samą num elementy.

Dlatego jesteśmy w lewo z tasowania elementy dookoła, albo w kierunku początku lub końca (którakolwiek jest tańszy), w naszym przypadku:

// Deque 
0:  +++ 
1: ++++++++ 
2: +O++++++ 
3: ++++++++ 
4: +++++ 

Uwaga jak wiadro 0 rosła.

Ten shuffle oznacza, że ​​w najgorszym przypadku przeniesiesz połowę elementów: O (N/2).

deque ma wstawkę O (1) na początku lub na końcu, ponieważ istnieje tylko kwestia dodania elementu we właściwym miejscu lub (jeśli wiadro jest pełne), tworząc nowe wiadro.

Istnieją inne pojemniki, które mają lepsze zachowanie przy wstawianiu/wymazywaniu w losowych indeksach, na podstawie B+ Trees. W indeksowanym drzewie B + można zamiast "klucza" (lub równolegle) utrzymywać wewnętrznie liczbę elementów przed określoną pozycją. Istnieją różne techniki, aby to zrobić skutecznie. Na koniec otrzymasz pojemnik:

• O (1): puste, wielkość
• O (log N): co, wkładki, wymazać

Można sprawdzić moduł blist w Python, który implementuje element podobny do listy Pythona wspierany przez taką strukturę.