H3_Collections.pdf

# Algemeen over collections Dit document biedt een introductie tot het concept van collections in C++, waarbij de basisprincipes, het beheer van elementen en de navigatie met iteratoren worden behandeld [1](#page=1) [2](#page=2). ### 1.1 Basisprincipes van collections Collections in C++ zijn klassen waarvan objecten worden aangemaakt om een verzameling van elementen te beheren. Elke collection biedt specifieke lidfuncties en operatoren om het gebruik te vereenvoudigen [3](#page=3). * **Elementtype:** Alle elementen binnen een enkele collection moeten van hetzelfde type zijn. Dit type kan zowel een basistype als een samengesteld type (een klasse) zijn [3](#page=3). * **Voorbeeld:** `set s;` declareert een collection genaamd `s` die alleen `string` elementen kan bevatten [3](#page=3). * **Groottebeheer:** De collection beheert intern het aantal elementen dat hij bevat. De huidige grootte kan worden opgevraagd met de `size()` lidfunctie [3](#page=3). * **Voorbeeld:** `cout << s.size();` drukt het aantal elementen in de set `s` af [3](#page=3). * **Kenmerken:** Elke collection heeft specifieke voor- en nadelen en is ontworpen met bepaalde kenmerken in gedachten [3](#page=3). ### 1.2 Iteratoren Iteratoren worden gebruikt om door de elementen van een collection te navigeren. Ze kunnen worden beschouwd als pointers naar individuele elementen binnen de collection [4](#page=4). * **Declaratie:** Een iterator wordt gedeclareerd met het type van de collection en het woord `iterator` (of `const_iterator` voor een iterator die de elementen niet mag wijzigen) [4](#page=4). * **Voorbeeld:** ```cpp list l; list::iterator it; // Iterator voor de list 'l' typename set::const_iterator cis; // Constante iterator voor een set van type T ``` * **Initialisatie naar het begin:** De `begin()` lidfunctie geeft een iterator terug die wijst naar het eerste element van de collection [5](#page=5). * **Voorbeeld:** `it = l.begin();` wijst de iterator `it` naar het eerste element van de list `l` [5](#page=5). * **Verplaatsen van iteratoren:** * `++it` of `it++`: Verplaatst de iterator naar het volgende element [5](#page=5). * `--it` of `it--`: Verplaatst de iterator naar het vorige element [5](#page=5). * `advance(it, n)`: Verplaatst de iterator `n` posities vooruit (of achteruit) [5](#page=5). * **Toegang tot elementen:** Het dereferentieer-symbool (`*`) wordt gebruikt om toegang te krijgen tot het element waar de iterator momenteel naar wijst [5](#page=5). * **Voorbeeld:** ```cpp cout << *it << endl; // Drukt het element af waar 'it' naar wijst *it = 10; // Wijzigt het element waar 'it' naar wijst naar 10 ``` * Voor collections die key-value paren opslaan, zoals `map`: `cout << (*it).first << it->second;` [5](#page=5). * **Het einde van de collection:** De `end()` lidfunctie retourneert een iterator die wijst naar de positie *na* het laatste element van de collection. Dit is nuttig om te controleren of alle elementen zijn doorlopen [6](#page=6). * **Belangrijk:** `end()` wordt ook gebruikt door de `find()` lidfunctie om aan te geven dat een gezocht element niet is gevonden [6](#page=6). ### 1.3 Door collections lopen met iteratoren Om alle elementen van een collection uit te schrijven met behulp van een iterator, wordt meestal een `while`-lus gebruikt in combinatie met `begin()` en `end()` [6](#page=6). * **Typische `while`-lus:** ```cpp list l; // ... vul de list 'l' ... list::iterator it = l.begin(); while (it != l.end()) { // Controleer of de iterator NIET gelijk is aan 'end()' cout << *it << endl; it++; // Verplaats naar het volgende element } ``` * **Alternatieven:** Er kan ook gebruik gemaakt worden van een `for`-lus of een *for-each* lus voor meer compacte code [6](#page=6). * **Opmerking over verplaatsing en dereferentie:** De uitdrukking `*it++` derefereert de iterator `it` (krijgt het element) en verhoogt vervolgens de iterator naar het volgende element. De volgorde is hier cruciaal [6](#page=6). > **Tip:** Gebruik altijd `it!= l.end()` om te controleren of je het einde van de collection hebt bereikt, en nooit `it < l.end()`, omdat de vergelijking met `<` niet altijd gedefinieerd is voor alle iteratortypes [6](#page=6). De inhoudsopgave van het document vermeldt de volgende secties na "Algemeen": Sequences, Container adapters, en Associatieve containers [2](#page=2) [7](#page=7). --- # Sequentiële containers (sequences) Sequentiële containers slaan elementen op in een lineaire volgorde [8](#page=8). ## 2. Sequentiële containers Sequentiële containers zijn datastructuren waarbij elk element, met uitzondering van het eerste en laatste, een linker- en rechterbuur heeft. De elementen worden in een specifieke, lineaire volgorde opgeslagen, en wanneer men de container doorloopt met een iterator, gebeurt dit in deze gedefinieerde volgorde. Dit impliceert dat er een `i`-de element bestaat binnen de sequentie [8](#page=8). ### 2.1 Voorbeelden van sequentiële containers De cursus bespreekt specifiek de groeitabel (ook wel bekend als `vector` in C++). Andere voorbeelden van sequentiële containers die niet verder worden uitgediept in deze cursus zijn de gelinkte lijst (`forward_list`) en de double-ended queue (`deque`), die als een vector met een efficiënte invoeging vooraan kan worden beschouwd [9](#page=9). ### 2.2 De groeitabel (vector) #### 2.2.1 Principe van de groeitabel Een groeitabel is een tabelgebaseerde container die dynamisch, dus tijdens de uitvoering van het programma, kan groeien. Bij de declaratie van een groeitabel wordt het type van de elementen vastgelegd en wordt een initiële capaciteit voorzien, wat het aantal beschikbare geheugenlocaties aangeeft [10](#page=10). #### 2.2.2 Elementtoevoeging in de groeitabel Er zijn twee scenario's mogelijk bij het toevoegen van een element aan een groeitabel [11](#page=11): 1. **Er is nog plaats beschikbaar:** Als het huidige aantal elementen (`n`) kleiner is dan de capaciteit van de tabel, wordt het nieuwe element op de eerstvolgende vrije index (`n`) geplaatst, en wordt `n` met één verhoogd [11](#page=11). 2. **Er is geen plaats meer beschikbaar:** Wanneer de capaciteit is bereikt, wordt er een nieuwe array met een grotere capaciteit gealloceerd. Alle elementen uit de oude array worden naar de nieuwe array gekopieerd, waarna de oude array wordt vrijgegeven. Het nieuwe element wordt vervolgens toegevoegd op index `n`, en `n` wordt verhoogd [11](#page=11). #### 2.2.3 Uitbreiding van de groeitabel Het proces van het alloceren van een nieuwe array en het kopiëren van elementen is een relatief kostbare operatie. Om de frequentie van deze dure herallocaties te minimaliseren, wordt de capaciteit van de array in de praktijk doorgaans verdubbeld bij elke herallocatie. Hoewel de gebruiker zich hier geen zorgen over hoeft te maken, is het in de praktijk wenselijk om deze verdubbelingen zoveel mogelijk te beperken om te voorkomen dat er te vaak opnieuw moet worden uitgebreid [12](#page=12). #### 2.2.4 C++ implementaties van groeitabellen In C++ zijn `string` en `vector` voorbeelden van groeitabellen [13](#page=13). #### 2.2.5 Declaratie en initialisatie van `vector` De declaratie van een `vector` vereist de `#include ` header en het gebruik van de `std` namespace [14](#page=14). * **Standaard declaratie:** `vector v1;` initialiseert een lege vector met een capaciteit en grootte van nul [14](#page=14). * **Declaratie met grootte:** `vector v2;` creëert een vector met een capaciteit en grootte van 6, waarbij de elementen worden geïnitialiseerd met de defaultwaarde (0 voor `int`) [15](#page=15) [6](#page=6). * **Declaratie met grootte en initiële waarde:** `vector v3(4, "test");` maakt een vector met een capaciteit en grootte van 4, waarbij alle elementen worden geïnitialiseerd met de string "test" [15](#page=15). * **Kopieerconstructor:** `vector v4(v2);` creëert een nieuwe vector `v4` die een kopie is van `v2` [15](#page=15). > **Tip:** Let op het verschil met `vector v2;`, wat een array van 6 lege vectoren definieert, niet een vector met 6 elementen. Het gebruik van constructors voor vectoren vervangt de noodzaak van `new` [14](#page=14) [15](#page=15) [6](#page=6). #### 2.2.6 Elementen toevoegen aan het einde De methode `void push_back(type e)` voegt een element `e` toe aan het einde van de vector en verhoogt de grootte (`size`) met 1 [16](#page=16). * **Voorbeeld:** Als `v4` initieel 3 elementen (met grootte 3 en capaciteit 3) bevat, zal `v4.push_back;` de vector uitbreiden met 8. De grootte wordt 4, en de capaciteit kan bijvoorbeeld 6 worden na een eventuele herallocatie. Vervolgens zal `v4.push_back;` het element 2 toevoegen [16](#page=16) [2](#page=2) [8](#page=8). #### 2.2.7 Toegang en aanpassing van elementen * **Indexering met `[]`:** Elementen kunnen worden benaderd en aangepast met de `[]` operator, bijvoorbeeld `v4 = -5;` [17](#page=17) [3](#page=3). > **Tip:** Het gebruik van de `[]` operator resulteert in een crash als de index groter is dan of gelijk is aan de capaciteit. Het is ook belangrijk om te weten dat `[]` de `size` van de vector niet aanpast. De index moet idealiter kleiner zijn dan de huidige `size` [17](#page=17). * **`size()` methode:** Geeft de huidige grootte (het aantal elementen) van de vector terug [17](#page=17). * **`capacity()` methode:** Geeft de huidige capaciteit (het aantal beschikbare geheugenplaatsen) van de vector terug [17](#page=17). #### 2.2.8 Andere nuttige methoden voor vectoren * **`front()`:** Geeft een referentie terug naar het eerste element van de vector. Kan gebruikt worden om het element te lezen of aan te passen (bv. `v.front() *= 2;`) [18](#page=18). * **`back()`:** Geeft een referentie terug naar het laatste element van de vector [18](#page=18). * **`at(int i)`:** Geeft een referentie terug naar het element op index `i`. Deze methode werpt een exception als de index `i` groter is dan of gelijk is aan de `size` van de vector [18](#page=18). * **`empty()`:** Controleert of de vector leeg is en retourneert `true` indien dit het geval is, anders `false` [18](#page=18). * **`clear()`:** Zet de grootte (`size`) van de vector op 0, terwijl de capaciteit ongewijzigd blijft [18](#page=18). * **`pop_back()`:** Verwijdert het laatste element uit de vector en vermindert de grootte (`size`) met 1 [19](#page=19). * **`resize(int n)`:** Past de grootte (`size`) van de vector aan naar `n`. Nieuw toegevoegde elementen worden geïnitialiseerd [19](#page=19). * **`reserve(int n)`:** Garandeert dat de capaciteit van de vector minimaal `n` is. De capaciteit wordt niet verkleind, en de inhoud wordt niet geïnitialiseerd; de grootte (`size`) blijft onveranderd [19](#page=19). #### 2.2.9 Toepassingen van `vector` * **Toepassing 1: Reeks gehele getallen lezen tot -1** Om een reeks gehele getallen in te lezen en op te slaan totdat -1 wordt ingevoerd, kan een `vector` gebruikt worden met `push_back` [20](#page=20). ```cpp vector v; int g; cin >> g; while (g != -1) { v.push_back(g); cin >> g; } ``` * **Toepassing 2: Een vooraf bepaald aantal gehele getallen lezen** Er zijn verschillende manieren om `n` gehele getallen in te lezen en op te slaan: * **Oplossing 1 (met C-style array):** Dit maakt gebruik van een C-style array van variabele grootte (`int t[n]`). Het nadeel is dat de grootte van een array achteraf niet meer kan worden aangepast [21](#page=21). ```cpp int n; cin >> n; int t[n; for (int i = 0; i < n; i++) { cin >> t[i; } ``` * **Oplossing 2 (met `vector::reserve` en `push_back`):** Hier wordt eerst de capaciteit gereserveerd met `v.reserve(n)`, waarna elementen worden toegevoegd met `push_back`. Dit is efficiënt omdat er minder herallocaties plaatsvinden. ```cpp int n, g; cin >> n; vector v; v.reserve(n); // Capaciteit wordt minstens n for (int i = 0; i < n; i++) { cin >> g; v.push_back(g); // Voegt element toe, size neemt toe } // Na dit proces: size = n, capaciteit = n (of meer) ``` > **Tip:** Men kan hier ook `cin >> v[i;` gebruiken, maar dan past de `size` van de vector zich niet automatisch aan. `push_back` is daarom beter geschikt in combinatie met `reserve` wanneer de uiteindelijke `size` gelijk is aan de gereserveerde capaciteit [22](#page=22). * **Oplossing 3 (met `vector` constructor en indexering):** De vector wordt direct geïnitialiseerd met de gewenste grootte `n`. Vervolgens worden de elementen direct op de juiste indexen ingelezen met `v[i]`. In dit geval is het gebruik van `push_back` niet nodig en zelfs inefficiënt, omdat de vector dan een onnodig grote interne structuur zou kunnen hebben [23](#page=23). ```cpp int n, g; cin >> n; vector v(n); // Vector met size = n en capaciteit = n for (int i = 0; i < n; i++) { cin >> v[i; // Directe toewijzing aan bestaande elementen } // Na dit proces: size = n, capaciteit = n ``` --- # Container adapters Container adapters zijn structuren die het gebruik van onderliggende collections beperken en een specifieke interface bieden, zoals stacks en queues. Ze worden geïmplementeerd met behulp van een van de reeds bestaande collections. Het primaire doel van een adapter is het aanpassen of beperken van de interface van een onderliggende datastructuur [25](#page=25). ### 3.1 Concept en functionaliteit Container adapters beperken het aantal toegankelijke elementen binnen de collectie. Dit betekent dat indexeren van elementen niet mogelijk is en er geen iteratoren beschikbaar zijn om door de collectie te navigeren. Ze definiëren slechts een beperkt aantal operaties die op de data kunnen worden uitgevoerd [25](#page=25). ### 3.2 Voorbeelden van container adapters Enkele veelvoorkomende voorbeelden van container adapters zijn: * **Stapel (stack)**: Een LIFO (Last-In, First-Out) datastructuur [25](#page=25). * **Wachtrij (queue)**: Een FIFO (First-In, First-Out) datastructuur [25](#page=25). * **Prioriteitswachtrij (priority\_queue)**: Een wachtrij waarbij elementen worden gesorteerd op prioriteit [25](#page=25). Deze specifieke adapters worden in de context van de cursus verder niet besproken [25](#page=25). --- # Associatieve containers Associatieve containers slaan gegevens op in de vorm van sleutel-waarde paren, waardoor efficiënte opslag en opvraging van informatie op basis van een sleutel mogelijk is [27](#page=27). ### 4.1 Verzamelingen (set) Een verzameling (set) is een collection waarin elk element uniek is en geen bijhorende informatie heeft; het element zelf fungeert als de sleutel. De volgende operaties zijn mogelijk: elementen toevoegen (indien al aanwezig gebeurt er niets), elementen opzoeken en de elementen overlopen [29](#page=29). #### 4.1.1 Families van verzamelingen Er zijn twee hoofd families van verzamelingen: 1. **Gebaseerd op een binaire zoekboom**: Elementen worden in gesorteerde volgorde opgeslagen en kunnen relatief snel toegevoegd of gevonden worden. In C++ wordt dit geïmplementeerd door de klasse `set`. De template parameter moet de `<` operator ondersteunen [30](#page=30). 2. **Gebaseerd op een hashtabel**: Elementen kunnen zeer snel toegevoegd of gevonden worden, maar de opslag is niet gesorteerd. In C++ wordt dit geïmplementeerd door de klasse `unordered_set`. De template parameter moet een hash-functie voorzien [30](#page=30). #### 4.1.2 Methoden voor `set` en `unordered_set` Enkele veelgebruikte methoden zijn [31-33](#page=31,32,33): * `pair insert(type x)`: Voegt element `x` toe als het nog niet aanwezig is. De methode retourneert een paar bestaande uit een iterator naar het element en een boolean die aangeeft of de toevoeging succesvol was [31](#page=31). > **Voorbeeld:** > ```cpp > set s; > s.insert [5](#page=5); > auto [it, b = s.insert; // Gebruik van structured binding (C++17) [1](#page=1). > if (b) { > cout << "Toegevoegd" << endl; > } > cout << *it << endl; // Output: 1 > ``` > [31](#page=31). * `int erase(type x)`: Verwijdert element `x` als het voorkomt. Retourneert het aantal keren dat `x` werd verwijderd (0 of 1) [32](#page=32). * `int count(type x)`: Telt hoe vaak element `x` voorkomt (0 of 1) [32](#page=32). * `void clear()`: Wist de volledige verzameling [32](#page=32). * `bool empty()`: Controleert of de verzameling leeg is [32](#page=32). * `int size()`: Geeft het aantal elementen in de verzameling terug [32](#page=32). Om de verzameling te overlopen, worden iteratoren of een for-each-lus gebruikt. Het gebruik van gewone for-lussen met indices is niet mogelijk omdat deze niet bestaan voor deze containers [32](#page=32). Iteratoren kunnen ook gebruikt worden voor het zoeken, toevoegen of verwijderen van elementen, hoewel dit zelden wordt gedaan [33](#page=33). * `iterator find(type x)`: Geeft een iterator terug naar het gezochte element, of de `end`-iterator als `x` niet voorkomt [33](#page=33). * `void erase(iterator it)`: Verwijdert het element waarnaar de iterator `it` verwijst [33](#page=33). * `iterator insert(iterator it, type x)`: Voegt `x` toe na (C++98) of vóór (C++11) de iterator `it`. Dit is enkel efficiënt als de iterator op de juiste positie staat [33](#page=33). ### 4.2 Multi-verzamelingen (multiset) Een multi-verzameling is een variant op de verzameling waarbij duplicaten wel worden bewaard. Een element kan dus meerdere keren voorkomen. In de C++ standard library kunnen de klassen `multiset` (gebaseerd op binaire zoekboom) en `unordered_multiset` (gebaseerd op hashtabel) gebruikt worden [34](#page=34). ### 4.3 Afbeeldingen (map) Een afbeelding (map), ook wel dictionary genoemd, is een collection van sleutel-waarde paren (key/value pairs). Bij het toevoegen wordt een sleutel en bijhorende waarde opgegeven, en via de sleutel kan de waarde opgezocht of gewijzigd worden. Een (multi)map is conceptueel een (multi)set van paren, waarbij bij een `map` de sleutels uniek zijn en bij een `multimap` niet [36](#page=36). #### 4.3.1 De (multi)map in C++ * **`map` en `multimap`**: Deze zijn gebaseerd op binaire zoekbomen. De paren worden opgeslagen in stijgende sleutelvolgorde, en de sleuteltypes moeten de `operator<` ondersteunen [37](#page=37). * **`unordered_map` en `unordered_multimap`**: Deze zijn gebaseerd op hashtabellen, wat snellere toegang biedt [37](#page=37). #### 4.3.2 Gebruik van `operator[]` in `map` Voor een `map` (niet `multimap`) kan de `operator[]` gebruikt worden om de bijhorende waarde op te vragen, in te stellen, of om een sleutel toe te voegen met een defaultwaarde indien de sleutel nog niet bestaat [37](#page=37). > **Nadeel:** Gebruik `operator[]` nooit bij een `const [unordered_]map&` omdat dit de const-correctheid schendt. Gebruik in dat geval `find` [38](#page=38). > > **Voorbeeld:** > ```cpp > map m; > m['a'] = 1; > m['b'] = 2; > m['a'] = 3; // Waarde bij sleutel 'a' wordt aangepast > cout << m['a'] << ' ' << m['c'; // Output: 3 0 > ``` > Hier wordt sleutel 'c' toegevoegd met de defaultwaarde 0 [38](#page=38). > > **Voordeel:** Kan de opbouw van een map erg compact maken. > ```cpp > map> m; // Sleutel = lengte string > string s; // ... lees strings ... > m[s.size().insert(s); // Voegt string s toe aan de set bij de key s.size() > ``` > [38](#page=38). #### 4.3.3 Methoden voor `map` en `unordered_map` Enkele veelgebruikte methoden zijn [39-41](#page=39,40,41): * `pair insert(const pair &p)`: Voegt paar `p` toe. Bij een `map` gebeurt dit enkel als de sleutel nog niet voorkomt [39](#page=39). > **Voorbeeld:** > ```cpp > map m; > m.insert(pair('b', 3)); > m.insert({'d', 9}); // Gebruik van initializer_list > ``` > [39](#page=39). * `int erase(type x)`: Verwijdert de sleutel `x` (en de bijhorende waarde) als deze voorkomt. Retourneert het aantal keren dat de sleutel werd verwijderd (0 of 1) [39](#page=39). * `int count(type x)`: Telt hoe vaak de sleutel `x` voorkomt (0 of 1 voor `map`, kan meer zijn voor `multimap`) [39](#page=39). * `void clear()`: Wist de volledige afbeelding [39](#page=39). * `bool empty()`: Controleert of de afbeelding leeg is [39](#page=39). * `int size()`: Geeft het aantal elementen (paren) in de afbeelding terug [39](#page=39). #### 4.3.4 Overlopen van (multi)maps Men kan een for-each-lus of iteratoren gebruiken om de (multi)map te overlopen [40](#page=40). > **Voorbeeld:** > ```cpp > map m; > // ... vul de map ... > > // Met for-each lus en structured binding (C++17) > for (const auto &[key, value: m) { > cout << key << "->" << value << endl; > } > > // Met iteratoren > for (auto it = m.begin(); it != m.end(); it++) { > cout << it->first << "->" << it->second << endl; > } > ``` > [40](#page=40). Net als bij verzamelingen, kunnen iteratoren gebruikt worden voor het zoeken, toevoegen of verwijderen van elementen, maar dit is enkel efficiënt als de iterator op de juiste positie staat [41](#page=41). * `iterator find(keytype x)`: Geeft een iterator terug naar de sleutel `x`, of de `end`-iterator indien `x` niet voorkomt [41](#page=41). * `void erase(iterator it)`: Verwijdert het element waarnaar de iterator `it` verwijst [41](#page=41). * `iterator insert(iterator it, pair p)`: Voegt paar `p` toe na (C++98) of vóór (C++11) de iterator `it` [41](#page=41). --- ## Veelgemaakte fouten om te vermijden - Bestudeer alle onderwerpen grondig voor examens - Let op formules en belangrijke definities - Oefen met de voorbeelden in elke sectie - Memoriseer niet zonder de onderliggende concepten te begrijpen

