Czym tak naprawdę jest deque w STL?

192

Patrzyłem na kontenery STL i próbowałem zorientować się, jakie one są naprawdę (tj. Zastosowana struktura danych), a deque mnie zatrzymał: na początku pomyślałem, że to podwójnie połączona lista, która umożliwi wstawianie i usuwanie z obu końców w stały czas, ale niepokoi mnie obietnica złożona przez operatora [], która ma być wykonana w stałym czasie. Na połączonej liście arbitralny dostęp powinien być O (n), prawda?

A jeśli jest to tablica dynamiczna, jak może dodawać elementy w stałym czasie? Należy wspomnieć, że może nastąpić realokacja i że O (1) jest zamortyzowanym kosztem, jak w przypadku wektora .

Zastanawiam się więc, jaka jest ta struktura, która umożliwia swobodny dostęp w stałym czasie, a jednocześnie nigdy nie musi być przenoszona w nowe, większe miejsce.

Zonko
źródło
4
możliwy duplikat dostępu deque STL przez indeks to O (1)?
fredoverflow
1
@Graham „dequeue” to inna popularna nazwa „deque”. Nadal zatwierdziłem edycję, ponieważ „deque” to zwykle nazwa kanoniczna.
Konrad Rudolph
@Konrad Thanks. Pytanie dotyczyło konkretnie deque C ++ STL, który używa krótszej pisowni.
Graham Borland,
2
dequeoznacza podwójnie zakończoną kolejkę , chociaż oczywiście rygorystyczny wymóg dostępu O (1) do środkowych elementów jest szczególny dla C ++
Matthieu M.

Odpowiedzi:

181

Deque jest nieco rekurencyjnie zdefiniowany: wewnętrznie utrzymuje podwójną kolejkę fragmentów o stałym rozmiarze. Każdy fragment jest wektorem, a sama kolejka („mapa” na poniższej grafice) fragmentów jest również wektorem.

schemat układu pamięci deque

Jest tam świetna analiza charakterystyk i jak to porównać do vectornad na CodeProject .

Standardowa implementacja biblioteki GCC wewnętrznie używa T**do reprezentowania mapy. Każdy blok danych T*ma przydzielony określony rozmiar __deque_buf_size(zależny od sizeof(T)).

Konrad Rudolph
źródło
27
To jest definicja deque, jak się jej nauczyłem, ale w ten sposób nie może zagwarantować stałego dostępu do czasu, więc czegoś brakuje.
stefaanv
14
W implementacjach @stefaanv, @Konrad: C ++ widziałem tablicę wskaźników do tablic o stałym rozmiarze. To faktycznie oznacza, że ​​push_front i push_back nie są tak naprawdę stałymi czasami, ale przy inteligentnych czynnikach wzrostu wciąż dostajesz amortyzowane stałe czasy, więc O (1) nie jest tak błędne, aw praktyce jest szybsze niż wektor, ponieważ zamieniasz pojedyncze wskaźniki zamiast całych obiektów (i mniej wskaźników niż obiektów).
Matthieu M.,
5
Dostęp przez cały czas jest nadal możliwy. Wystarczy, jeśli chcesz przydzielić nowy blok z przodu, odepchnij nowy wskaźnik na głównym wektorze i przesuń wszystkie wskaźniki.
Xeo,
4
Jeśli mapa (sama kolejka) była listą dwustronną, nie widzę, jak mogłaby pozwolić losowemu dostępowi O (1). Może być zaimplementowany jako bufor cykliczny, co pozwoliłoby na zwiększenie jego wydajności: Kopiuj tylko wskaźniki zamiast wszystkich elementów w kolejce. Wydaje się jednak, że jest to niewielka korzyść.
Wernight
14
@JeremyWest Dlaczego nie? Dostęp indeksowany trafia do i-procentowego B-tego elementu w i-B-tym bloku (B = rozmiar bloku), to wyraźnie O (1). Możesz dodać nowy blok w zamortyzowanym O (1), stąd dodawanie elementów jest zamortyzowane O (1) na końcu. Dodanie nowego elementu na początku to O (1), chyba że trzeba dodać nowy blok. Dodanie nowego bloku na początku nie jest O (1), to prawda, O (N), ale w rzeczywistości ma bardzo mały stały współczynnik, ponieważ wystarczy przesunąć wskaźniki N / B zamiast N elementów.
Konrad Rudolph
22

