Przestrzenie nazw
Warianty
Działania

std::deque

Z cppreference.com
< cpp‎ | container
Zdefiniowane w nagłówku <deque>
template<

    class T,
    class Allocator = std::allocator<T>

> class deque;
(1)

std::deque (double-ended queue, dwustronnie zakończona kolejka) jest indeksowanym kontenerem sekwencyjnym, pozwalającym na szybkie dodawanie i usuwanie elementów zarówno na swoim końcu, jak i początku. Dodatkowo, usuwanie ani dodawanie na którymkolwiek z końców deque nigdy nie unieważni wskaźników ani referencji na pozostałe elementy.

W przeciwieństwie do std::vectora, elementy kontenera deque nie są przechowywane w ciągłej pamięci: typowa implementacja używa ciągu samodzielnie alokowanych tablic o ustalonym, niezmiennym rozmiarze, wraz z dodatkowym bookkeeping, co oznacza, że dostęp do elementu po indeksie wymaga dwóch dereferencji wskaźnika, w przeciwieństwie do wektora, u którego dostęp do elementu po indeksie wykonuje tylko jedną dereferencję.

Pamięć deque jest automatycznie rozszerzana lub kurczona, zależnie od potrzeb. Rozszerzenie deque jest mniej kosztowne niż rozszerzenie std::vectora , ponieważ nie pociąga za sobą kopiowania istniejących elementów do nowego miejsca w pamięci. Z drugiej strony, kontenery deque mają zwykle duży minimalny koszt pamięciowy; deque zawierająca zaledwie jeden element musi zaalokować całą wewnętrzną tablicę (np. 8 razy wielkość obiektu na 64-bitowym libstdc++; większa z wartości (16 razy wielkość obiektu i 4096 bajtów) na 64-bitowym libc++).

Złożoność obliczeniowa (wydajność) standardowych operacji na deque jest następująca:

  • Dostęp bezpośredni do elementu - stała O(1)
  • Wstawienie lub usunięcie elementu na końcu lub początku - stała O(1)
  • Wstawienie lub usunięcie elementu - liniowa względem odległości do bliższego z końców O(n)

std::deque spełnia wymagania Container, AllocatorAwareContainer, SequenceContainer i ReversibleContainer.

Spis treści

[edytuj] Parametry szablonu

T - Typ elementów.
T musi spełniać wymagania CopyAssignable i CopyConstructible. (do C++11)
Wymagania nałożone na elementy zależą od rzeczywiście wykonywanych na kontenerze operacji. Z reguły jest wymagane, aby typ elementu był typem kompletnym i spełniał wymagania Erasable, lecz wiele metod nakłada bardziej rygorystyczne warunki. (od C++11)

[edit]

Allocator - Alokator wykorzystywany do uzyskiwania/zwalniania pamięci i tworzenia/niszczenia elementów w tej pamięci. Typ musi spełniać wymogi Allocator. Zachowanie jest niezdefiniowane, jeśli Allocator::value_type nie jest identyczny jak T. [edit]

[edytuj] Unieważnienie iteratorów

Operacja Unieważnia
Operacje odczytu Nigdy
swap, std::swap Wartość end() może być unieważniona (zależne od implementacji)
shrink_to_fit, clear, insert, emplace,
push_front, push_back, emplace_front, emplace_back
Zawsze
erase Jeśli usuwane elementy znajdują się na początku - tylko do usuwanych elementów

Jeśli usuwane elementy znajdują się na końcu - tylko do usuwanych elementów i iterator zakońcowy
W innym wypadku- wszystkie iteratory zostają unieważnione (wliczając iterator zakońcowy).

resize Jeśli nowy rozmiar jest mniejszy niż stary : tylko do usuwanych elementów i iterator zakońcowy

Jeśli nowy rozmiar jest większy niż stary  : wszystkie iteratory zostają unieważnione
W innym wypadku - żadne iteratory nie zostają unieważnione.

pop_front Tylko do usuwanych elementów
pop_back Tylko do usuwanych elementów i iterator zakońcowy

