STL: Standard Template Library

De C++ Standard Template Library biedt een kant en klaar raamwerk voor enkele veel gebruikte datastructuren. Het steunt op drie pijlers:

• Containers: de structuren die gegevens kunnen bevatten
• Iteratoren om door containers heen te wandelen
• Algoritmen die bewerkingen op containers kunnen uitvoeren

Omdat de containers van de STL als templates zijn uitgevoerd kun je ze gebruiken voor allerlei typen variabelen. Dit heeft een enorme impact op het aantal mogelijke varianten van een datastructuur en alle algoritmen daarvoor. Stel dat je algoritmes wilt maken voor verschillende containers van verschillende typen, dan heb je:

1. Data types
2. Containers
3. Algoritmen

Zonder STL zou je A*B*C varianten moeten maken, bv sorteer een vector van ints, sorteer een vector van floats, merge een vector van ints, merge een queue van floats, search een queue van floats...

Met STL hoef je slechts B+C varianten te maken: sort + merge + search + vector + queue + map etc...

Containers

• vector
• deque
• list
• set
• multiset
• map
• multimap
• stack
• queue
• priority queue
• bitset

Iteratoren

Algoritmen

Er zijn diverse typen algoritmen: sommige kijken alleen maar (read only, of nonmodifying), andere veranderen data, en weer andere veranderen de volgorde van de data. Bij elke categorie staan hier enkele voorbeelden.

nonmodifying

• for_each
• count
• find search for first element
• search search for first occurrence of subrange
• equal

modifying

• for_each
• copy
• merge
• fill
• replace

removing

• remove
• remove_if
• unique

mutating

• reverse
• rotate

sorting

• sort
• stable_sort

sorted range

• binary_search
• lower_bound
• upper_bound
• merge

Vector

Een vector lijkt op een array, alleen zonder pointergedoe en je hoeft niet bij te houden of je op plaatsen schrijft waar je niet mag schrijven want dat houdt de vector zelf in de gaten als je hem goed gebruikt. Elementen aan het einde toevoegen en weghalen is efficient bij een vector. Toevoegen en weghalen tussen het begin en eind is langzaam.

Methods:

• insert
• push_back
• pop_back

Deque

Een deque is een vector waarbij je ook aan het begin efficient elementen kunt toevoegen en weghalen.

Methods:

• insert
• push_back
• pop_back
• push_front
• pop_front

List

Een list is vooral interessant als invoegen of weghalen in het midden snel moet verlopen. Een list is traag als het gaat om zoeken van elementen of random-access.

Methods:

• insert
• push_back
• pop_back
• push_front
• pop_front

Het tussenvoegen van een element is een kwestie van de pijlen omleiden:

Set

Een set is (letterlijk) een verzameling elementen. Een set wordt vaak als binaire boom geimplementeerd, al hoef je dat als gebruiker ervan niet te weten. Een set is vooral interessant voor het snel opzoeken van elementen.

Methods:

• insert
• erase

Map

Een map is een verzameling key-value-paren. Een map wordt vaak als binaire boom geimplementeerd. Een map is vooral interessant voor het snel opzoeken van de key en de daarmee geassocieerde value.

Methods:

• insert
• erase

Stack

Ook wel bekend als LIFO: last-in first-out.

Methods:

• push
• top
• pop

Queue

Ook wel bekend als FIFO: first-in first-out.

Methods:

• push
• pop
• front
• back

Zie ook de voorbeelden.