Wyobraź to sobie jako wektor wektorów. Tylko, że nie są standardowymi std::vector.

Wektor zewnętrzny zawiera wskaźniki do wektorów wewnętrznych. Kiedy jego pojemność zostanie zmieniona poprzez realokację, zamiast przydzielać całą pustą przestrzeń do końca, jak to std::vectorrobi, dzieli pustą przestrzeń na równe części na początku i na końcu wektora. To pozwala push_frontipush_back na tym wektorze występować zarówno w zamortyzowanym czasie O (1).

Zachowanie wektora wewnętrznego musi się zmieniać w zależności od tego, czy znajduje się z przodu, czy z tyłu deque. Z tyłu może zachowywać się normalnie, std::vectorgdy rośnie na końcu i push_backwystępuje w czasie O (1). Z przodu musi robić coś przeciwnego, rosnąc na początku z każdym push_front. W praktyce można to łatwo osiągnąć, dodając wskaźnik do elementu przedniego i kierunek wzrostu wraz z rozmiarem. Dzięki tej prostej modyfikacji push_frontmożna również ustawić czas O (1).

Dostęp do dowolnego elementu wymaga przesunięcia i podziału na odpowiedni indeks wektora zewnętrznego, który występuje w O (1), i indeksowania do wektora wewnętrznego, który jest również O (1). Zakłada się, że wszystkie wektory wewnętrzne mają stały rozmiar, z wyjątkiem tych na początku lub na końcu deque.

Mark Ransom
źródło
1
Wektory wewnętrzne można opisać jako o stałej pojemności
Caleth
18

deque = podwójnie zakończona kolejka

Pojemnik, który może rosnąć w dowolnym kierunku.

Deque jest zazwyczaj realizowane jako vectoro vectors(wykaz wektorów nie może dać stały czas dostępu losowego). Podczas gdy rozmiar wektorów wtórnych zależy od implementacji, powszechnym algorytmem jest stosowanie stałego rozmiaru w bajtach.

Alok Save
źródło
6
To nie całkiem wektory wewnętrzne. Struktury wewnętrzne mogły przydzielić, ale niewykorzystane moce zarówno na początku, jak i na końcu
Mooing Duck
@MooingDuck: Jest to naprawdę zdefiniowana implementacja. Może to być tablica tablic lub wektor wektorów lub cokolwiek, co może zapewnić zachowanie i złożoność wymagane przez standard.
Alok Zapisz
1
@Als: Nie myślę arrayo niczym ani vectoro niczym, co mogłoby obiecać zamortyzowane O(1)push_front. Przynajmniej wewnętrzna z tych dwóch struktur musi mieć zdolność O(1)push_front, której nie gwarantuje ani arrayani ani vector.
Mooing Duck,
4
@MooingDuck to wymaganie jest łatwo spełnione, jeśli pierwsza część rośnie od góry do dołu, a nie od dołu. Oczywiście standard vectortego nie robi, ale jest to wystarczająco prosta modyfikacja, aby to zrobić.
Mark Ransom
3
@ Mooing Duck, zarówno push_front, jak i push_back można łatwo wykonać w zamortyzowanym O (1) za pomocą struktury pojedynczego wektora. To tylko trochę więcej księgowości okrągłego bufora, nic więcej. Załóżmy, że masz regularny wektor pojemności 1000 ze 100 elementami w pozycjach od 0 do 99. Teraz, gdy zdarzy się push_Front, po prostu naciskasz na końcu, tj. W pozycji 999, a następnie 998 itd., Aż oba końce się spotkają. Następnie dokonujesz realokacji (z wykładniczym wzrostem, aby zagwarantować stałe czasy amortyzacji), tak jak w przypadku zwykłego wektora. Tak skutecznie potrzebujesz tylko jednego dodatkowego wskaźnika do pierwszego el.
plamenko
14

(To jest odpowiedź, którą podałem w innym wątku . Zasadniczo twierdzę, że nawet dość naiwne implementacje, używając jednego vector, są zgodne z wymogami „ciągłego niezamortyzowanego pchnięcia {przód, tył}”. Możesz być zaskoczony i myślę, że jest to niemożliwe, ale znalazłem inne istotne cytaty w standardzie, które definiują kontekst w zaskakujący sposób. Proszę o wyrozumiałość; jeśli popełniłem błąd w tej odpowiedzi, bardzo pomocne byłoby określenie, które rzeczy Powiedziałem poprawnie i gdzie moja logika się zepsuła).