[edytuj] Notka odnośnie unieważniania

  • Wstawienie elementów na któryś z końców kolejki za pomocą insert lub emplace nie unieważnia referencji.
  • push_front, push_back, emplace_front ani emplace_back nie unieważniają żadnych referencji do elementów deque.
  • Usuwanie elementów z któregoś z końców kolejki za pomocą erase, pop_front lub pop_back nie unieważnia referencji do pozostałych elementów.
  • Wywołanie resize z rozmiarem mniejszym, niż obecny nie unieważnia żadnych referencji do elementów, które nie zostały usunięte.
  • Wywołanie resize z rozmiarem większym, niż obecny nie unieważnia żadnych referencji do elementów deque.

[edytuj] Typy składowe

Typ składowy Definicja
value_type T [edit]
allocator_type Allocator [edit]
size_type Typ całkowitoliczbowy bez znaku (zwykle std::size_t) [edit]
difference_type Typ całkowitoliczbowy ze znakiem (zwykle std::ptrdiff_t) [edit]
reference
Allocator::reference (do C++11)
value_type& (od C++11)
[edit]
const_reference
Allocator::const_reference (do C++11)
const value_type& (od C++11)
[edit]
pointer
Allocator::pointer (do C++11)
std::allocator_traits<Allocator>::pointer (od C++11)
[edit]
const_pointer
Allocator::const_pointer (do C++11)
std::allocator_traits<Allocator>::const_pointer (od C++11)
[edit]
iterator RandomAccessIterator [edit]
const_iterator Constant RandomAccessIterator [edit]
reverse_iterator std::reverse_iterator<iterator> [edit]
const_reverse_iterator std::reverse_iterator<const_iterator> [edit]

[edytuj] Metody

Konstruuje deque
(publiczna metoda) [edit]
Niszczy deque
(publiczna metoda) [edit]
przypisuje wartości do kontenera
(publiczna metoda) [edit]
przypisuje wartości do kontenera
(publiczna metoda) [edit]
zwraca skojarzony alokator
(publiczna metoda) [edit]
Dostęp do elementów
dostęp do wskazanego elementu, ze sprawdzeniem zakresów
(publiczna metoda) [edit]
dostęp do wskazanego elementu
(publiczna metoda) [edit]
dostęp do pierwszego elementu
(publiczna metoda) [edit]
dostęp do ostatniego elementu
(publiczna metoda) [edit]
Iteratory
zwraca iterator na początek kontenera
(publiczna metoda) [edit]
zwraca iterator za koniec kontenera
(publiczna metoda) [edit]
zwraca odwrócony iterator na początek
(publiczna metoda) [edit]
zwraca odwrócony iterator za koniec kontenera
(publiczna metoda) [edit]
Pojemność
sprawdza, czy kontener jest pusty
(publiczna metoda) [edit]
zwraca liczbę elementów
(publiczna metoda) [edit]
zwraca maksymalną możliwą liczbę elementów
(publiczna metoda) [edit]
zmniejsza zużycie pamięci poprzez zwolnienie nieużywanej pamięci
(publiczna metoda) [edit]
Modyfikatory
czyści zawartość
(publiczna metoda) [edit]
wstawia elementy
(publiczna metoda) [edit]
(C++11)
konstruuje element "w miejscu"
(publiczna metoda) [edit]
usuwa elementy
(publiczna metoda) [edit]
dodaje element na koniec
(publiczna metoda) [edit]
konstruuje element "w miejscu" na końcu
(publiczna metoda) [edit]
usuwa ostatni element
(publiczna metoda) [edit]
wstawia element na początek
(publiczna metoda) [edit]
konstruuje element "w miejscu" na początku
(publiczna metoda) [edit]
usuwa pierwszy element
(publiczna metoda) [edit]
zmienia liczbę przechowywanych elementów
(publiczna metoda) [edit]
zamienia zawartość
(publiczna metoda) [edit]

[edytuj] Funkcje operujące na zawartości

leksykograficznie porównuje wartości w deque
(szablon funkcji) [edit]
specjalizacja dla algorytmu std::swap
(szablon funkcji) [edit]


[edytuj] Przykład

#include <iostream>
#include <deque>
 
int main()
{
    // Tworzy deque zawierającą liczby całkowite
    std::deque<int> d = {7, 5, 16, 8};
 
    // Dodaje liczby na początek i koniec kontenera
    d.push_front(13);
    d.push_back(25);
 
    // Iteruje po wartościach w deque i wypisuje je
    for(int n : d) {
        std::cout << n << '\n';
    }
}

Wynik:

13
7
5
16
8
25