21.2 — Przegląd kontenerów STL

Zdecydowanie najczęściej używaną funkcjonalnością biblioteki STL są klasy kontenerów STL. Jeśli potrzebujesz szybkiego odświeżenia wiedzy na temat klas kontenerów, zapoznaj się z lekcją 23.6 — Klasy kontenerów.

STL zawiera wiele różnych klas kontenerów, których można używać w różnych sytuacjach. Ogólnie rzecz biorąc, klasy kontenerów można podzielić na trzy podstawowe kategorie: kontenery sekwencji, kontenery asocjacyjne i adaptery kontenerów. Zrobimy tutaj tylko krótki przegląd kontenerów.

Kontenery sekwencji

Kontenery sekwencji to klasy kontenerów, które utrzymują kolejność elementów w kontenerze. Cechą charakterystyczną kontenerów sekwencji jest to, że możesz wybrać miejsce wstawienia elementu według pozycji. Najbardziej typowym przykładem kontenera sekwencji jest tablica: jeśli wstawisz cztery elementy do tablicy, elementy będą dokładnie w tej kolejności, w jakiej je wstawiłeś.

Od C++11 STL zawiera 6 kontenerów sekwencji: std::vector, std::deque, std::array, std::list, std::forward_list i std::basic_string.

• Jeśli kiedykolwiek studiowałeś fizykę, prawdopodobnie myślisz o wektorze jako o obiekcie posiadającym zarówno wielkość, jak i kierunek. Niestety nazwana klasą vector w STL jest tablicą dynamiczną, która może rosnąć w miarę potrzeb, aby pomieścić jej elementy. Klasa wektora umożliwia losowy dostęp do swoich elementów za pomocą operatora[], a wstawianie i usuwanie elementów z końca wektora jest generalnie szybkie.

  Następujący program wstawia 6 liczb do wektora i używa przeciążonego operatora [], aby uzyskać do nich dostęp w celu ich wydrukowania.

  #include <vector>
  #include <iostream>
  
  int main()
  {
  
      std::vector<int> vect;
      for (int count=0; count < 6; ++count)
          vect.push_back(10 - count); // insert at end of array
  
      for (int index=0; index < vect.size(); ++index)
          std::cout << vect[index] << ' ';
  
      std::cout << '\n';
  }

  Ten program generuje wynik:
  10 9 8 7 6 5

• Klasa deque class (wymawiane „talia”) to klasa kolejki dwustronnej, zaimplementowana jako dynamiczna tablica, która może rosnąć z obu kończy się.

  #include <iostream>
  #include <deque>
  
  int main()
  {
      std::deque<int> deq;
      for (int count=0; count < 3; ++count)
      {
          deq.push_back(count); // insert at end of array
          deq.push_front(10 - count); // insert at front of array
      }
  
      for (int index=0; index < deq.size(); ++index)
          std::cout << deq[index] << ' ';
  
      std::cout << '\n';
  }

  Ten program generuje wynik:

  8 9 10 0 1 2

• A lista to specjalny typ kontenera sekwencji zwany listą podwójnie połączoną, w którym każdy element kontenera zawiera wskaźniki wskazujące następny i poprzedni element listy. Listy zapewniają dostęp tylko do początku i końca listy — nie jest zapewniony dostęp losowy. Jeśli chcesz znaleźć wartość pośrodku, musisz zacząć od jednego końca i „przemierzać listę”, aż dojdziesz do elementu, który chcesz znaleźć. Zaletą list jest to, że wstawianie elementów do listy jest bardzo szybkie, jeśli już wiesz, gdzie chcesz je wstawić. Generalnie do poruszania się po liście używa się iteratorów.

  W przyszłych lekcjach omówimy więcej zarówno list połączonych, jak i iteratorów.

• Chociaż klasa STL ciąg (i wstring) nie jest zazwyczaj uwzględniana jako typ kontenera sekwencji, zasadniczo tak jest, ponieważ można ją traktować jako wektor z elementami danych typu char (lub wchar).

Kontenery skojarzone

Kontenery skojarzone to kontenery, które automatycznie sortują dane wejściowe, gdy te dane wejściowe są wstawiane do kontenera. Domyślnie kontenery skojarzone porównują elementy za pomocą operatora<.

• A set to kontener przechowujący unikalne elementy, przy czym duplikaty elementów są niedozwolone. Elementy są sortowane według ich wartości.
• A multiset to zbiór, w którym dozwolone są duplikaty elementów.
• A map (nazywany także tablicą asocjacyjną) to zbiór, w którym każdy element jest parą, zwaną parą klucz/wartość. Klucz służy do sortowania i indeksowania danych i musi być unikalny. Wartością są rzeczywiste dane.
• A multimap (zwany także słownikiem) to mapa umożliwiająca duplikowanie kluczy. Słowniki z życia codziennego to multimapy: kluczem jest słowo, a wartością jest znaczenie słowa. Wszystkie klucze są posortowane w kolejności rosnącej, a wartość można wyszukiwać według klucza. Niektóre słowa mogą mieć wiele znaczeń, dlatego słownik jest multimapą, a nie mapą.

Adaptery kontenerów

Adaptery kontenerów to specjalne, predefiniowane kontenery, które są przystosowane do określonych zastosowań. Interesującą częścią adapterów kontenerów jest to, że możesz wybrać, jakiego kontenera sekwencji chcesz używać.

• A stos to kontener, w którym elementy działają w kontekście LIFO (Last In, First Out), gdzie elementy są wstawiane (wypychane) i usuwane (wysuwane) z końca kontenera. Stosy domyślnie używają deque jako domyślnego kontenera sekwencji (co wydaje się dziwne, ponieważ wektor wydaje się bardziej naturalnym dopasowaniem), ale może również używać wektora lub listy.
• A queue to kontener, w którym elementy działają w kontekście FIFO (pierwsze weszło, pierwsze wyszło), gdzie elementy są wstawiane (wypychane) na tył kontenera i usuwane (wysuwane) z przodu. Kolejki domyślnie używają deque, ale mogą także używać list.
• A Kolejka priorytetowa to typ kolejki, w której elementy są sortowane (poprzez operator<). Kiedy elementy są wypychane, element jest sortowany w kolejce. Usunięcie elementu z przodu zwraca element o najwyższym priorytecie w kolejce priorytetów.