W tej odpowiedzi nie próbuję zidentyfikować dobrej implementacji, staram się jedynie pomóc w interpretacji wymagań dotyczących złożoności standardu C ++. Cytuję z N3242 , co według Wikipedii jest najnowszym dokumentem normalizacyjnym C ++ 11. (Wygląda na to, że jest zorganizowany inaczej niż w ostatecznym standardzie, dlatego nie podam dokładnych numerów stron. Oczywiście reguły te mogły ulec zmianie w ostatecznym standardzie, ale nie sądzę, żeby tak się stało).

A deque<T>może być poprawnie zaimplementowany za pomocą vector<T*>. Wszystkie elementy są kopiowane na stos, a wskaźniki są przechowywane w wektorze. (Więcej o wektorze później).

Dlaczego T*zamiast T? Ponieważ standard tego wymaga

„Wstawienie na obu końcach deque unieważnia wszystkie iteratory deque, ale ma ma wpływu na ważność odniesień do elementów deque ”.

(mój nacisk). TheT*Pomaga zaspokoić to. Pomaga nam to również spełnić:

„Wstawienie pojedynczego elementu na początku lub na końcu znaku odwrotnego zawsze ..... powoduje pojedyncze wywołanie konstruktora T ”.

Teraz trochę (kontrowersyjny) bit. Po co używać a vectordo przechowywania T*? Daje nam losowy dostęp, co jest dobrym początkiem. Zapomnijmy na chwilę o złożoności wektora i starannie do tego budujmy:

Standard mówi o „liczbie operacji na zawartych obiektach”. Dladeque::push_front to wyraźnie 1 bo dokładnie jeden Tobiekt jest zbudowany i zero istniejących Tobiektów są odczytywane lub zeskanowane w jakikolwiek sposób. Ta liczba, 1, jest wyraźnie stała i jest niezależna od liczby obiektów znajdujących się obecnie w deque. To pozwala nam powiedzieć, że:

'Dla naszych deque::push_front liczba operacji na zawartych obiektach (Ts) jest stała i jest niezależna od liczby obiektów już znajdujących się w deque”.

Oczywiście liczba operacji na T*nie będzie tak dobrze wychowana. Gdy stanie się vector<T*>zbyt duży, zostanie przeniesiony i wiele innychT* nich zostanie skopiowanych. Więc tak, liczba operacji naT* będzie się bardzo różnić, ale Tnie wpłynie to na liczbę operacji na .

Dlaczego zależy nam na tym rozróżnieniu między liczeniem operacji Ta liczeniem operacjiT* ? Jest tak, ponieważ standard mówi:

Wszystkie wymagania dotyczące złożoności zawarte w tym punkcie są określone wyłącznie w odniesieniu do liczby operacji na zawartych obiektach.

Dla deque, zawarte obiekty są T, a nieT* , co oznacza, że ​​możemy zignorować każdą operację, którą kopiuje (lub ponownie przydziela) a T*.

