Biblioteka kontenerów

 

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

 

Biblioteka kontenerów jest kolekcją szablonów klas i algorytmów, pozwalających programistom w łatwy sposób zaimplementować podstawowe struktury danych, jak kolejki, listy, stosy. Obecnie występują trzy rodzaje kontenerów -- kontenery sekwencyjne, kontenery asocjacyjne i nieuporządkowane kontenery asocjacyjne -- każdy z nich został zaprojektowany, aby zapewniać inny zestaw operacji.

Kontenery zarządzają pamięcią alokowaną do przechowywania ich elementów, i zapewniają metody pozwalające na dostęp do nich, bezpośrednio lub przez iteratory (obiekty o właściwościach podobnych do wskaźników).

Większość kontenerów ma co najmniej kilka wspólnych funkcji. Na to, który kontener jest najlepszy w konkretnym rozwiązaniu, wpływa nie tylko zapewniana przez kontenery funkcjonalność, ale również ich wydajność przy wykonywaniu konkretnych operacji.

Kontenery sekwencyjne

Kontenery sekwencyjne implementują struktury danych, które zapewniają sekwencyjny dostęp do ich elementów.

array (C++11)	statyczna, ciągła tablica (szablon klasy)
vector	dynamiczna, ciągła tablica (szablon klasy)
deque	dwustronnie zakończona kolejka (szablon klasy)
forward_list (C++11)	lista jednokierunkowa (szablon klasy)
list	lista dwukierunkowa (szablon klasy)

Kontenery asocjacyjne

Kontenery asocacyjne implementują posortowane struktury danych, które da się szybko przeszukiwać
(złożoność O(log n)).

set	kolekcja unikalnych kluczy, posortowana po kluczach (szablon klasy)
map	słownik - kolekcja par klucz-wartość, posortowana po kluczach, klucze są unikalne (szablon klasy)
multiset	kolekcja kluczy, posortowana po kluczach (szablon klasy)
multimap	słownik - kolekcja par klucz-wartość, posortowana po kluczach (szablon klasy)

Nieuporządkowane kontenery asocjacyjne

Nieuporządkowane kontenery asocjacyjne implementują nieposortowane (haszowane) struktury danych, które mogą być szybko przeszukiwane (zamortyzowana złożoność O(1), w najgorszym przypadku O(n)).

unordered_set (C++11)	kolekcja unikalnych kluczy, haszowana po kluczach (szablon klasy)
unordered_map (C++11)	słownik haszowany - kolekcja par klucz-wartość, haszowana po kluczach, klucze są unikalne (szablon klasy)
unordered_multiset (C++11)	kolekcja kluczy, haszowana po kluczach (szablon klasy)
unordered_multimap (C++11)	słownik hashowany - kolekcja par klucz-wartość, haszowana po kluczach (szablon klasy)

Adaptery kontenerów

Adaptery kontenerów zapewniają inny interfejs kontenerom sekwencyjnym, umożliwiając inny zakres operacji.

stack	adaptuje kontener w celu zapewnienia stosu (struktura danych LIFO) (szablon klasy)
queue	adaptuje kontener w celu zapewnienia kolejki (struktura danych FIFO) (szablon klasy)
priority_queue	adaptuje kontener w celu zapewnienia kolejki priorytetowej (szablon klasy)