Tárolók (STL)

Az STL (azaz Standard Template Library) egyik fontos részét képezik a tárolók, azok az adatszerkezetek, amelyek különféle tárolási stratégiákat implementálva hatékonyan, biztonságosan, kivételbiztosan és típushelyesen képesek tárolni az adatokat, ellentétben a C-stílusú, beépített tömbökkel és kézzel írt láncolt adatszerkezetekkel.

Filozófia

Az STL tárolóinak tervezése során azokat a szempontokat tartották szem előtt, amelyek a nyelv megalkotásakor: a hatékonyság és a kényelmes használat. Az általánosságot szem előtt tartva - de nem túlzásba esve - valósították meg a tárolókat: az elnevezések szabványosak, de nincs közös ősosztályuk, mert annyira különbözőek, hogy nagyon kövér felület alakulna ki.

Elemei

<bitset>

A bitset egy speciális bitvektor, templateparaméterként a méretét várja, így fordítási időben ismert, és rendkívül nagy hatékonysággal hajtja végre a bitműveleteket, bebillentett bitek megszámlálását.

<deque>

A deque (double-ended queue), azaz kétvégű sor egy olyan speciális sor, amelynek az elejére és a végére is értelmezve van a push és pop művelet, ellentétben a normál sorral vagy vektorral(amelyeknél csak 1-1 végre vannak ezek megvalósítva). Biztosít indexelő operátort, amivel konstans időben érhető el tetszőleges az elem, és a vektornál valamivel hatékonyabbak a belső insert és erase metódusok, de sűrű használat esetén érdemes lehet megfontolni a list használatát.

<list>

A list egy kétirányú láncolt listát bocsát a rendelkezésünkre, amellyel lineáris időben hajthatjuk végre az insert és az erase metódusokat, viszont az indexelés nem biztosított. Akkor érdemes listát használni, ha sűrűn kell az adatszerkezet belső részeit változtatni, és nem lényeges az elemek konstans idejű elérése, elég a szekvenciális. A list az elemeihez saját sort metódust biztosít, amivel hatékonyabban tudja rendezni magát, mint az STL részét képező sort algoritmus.

<map>

A map egy növekvően rendezetten tárolt asszociatív tömb, amely kulcs-adat párokat(std::pair<>) tárol, viselkedésében akár egy normál tömb. A kulcs és az adat típusa is paraméter. Az indexelés nem létező elemre új elemet hoz létre, alapértelmezett konstruktorral(ennek hiányában csak inserttel lehet létrehozás után bejuttatni elemeket), és a legtöbb tárolótól eltérően megköveteli, hogy a kulcstípushoz rendelkezésre álljon egy (szigorú részben)rendezés.

Tipikusan kiegyensúlyozott bináris keresőfával implementálják (a legtöbb esetben Vörös-fekete fával), de a szabvány ezt nem köti ki.

A map egy variánsa a multimap, amelyben egy kulcs többször is szerepelhet, így értelmetlenné válik a [] operátor, viszont megjelenik egy kulcs számossága.

<set>

A maphez hasonlóan a set (halmaz) is egy növekvően rendezett adatszerkezet, de itt csak kulcsok vannak önmagukban. Egy kulcs vagy szerepel a halmazban, vagy nem.

A maphoz hasonlóan a set is rendelkezik a kulcsismétlődést megengedő változattal (multiset), ekkor a kulcsok számosságáról lehet beszélni.

<vector>

A vectort a hagyományos, C-stílusú tömb kiváltására tervezték, azzal a kiegészítéssel, hogy méretét dinamikusan változtatja szükség szerint.

Fontos specializáció a bool sablonparaméterrel létrehozott vector (vector<bool>), amely egy biten tárolja az egyes értékeket, legalább nyolcadakkorára csökkentve a méretét a vectornak, de pont a bájtonkénti címezhetőség miatt problémás indexelő operátort és speciális iterátor szükségességét okozva.

<valarray>

A valarray a vektorhoz hasonló egydimenziós tömb, de az implementációt készítők sokkal nagyobb szabadságot kaptak az elkészítésekor, hiszen kifejezetten a nagyhatékonyságú matematikai számításokra tervezték, valamint speciális indexelési lehetőségei is vannak (sliceok).

<stack>

A stack, vagy verem az STL-ben egy nem önálló adatszerkezet, ráépül valamely fentebbi általánosabb tárolóra(többnyire a deque-ra), a felületét átalakítva egy veremére, mintegy burkoló osztályként(wrapper) működve.

<queue>

A sor a C++-ban, a veremhez hasonlóan, burkoló osztály, azaz a meglévő tárolókra ráépülve biztosítja a FIFO felületet. A fejállomány tartalmazza még a Prioritásos sort(priority_queue).

Műveletek

Sok tárolónak vannak speciális műveletei, amelyek szerepelnek az általános algoritmusok között, de hatékonyabban megvalósítható az adott tárolóra speciálisan, ilyen például a vector -on értelmezett csere (swap) vagy a list -re vonatkozó rendezés (sort).

Tároló	Listaműveletek	Indexelés	Front-műveletek	Back-(verem-)műveletek	Iterátor
bitset		Van
deque	O(n)	Van	Van	Van	Közvetlen
list	O(1)	Nincs	Van	Van	Kétirányú
map	O(log(n))	Van(O(log(n))			Kétirányú
set	O(log(n))	Nincs			Kétirányú
vector	O(n)	Van		Van	Közvetlen
valarray		Van			Közvetlen
stack				Van
queue			Van	Van
priority_queue			O(log(n))	O(log(n))