| Term | Definition | |------|------------| | Collections | Een verzameling van elementen van hetzelfde type, die verschillende functionaliteiten biedt voor het opslaan en beheren van data. Ze hebben specifieke lidfuncties en operatoren om het gebruik te vereenvoudigen. | | Lidfuncties | Functies die behoren tot een klasse en operaties uitvoeren op de objecten van die klasse, zoals het toevoegen of opvragen van elementen. | | Iteratoren | Een pointer-achtig object dat gebruikt wordt om elementen binnen een collection te doorlopen. Ze bieden een uniforme manier om toegang te krijgen tot elementen, ongeacht het type collection. | | begin() | Een lidfunctie van collections die een iterator retourneert die wijst naar het eerste element van de collection. | | end() | Een lidfunctie van collections die een iterator retourneert die wijst naar de positie na het laatste element van de collection. Wordt gebruikt als eindconditie in lussen. | | Sequences | Een type collection dat elementen in een lineaire, sequentiële volgorde opslaat. Elk element, behalve het eerste en laatste, heeft een linker- en rechterbuur. | | Groeitabel (vector) | Een dynamische array-achtige collection die automatisch kan groeien wanneer er nieuwe elementen worden toegevoegd. De capaciteit kan worden beheerd om efficiëntie te optimaliseren. | | Capaciteit | Het aantal elementen dat op dit moment in de onderliggende geheugenruimte van een collection kan worden opgeslagen zonder dat er een herallocatie nodig is. | | Grootte (size) | Het werkelijke aantal elementen dat momenteel in een collection aanwezig is. | | push_back() | Een functie die een element toevoegt aan het einde van een vector, waardoor de grootte van de vector met één toeneemt. | | pop_back() | Een functie die het laatste element uit een vector verwijdert en de grootte van de vector met één vermindert. | | reserve() | Een functie die de minimale capaciteit van een vector instelt. Dit kan vooraf geheugen toewijzen om frequente herallocaties te voorkomen. | | Container adapters | Interfaces die bovenop bestaande collections worden gebouwd om hun functionaliteit te beperken of aan te passen, zoals een stack of een queue. Ze bieden een vereenvoudigde set operaties. | | Stapel (stack) | Een LIFO (Last-In, First-Out) data-structuur die wordt geïmplementeerd met een container adapter. Elementen worden toegevoegd en verwijderd aan dezelfde kant (de top). | | Wachtrij (queue) | Een FIFO (First-In, First-Out) data-structuur die wordt geïmplementeerd met een container adapter. Elementen worden toegevoegd aan de achterkant en verwijderd aan de voorkant. | | Associatieve containers | Collections die gegevens opslaan als sleutel-waarde paren. Ze maken efficiënt zoeken, invoegen en verwijderen van gegevens mogelijk op basis van de sleutel. | | Set | Een associatieve container waarin elk element uniek is en geen bijbehorende informatie heeft. Elementen worden vaak in gesorteerde volgorde opgeslagen. | | Multiset | Een variant van de set waarin duplicaten van elementen zijn toegestaan. Een element kan dus meerdere keren voorkomen. | | Afbeelding (map) | Een associatieve container die een verzameling van unieke sleutel-waarde paren opslaat. Via de sleutel kan de bijbehorende waarde efficiënt worden opgezocht. | | Unordered_set | Een associatieve container die elementen opslaat op basis van een hash-tabel, wat resulteert in zeer snelle zoek- en invoegoperaties, maar de elementen worden niet in gesorteerde volgorde bewaard. | | Unordered_map | Een associatieve container die sleutel-waarde paren opslaat op basis van een hash-tabel. Dit biedt snelle toegang tot waarden via hun sleutels, zonder garanties over de volgorde. | | Hash tabel | Een datastructuur die sleutels omzet in indices in een array met behulp van een hash-functie, wat snelle gemiddelde tijdcomplexiteit voor zoek-, invoeg- en verwijderbewerkingen mogelijk maakt. | | Binaire zoekboom | Een boomdatastructuur waarin elk knooppunt een sleutel heeft en de sleutels in de linker subboom kleiner zijn dan de sleutel van het knooppunt, en de sleutels in de rechter subboom groter zijn. |