std::deque

 

C++

Język

Nagłówki biblioteki standardowej

Koncepty

Biblioteka narzędzi

Biblioteka string

Biblioteka kontenerów

Biblioteka algorytmów

Biblioteka iteratorów

Biblioteka numeryczna

Biblioteka wejścia/wyjścia

Biblioteka lokalizacji

Biblioteka wyrażeń regularnych (C++11)

Biblioteka operacji atomowych (C++11)

Biblioteka obsługi wątków (C++11)

 

Kontenery

array (C++11)

vector

deque

forward_list (C++11)

list

set

multiset

map

multimap

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

stack

queue

priority_queue

 

std::deque

Metody

deque::deque

deque::~deque

deque::operator=

deque::assign

deque::get_allocator

Dostęp do elementów

deque::at

deque::operator[]

deque::front

deque::back

Iteratory

deque::begindeque::cbegin (C++11)

deque::enddeque::cend (C++11)

deque::rbegindeque::crbegin (C++11)

deque::renddeque::crend (C++11)

Pojemność

deque::empty

deque::size

deque::max_size

deque::shrink_to_fit

Modyfikatory

deque::clear

deque::insert

deque::emplace

deque::erase

deque::push_front

deque::emplace_front

deque::pop_front

deque::push_back

deque::emplace_back

deque::pop_back

deque::resize

deque::swap

 

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.

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)
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.

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

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.

Typy składowe

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

Metody

(constructor)	Konstruuje deque (publiczna metoda)
(destructor)	Niszczy deque (publiczna metoda)
operator=	przypisuje wartości do kontenera (publiczna metoda)
assign	przypisuje wartości do kontenera (publiczna metoda)
get_allocator	zwraca skojarzony alokator (publiczna metoda)
Dostęp do elementów
at	dostęp do wskazanego elementu, ze sprawdzeniem zakresów (publiczna metoda)
operator[]	dostęp do wskazanego elementu (publiczna metoda)
front	dostęp do pierwszego elementu (publiczna metoda)
back	dostęp do ostatniego elementu (publiczna metoda)
Iteratory
begin cbegin	zwraca iterator na początek kontenera (publiczna metoda)
end cend	zwraca iterator za koniec kontenera (publiczna metoda)
rbegin crbegin	zwraca odwrócony iterator na początek (publiczna metoda)
rend crend	zwraca odwrócony iterator za koniec kontenera (publiczna metoda)
Pojemność
empty	sprawdza, czy kontener jest pusty (publiczna metoda)
size	zwraca liczbę elementów (publiczna metoda)
max_size	zwraca maksymalną możliwą liczbę elementów (publiczna metoda)
shrink_to_fit (C++11)	zmniejsza zużycie pamięci poprzez zwolnienie nieużywanej pamięci (publiczna metoda)
Modyfikatory
clear	czyści zawartość (publiczna metoda)
insert	wstawia elementy (publiczna metoda)
emplace (C++11)	konstruuje element "w miejscu" (publiczna metoda)
erase	usuwa elementy (publiczna metoda)
push_back	dodaje element na koniec (publiczna metoda)
emplace_back (C++11)	konstruuje element "w miejscu" na końcu (publiczna metoda)
pop_back	usuwa ostatni element (publiczna metoda)
push_front	wstawia element na początek (publiczna metoda)
emplace_front (C++11)	konstruuje element "w miejscu" na początku (publiczna metoda)
pop_front	usuwa pierwszy element (publiczna metoda)
resize	zmienia liczbę przechowywanych elementów (publiczna metoda)
swap	zamienia zawartość (publiczna metoda)

Funkcje operujące na zawartości

operator==operator!=operator<operator<=operator>operator>=	leksykograficznie porównuje wartości w deque (szablon funkcji)
std::swap(std::deque)	specjalizacja dla algorytmu std::swap (szablon funkcji)

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