presentation_deque.md

std::deque<T>

Kolejka dwustronna

deque = double ended queue

---

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>

---

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