Skip to content

Latest commit

 

History

History
125 lines (90 loc) · 5.47 KB

presentation_deque.md

File metadata and controls

125 lines (90 loc) · 5.47 KB

std::deque<T>

Kolejka dwustronna

deque = double ended queue

Coders School

Cechy std::deque<T>

  • Hybryda listy oraz wektora
  • deque dzieli się na kawałki (ang. chunk), które są tablicami porozrzucanymi po pamięci
  • O wielkości takiego kawałka decyduje kompilator (nie ma jednej reguły)
  • Dodatkowo deque wyposażony jest w jeszcze jeden wektor, który przechowuje wskaźniki wskazujące początek każdego `chunka` w pamięci.
  • W ten sposób zyskujemy 2 rzeczy:
    • Dodawanie nowego elementu, jest szybsze, gdyż alokujemy zawsze pamięć dla całego chunka i nie będziemy przenosić elementów jak w std::vector<T>, gdy zabraknie nam miejsca na alokacje dodatkowej pamięci
    • Dane załadowane z jednego chunka są cache-friendly

Struktura std::deque<T>

deque

Cechy std::deque<T> cd.

  • Częściowo cache-friendly, czyli poszczególne `chunki` znajdą się w pamięci podręcznej procesora
  • Typ <T> może być dowolny. Zarówno typ wbudowany jak int, double, jak i własny zdefiniowany przez nas typ
  • Każdy `chunk` jest reprezentowany w pamięci jak tablica, natomiast same `chunki` nie sąsiadują ze sobą i są porozrzucane jak węzły listy
  • Dodanie nowego elementu jest szybkie
    • Jeżeli dany chunk ma jeszcze miejsce to dopisujemy go na koniec
    • Jeżeli nie, to alokowany jest nowy chunk i tam wpisywany jest nowy element
  • Usuwanie z początku i końca jest szybkie, bo powoduje jedynie przesunięcie iteratorów begin() lub end()
  • Usuwanie elementów ze środka jest kosztowne
  • Odczyt i modyfikacja jest szybka
    • Znamy rozmiar chunka, więc wiemy dokładnie, z którego pola w naszym wektorze pomocniczym powinniśmy odczytać adres chunka
    • Wiemy także, z którego pola odczytać daną, gdyż chunk jest ułożony jak tablica.

Dostęp do elementu

Matematycznie ujmując: jeżeli chunk ma 16 elementów a my chcemy dostać się do 100 elementu to:

  • x = 100 / 16 -> x = 6 (ucinamy część po przecinku)
  • y = 100 % 16 -> y = 4

Zatem wiemy, że jest to 4-ty element w 6-tym chunku

Ta wiedza jest zupełnie niepotrzebna przy użytkowaniu std::deque. Kontener zajmuje się tym automatycznie.

Operacje na std::deque<T>

  • dodawanie elementu: push_back(), emplace_back(), push_front(), emplace_front(), insert()
  • modyfikowanie/dostęp do elementu: at(), operator[]
  • pierwszy/ostatni element: back(), front()
  • rozmiar/czy kontener jest pusty: size(), empty()
  • wyczyszczenie nieużywanej pamięci: shrink_to_fit(),
  • iterator początku/końca: begin(), end()
  • odwrócony (ang. reverse) iterator: rbegin(), rend()
  • stały iterator: cbegin(), cend(), crbegin(), crend()
  • wyczyszczenie kontenera: clear()
  • przygotowanie elementu do usunięcia: remove() (nie jest metodą std::deque),
  • wymazanie elementów z pamięci: erase()
  • podmiana całego kontenera: swap()

Przykład użycia

#include <iostream>
#include <deque>

int main() {
    // Create a deque containing integers
    std::deque<int> d = {7, 5, 16, 8};

    // Add an integer to the beginning and end of the deque
    d.push_front(13);
    d.push_back(25);

    // Iterate and print values of the deque
    for(const auto& n : d) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

Output:

13 7 5 16 8 25

Zadanie 6

  • Znajdź dokumentację std::deque na cppreference.com
  • Stwórz nowy plik cpp i napisz funkcję main()
  • Stwórz pusty deque
  • Dodaj do niego 5 dowolnych wartości
  • Wyświetl deque
  • Usuń 2-gi i 4-ty element
  • Dodaj na początek i koniec wartość 30
  • Wyświetl deque
  • Dodaj na 4 pozycji liczbę 20
  • Wyświetl deque

Q&A