05-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
• Rozmiar takiego kawałka zależy od kompilatora i implementacji biblioteki standardowej (nie ma jednej reguły)
• Dodatkowo deque posiada 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, bo alokujemy co najwyżej pamięć dla jednego, 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>

Operacje	Metody
dodawanie elementu	push_back(), emplace_back(), push_front(), emplace_front(), insert(), emplace()
modyfikowanie/dostęp do elementu	at(), operator[]
pierwszy/ostatni element	back(), front()
rozmiar	size()
wyczyszczenie nieużywanej pamięci	shrink_to_fit(),
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()

---

Przykład użycia

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d = {7, 5, 16, 8};

    d.push_front(13);
    d.push_back(25);

    for(const auto& n : d) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

Output:

13 7 5 16 8 25

---

Zadanie

• Znajdź dokumentację std::deque na cppreference.com
• Stwórz nowy plik 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