Nie powiedziałem wiele o tym, jak wektor zachowuje się w deque. Być może interpretowalibyśmy go jako bufor kołowy (wektor zawsze przyjmuje maksimumcapacity() , a następnie przestawia wszystko do większego bufora, gdy wektor jest pełny. Szczegóły nie mają znaczenia.

W ostatnich kilku akapitach przeanalizowaliśmy deque::push_fronti związek między liczbą obiektów w deque już a liczbą operacji wykonanych przez push_front na zawartych Tobiektach. I stwierdziliśmy, że byli od siebie niezależni. Ponieważ standard wymaga, aby złożoność dotyczyła operacji na T, więc możemy powiedzieć, że ma ona stałą złożoność.

Tak, złożoność Operacji On-T * jest amortyzowana (z powodu vector), ale interesuje nas tylko złożoność Operacje On-T i jest ona stała (nie amortyzowana).

Złożoność vector :: push_back lub vector :: push_front nie ma znaczenia w tej implementacji; względy te dotyczą operacji, T*a zatem są nieistotne. Gdyby norma odnosiła się do „konwencjonalnego” teoretycznego pojęcia złożoności, wówczas nie ograniczyliby się wprost do „liczby operacji na zawartych obiektach”. Czy interpretuję to zdanie?

Aaron McDaid
źródło
8
Wydaje mi się, że to oszustwo! Kiedy określasz złożoność operacji, nie robisz tego tylko na niektórych częściach danych: chcesz mieć pojęcie o oczekiwanym czasie działania wywoływanej operacji, niezależnie od tego, na czym ona działa. Jeśli podążę za twoją logiką dotyczącą operacji na T, oznacza to, że możesz sprawdzić, czy wartość każdego T * jest liczbą pierwszą za każdym razem, gdy wykonywana jest operacja, i nadal przestrzegać standardu, ponieważ nie dotykasz Ts. Czy możesz określić, skąd pochodzą Twoje cytaty?
Zonko,
2
Myślę, że standardowi pisarze wiedzą, że nie mogą stosować konwencjonalnej teorii złożoności, ponieważ nie mamy w pełni określonego systemu, w którym znamy na przykład złożoność alokacji pamięci. Udawanie, że pamięć można przydzielić nowemu członkowi listniezależnie od aktualnego rozmiaru listy, jest nierealistyczne ; jeśli lista jest zbyt duża, alokacja będzie powolna lub zakończy się niepowodzeniem. Dlatego, o ile widzę, komitet podjął decyzję o sprecyzowaniu jedynie operacji, które można obiektywnie policzyć i zmierzyć. (PS: Mam inną teorię na inną odpowiedź.)
Aaron McDaid,
Jestem prawie pewien O(n), że liczba operacji jest asymptotycznie proporcjonalna do liczby elementów. IE, liczą się metaoperacje. W przeciwnym razie nie ma sensu ograniczać wyszukiwania do O(1). Ergo, listy połączone nie kwalifikują się.
Mooing Duck,
8
Jest to bardzo interesująca interpretacja, ale dzięki tej logice listmożna również zaimplementować a jako vectorwskaźnik (wstawienie w środku spowoduje wywołanie pojedynczej kopii konstruktora, niezależnie od wielkości listy, a O(N)przetasowanie wskaźników można zignorować, ponieważ nie są operacjami na T).
Mankarse,
1
To jest dobre prawnictwo językowe (choć nie zamierzam próbować wypytywać, czy rzeczywiście jest poprawne, czy też w normie jest jakiś subtelny punkt, który zabrania tej implementacji). Ale to nie jest użyteczna informacja w praktyce, ponieważ (1) typowe implementacje nie implementują w dequeten sposób i (2) „oszukuje” w ten sposób (nawet jeśli jest to dozwolone przez standard), gdy obliczanie złożoności algorytmicznej nie jest pomocne w pisaniu wydajnych programów .
Kyle Strand,
13

Z przeglądu możesz myśleć dequejakodouble-ended queue

przegląd ogólny

Dane w deque są przechowywane przez fragmenty wektora o stałym rozmiarze, które są

wskazywany przez map(który jest również kawałkiem wektora, ale jego rozmiar może się zmienić)

deque struktura wewnętrzna

Główny kod części deque iteratorjest następujący:

/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
    typedef __deque_iterator<T, buff_size>              iterator;
    typedef T**                                         map_pointer;

    // pointer to the chunk
    T* cur;       
    T* first;     // the begin of the chunk
    T* last;      // the end of the chunk

    //because the pointer may skip to other chunk
    //so this pointer to the map
    map_pointer node;    // pointer to the map
}

Główny kod części dequejest następujący:

/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
    public:
        typedef T              value_type;
        typedef T&            reference;
        typedef T*            pointer;
        typedef __deque_iterator<T, buff_size> iterator;

        typedef size_t        size_type;
        typedef ptrdiff_t     difference_type;

    protected:
        typedef pointer*      map_pointer;

        // allocate memory for the chunk 
        typedef allocator<value_type> dataAllocator;

        // allocate memory for map 
        typedef allocator<pointer>    mapAllocator;

    private:
        //data members

        iterator start;
        iterator finish;

        map_pointer map;
        size_type   map_size;
}

Poniżej dam ci podstawowy kod deque, głównie o trzech częściach:

  1. iterator

  2. Jak zbudować deque

