Czym tak naprawdę jest deque w STL?

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.

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.

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)).

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.

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.

(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?

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

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ć)

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.

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;
}

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:

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

push_back(3)

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

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.

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.

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.