Przestrzenie nazw
Warianty
Działania

Biblioteka kontenerów

Z cppreference.com
< cpp

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

Spis treści

[edytuj] Kontenery sekwencyjne

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

(C++11)
statyczna, ciągła tablica
(szablon klasy) [edit]
dynamiczna, ciągła tablica
(szablon klasy) [edit]
dwustronnie zakończona kolejka
(szablon klasy) [edit]
lista jednokierunkowa
(szablon klasy) [edit]
lista dwukierunkowa
(szablon klasy) [edit]

[edytuj] Kontenery asocjacyjne

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

kolekcja unikalnych kluczy, posortowana po kluczach
(szablon klasy) [edit]
słownik - kolekcja par klucz-wartość, posortowana po kluczach, klucze są unikalne
(szablon klasy) [edit]
kolekcja kluczy, posortowana po kluczach
(szablon klasy) [edit]
słownik - kolekcja par klucz-wartość, posortowana po kluczach
(szablon klasy) [edit]

[edytuj] 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)).

kolekcja unikalnych kluczy, haszowana po kluczach
(szablon klasy) [edit]
słownik haszowany - kolekcja par klucz-wartość, haszowana po kluczach, klucze są unikalne
(szablon klasy) [edit]
kolekcja kluczy, haszowana po kluczach
(szablon klasy) [edit]
słownik hashowany - kolekcja par klucz-wartość, haszowana po kluczach
(szablon klasy) [edit]

[edytuj] Adaptery kontenerów

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

adaptuje kontener w celu zapewnienia stosu (struktura danych LIFO)
(szablon klasy) [edit]
adaptuje kontener w celu zapewnienia kolejki (struktura danych FIFO)
(szablon klasy) [edit]
adaptuje kontener w celu zapewnienia kolejki priorytetowej
(szablon klasy) [edit]