Skip to content

Latest commit

 

History

History
122 lines (87 loc) · 7.54 KB

05-deque.md

File metadata and controls

122 lines (87 loc) · 7.54 KB
Raw

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
  • 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>

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>

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