1. iterator ( __deque_iterator)

Głównym problemem iteratora jest to, że gdy ++, - iterator może przejść do innej porcji (jeśli jest wskaźnikiem do krawędzi porcji). Na przykład, istnieją trzy kawałki danych: chunk 1, chunk 2, chunk 3.

Te pointer1wskaźniki do pocz? Tku chunk 2, gdy operator --pointerbędzie to wskaźnik do końca chunk 1, tak jak do pointer2.

wprowadź opis zdjęcia tutaj

Poniżej podam główną funkcję __deque_iterator:

Po pierwsze, przejdź do dowolnego fragmentu:

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + chunk_size();
}

Zauważ, że chunk_size() funkcja, która oblicza wielkość porcji, możesz pomyśleć, że zwraca 8 dla uproszczenia tutaj.

operator* pobierz dane do porcji

reference operator*()const{
    return *cur;
}

operator++, --

// przedrostek formy przyrostu

self& operator++(){
    ++cur;
    if (cur == last){      //if it reach the end of the chunk
        set_node(node + 1);//skip to the next chunk
        cur = first;
    }
    return *this;
}

// postfix forms of increment
self operator++(int){
    self tmp = *this;
    ++*this;//invoke prefix ++
    return tmp;
}
self& operator--(){
    if(cur == first){      // if it pointer to the begin of the chunk
        set_node(node - 1);//skip to the prev chunk
        cur = last;
    }
    --cur;
    return *this;
}

self operator--(int){
    self tmp = *this;
    --*this;
    return tmp;
}
iterator pomiń n kroków / dostęp losowy
self& operator+=(difference_type n){ // n can be postive or negative
    difference_type offset = n + (cur - first);
    if(offset >=0 && offset < difference_type(buffer_size())){
        // in the same chunk
        cur += n;
    }else{//not in the same chunk
        difference_type node_offset;
        if (offset > 0){
            node_offset = offset / difference_type(chunk_size());
        }else{
            node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
        }
        // skip to the new chunk
        set_node(node + node_offset);
        // set new cur
        cur = first + (offset - node_offset * chunk_size());
    }

    return *this;
}

// skip n steps
self operator+(difference_type n)const{
    self tmp = *this;
    return tmp+= n; //reuse  operator +=
}

self& operator-=(difference_type n){
    return *this += -n; //reuse operator +=
}

self operator-(difference_type n)const{
    self tmp = *this;
    return tmp -= n; //reuse operator +=
}

// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
    return *(*this + n);
}

2. Jak zbudować deque

wspólna funkcja deque

iterator begin(){return start;}
iterator end(){return finish;}

reference front(){
    //invoke __deque_iterator operator*
    // return start's member *cur
    return *start;
}

reference back(){
    // cna't use *finish
    iterator tmp = finish;
    --tmp; 
    return *tmp; //return finish's  *cur
}

reference operator[](size_type n){
    //random access, use __deque_iterator operator[]
    return start[n];
}


