Kontenery sekwencyjne w C++ STL

Kontener to struktura danych umożliwiająca przechowywanie w zorganizowany sposób innych obiektów. Natywne biblioteki STL z C++ udostępniają wysokiej jakości kontenery zróźnicowane pod względem swoich właściwości. Kontenery w STL oparte są o szablony klasy (template class).

Kontenery sekwencyjne to specjalny rodzaj kontenerów, których zadaniem jest przechowywanie innych elementów w sposób zachowujący informacje o kolejności tych elemetów, co przekłada się na dostęp do tych elementów za pomocą pozycji relatywnej (iterator) lub absolutnej (indeks).

vector

Wektory zaimplementowane są w postaci dynamicznych tablic. Tak jak zwykłe tablice, przetrzymują swoje elementy w spójnym obszarze pamięci, co sprawia, że można się do nich dostać nie tylko poprzez iterator, ale również poprzez offset na wskaźniku do wektora. W odróźnieniu od zwykłych tablic, jest w nich zautomatyzowany proces alokacji większych obszarów pamięci (i zwalniania) przy dodawaniu (usuwaniu) nowych elementów.

Wektory najlepiej nadają się do:

  • Dostępu do elementów za pomocą indeksu pozycji (wskaźnika lub operatora []) (w stałym czasie)
  • Dodawania i usuwania elementów od końca (stały, zamortyzowany czas)

list

Lista jest implementowana w postaci kolejki dwukierunkowej, czyli elementy znajdują się oddzielnych obszarach pamięci, a są ze sobą połączone dzięki wskaźnikom na element następny oraz element poprzedzający. Lista nie zapewnia efektywnego dostępu do dowolnego elementu, więc nie można się odwoływać do elementów za pomocą pozycji absolutnej (indeksu), ale za pomocą iteratora.

Listy najlepiej nadają się do:

  • Wstawiania, przenoszenia i usuwania elementów gdziekolwiek w liście (stały czas)

deque

Jest to implementacja dwu-końcowej kolejki. Elementy mogą, ale nie muszą znajdować się w jednym bloku pamięci, więc nie jest bezpieczne odnoszenie się do nich poprzez wskaźniki. Jeżeli chodzi o wstawianie elementów to Daque umożliwia ich efektywne wstawianie z obu stron (lepiej niż wektor, który umożliwia efektywne wstawianie tylko od końca, ale gorzej niż lista, która umożliwia to efektywnie w dowolnym miejscu). Jeżeli chodzi o dostęp przez indeks pozycji to jest to mniej efektywne niż w przypadku wektora (gdyż elementy nie muszą znajdować się w jednym bloku pamięci), ale lepiej niż lista (gdyż w liście każdy element znajduje się w oddzielnym bloku pamięci i nie ma odwoływanie się za pomocą indeksu w ogóle).

Daque najlepiej nadają się do:

  • Dostępu do elementów za pomocą indeksu pozycji (operatora [])
  • Dodawania i usuwania elementów od początku oraz od końca