template<typename T, size_t buff_size>
deque<T, buff_size>::deque(size_t n, const value_type& value){
    fill_initialize(n, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::fill_initialize(size_t n, const value_type& value){
    // allocate memory for map and chunk
    // initialize pointer
    create_map_and_nodes(n);

    // initialize value for the chunks
    for (map_pointer cur = start.node; cur < finish.node; ++cur) {
        initialized_fill_n(*cur, chunk_size(), value);
    }

    // the end chunk may have space node, which don't need have initialize value
    initialized_fill_n(finish.first, finish.cur - finish.first, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::create_map_and_nodes(size_t num_elements){
    // the needed map node = (elements nums / chunk length) + 1
    size_type num_nodes = num_elements / chunk_size() + 1;

    // map node num。min num is  8 ,max num is "needed size + 2"
    map_size = std::max(8, num_nodes + 2);
    // allocate map array
    map = mapAllocator::allocate(map_size);

    // tmp_start,tmp_finish poniters to the center range of map
    map_pointer tmp_start  = map + (map_size - num_nodes) / 2;
    map_pointer tmp_finish = tmp_start + num_nodes - 1;

    // allocate memory for the chunk pointered by map node
    for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
        *cur = dataAllocator::allocate(chunk_size());
    }

    // set start and end iterator
    start.set_node(tmp_start);
    start.cur = start.first;

    finish.set_node(tmp_finish);
    finish.cur = finish.first + num_elements % chunk_size();
}

Załóżmy, że i_dequema 20 elementów int, 0~19których wielkość porcji wynosi 8, a teraz push_back 3 elementy (0, 1, 2) do i_deque:

i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);

To wewnętrzna struktura, jak poniżej:

wprowadź opis zdjęcia tutaj

Następnie push_back ponownie, wywoła przydzielanie nowej porcji:

push_back(3)

wprowadź opis zdjęcia tutaj

Jeśli my push_front, przydzielimy nową porcję przed poprzedniąstart

wprowadź opis zdjęcia tutaj

Zauważ, że gdy push_backelement w deque, wszystkie mapy i fragmenty są wypełnione, spowoduje to przydzielenie nowej mapy i dostosowanie fragmentów, ale powyższy kod może być wystarczający do zrozumienia deque.

Jayhello
źródło
Wspomniałeś: „Uwaga, gdy element push_back zostanie deque, jeśli wszystkie mapy i fragmenty zostaną wypełnione, spowoduje to przydzielenie nowej mapy i dostosowanie fragmentów”. Zastanawiam się, dlaczego standard C ++ mówi „[26.3.8.4.3] Wstawienie pojedynczego elementu na początku lub na końcu odwrotności zawsze zajmuje stały czas” w N4713. Przydzielenie części danych zajmuje więcej niż stały czas. Nie?
HCSF
7

Czytałem „Struktury danych i algorytmy w C ++” Adama Drozdka i uznałem to za przydatne. HTH.

Bardzo interesującym aspektem deque STL jest jego implementacja. Deque STL nie jest implementowany jako lista połączona, ale jako tablica wskaźników do bloków lub tablic danych. Liczba bloków zmienia się dynamicznie w zależności od potrzeb pamięci, a odpowiednio zmienia się rozmiar tablicy wskaźników.

W środku widać tablicę wskaźników do danych (fragmenty po prawej), a także można zauważyć, że tablica w środku zmienia się dynamicznie.

Obraz jest wart tysiąca słów.

wprowadź opis zdjęcia tutaj

Keloo
źródło
1
Dziękujemy za polecenie książki. Przeczytałem tę dequeczęść i jest całkiem dobra.
Rick
@ Rick z przyjemnością to słyszy. Pamiętam, jak w pewnym momencie zagłębiałem się w deque, ponieważ nie mogłem zrozumieć, w jaki sposób możesz mieć losowy dostęp ([] operator) w O (1). Również udowodnienie, że (push / pop) _ (back / front) zamortyzowało złożoność O (1) jest interesującym „momentem aha”.
Keloo
6

Chociaż standard nie nakazuje żadnej konkretnej implementacji (tylko losowy dostęp w stałym czasie), deque jest zwykle implementowany jako zbiór ciągłych „stron” pamięci. Nowe strony są przydzielane w razie potrzeby, ale nadal masz dostęp losowy. W przeciwieństwie do tego std::vector, nie obiecuje się, że dane są przechowywane w sposób ciągły, ale podobnie jak wektor, wstawki w środku wymagają dużo przeniesienia.

Kerrek SB
źródło
4
lub skreślenia w środku wymagają dużo przeniesienia
Mark Hendrickson,
Jeśli insertwymaga dużo relokacji w jaki sposób eksperyment 4 tutaj pokazać zdumiewające różnicę między vector::insert()a deque::insert()?
Bula
1
@Bula: Być może z powodu nieporozumienia ze szczegółami? Złożoność wstawki deque jest „liniowa pod względem liczby wstawionych elementów plus mniejsza odległość do początku i końca deque”. Aby poczuć ten koszt, musisz wstawić w bieżącym środku; czy to właśnie robi Twój test?
Kerrek SB,
@KerrekSB: artykuł z testem został wymieniony w odpowiedzi Konrada powyżej. Właściwie nie zauważyłem sekcji komentarzy w poniższym artykule. W wątku „Ale deque ma liniowy czas wstawiania?” autor wspomniał, że zastosował wstawianie w pozycji 100 przez wszystkie testy, co sprawia, że ​​wyniki są nieco bardziej zrozumiałe.
Bula