Wikipedia

Standard Template Library

softwarebibliotheek voor C++

De Standard Template Library of STL is een softwarebibliotheek voor de programmeertaal C++ die deel uitmaakt van de C++ Standard Library. De bibliotheek definieert een groot aantal standaard templates voor het afhandelen van algemene taken, zoals containers, iteratoren en algoritmes.

Beschrijving bewerken

De STL bestaat uit een kant en klare set van veel gebruikte klassen, zoals containers en associatieve arrays. Door middel van het templatesysteem van C++ kunnen deze klassen gebruikt worden voor zowel ingebouwde types als eigen gedefinieerde types, zolang ze een aantal elementaire operaties toelaten (zoals kopiëren en toewijzen). Ook deel van de STL is een aantal standaard algoritmes, waaronder sorteren en binair zoeken, die onafhankelijk zijn van de container waarin de datatypes worden opgeslagen.

Doordat de STL het templatesysteem van C++ gebruikt, levert het polymorfisme op compilatieniveau, wat in veel gevallen efficiënter is dan traditioneel run-time polymorfisme. Moderne C++ compilers houden rekening met extra abstractie, waardoor de kosten voor het gebruik van STL minimaal zijn.

De STL was de eerste softwarebibliotheek die gebruik maakte van generieke algoritmes en datastructuren, waarbij uitgegaan werd van vier ideeën:

  • Generiek programmeren
  • Abstractie zonder verlies van efficiëntie
  • De Von Neumann-architectuur
  • Value semantiek (dit houdt in dat waarden gekopieerd worden in plaats van dat er referenties gekopieerd worden)

Geschiedenis bewerken

De standaard bibliotheek van C++ is gebaseerd op een versie van STL zoals deze gepubliceerd is door Silicon Graphics, Inc. De gestandaardiseerde STL en de oorspronkelijke STL van Silicon Graphics, inc. verschillen echter op kleine punten; beide implementeren een aantal functionaliteiten die niet aanwezig zijn in de andere versie. Ook bestaat de STL versie van SGI enkel uit een set van header-bestanden, terwijl de ISO C++ standaard zowel implementatie van STL in header-bestanden als in een library-bestand toelaat.

Inhoud van de bibliotheek bewerken

Containers bewerken

De STL bestaat uit sequentiële containers en associatieve containers. Veel gebruikte sequentiele containers zijn vector, deque en list. De associatieve containers zijn onder andere set, multiset, map en multimap.

Container Beschrijving
Sequenties / lijsten - geordende collecties
vector Een dynamische lijst zoals een array in C (i.e., staat random access toe) met de toegevoegde mogelijkheid voor het automatisch groter en kleiner maken van de array. Het toevoegen en verwijderen van een element aan/van het einde van een vector heeft gemiddeld genomen (amortized) constante tijdscomplexiteit. Het toevoegen en verwijderen van een element aan het begin of in het midden van een vector kost gemiddeld genomen lineaire tijd.
list Een tweevoudig gekoppelde lijst. Elementen in een list worden in het geheugen niet opgeslagen in achtereenvolgende locaties, waardoor de tijdscomplexiteit van de operaties precies tegengesteld is aan een vector: een element opvragen is langzaam (lineaire tijdscomplexiteit) terwijl, als een positie eenmaal gevonden is, het toevoegen en verwijderen zeer snel gaat (constante tijd).
deque (double ended queue) Een vector waarbij toevoegen en verwijderen zowel aan het begin als aan het eind van de deque gemiddeld genomen in constante tijd gaat. Dit gaat echter ten koste van bepaalde garanties over het geldig blijven van iteratoren bij het toevoegen en verwijderen van elementen.
Collectie adapters
queue Een queue is een wachtrij en levert een FIFO-interface met de push/pop/front/back operaties. Iedere collectie die de front(), back(), push_back() en pop_front() operaties ondersteunt, kan gebruikt worden om een wachtrij te maken. Dit zijn onder andere de list en de deque.
priority_queue Een priority_queue is een wachtrij waar een prioriteit aan ieder element is gekoppeld. Elementen met een hoge prioriteit bevinden zich vooraan de wachtrij. De priority_queue levert een interface met de push/pop/top operaties. Een rij met willekeurige toegang die de operaties front(), push_back() en pop_front() ondersteunt, kan gebruikt worden om een priority_queue aan te maken. Dit zijn onder andere de vector en de deque.

Het elementtype moet de vergelijkingsoperator implementeren, om te bepalen welk element een hogere prioriteit heeft.

stack Levert een interface voor een LIFO stapel, met de push/pop/top operaties (het laatst toegevoegde element staat bovenaan). Iedere collectie die de operaties back(), push_back(), en pop_back() implementeert, kan gebruikt worden om een stack te initiëren. Dit zijn onder andere de vector, list en deque.
Associatieve containers - ongeordende collecties
set Een gesorteerde set (verzameling). Bij het toevoegen en verwijderen van elementen blijven iteratoren geldig. Ook zijn operaties zoals vereniging, doorsnede, verschil, symmetrisch verschil en het testen op aanwezigheid beschikbaar. Het datatype dat opgeslagen wordt in een set, moet de vergelijkingsoperator < (kleiner-dan) implementeren of er moet een alternatieve vergelijkingsfunctie gespecificeerd worden. Een set wordt geïmplementeerd met een self-balancing binaire zoekboom.
multiset Dit is hetzelfde als een set, maar staat duplicate elementen toe.
map Een gesorteerde associatieve array waarmee objecten van een bepaald type aan objecten van een ander bepaald type toegevoegd kunnen worden. Het eerste object wordt de key of sleutel genoemd en moet de vergelijkingsoperator < implementeren. Het tweede type wordt value of waarde genoemd en heeft deze eis niet. Ook een map wordt geïmplementeerd met een self-balancing binaire zoekboom.
multimap Een multimap is hetzelfde als een map maar staat duplicate elementen toe.
unordered_set

unordered_multiset
unordered_map
unordered_multimap

Deze zijn respectievelijk gelijk aan de set, multiset, map en multimap maar worden geïmplementeerd met een hashtabel. De keys worden niet gesorteerd maar gebruiken een hashfunctie die beschikbaar moet zijn voor het datatype.

Iteratoren bewerken

Een iterator levert ongeveer dezelfde basisfunctionaliteit als pointers, maar levert extra generalisatie door het abstraheren van de container waar de data in opgeslagen zit. De STL implementeert vijf verschillende type iteratoren, invoeriteratoren (deze kunnen alleen gebruikt worden voor het sequentieel lezen van waarden), uitvoeriteratoren (deze kunnen alleen gebruikt worden voor het sequentieel schrijven van waarden), voorwaartse iteratoren (deze kunnen worden gelezen, beschreven en in voorwaartse richting verplaatst worden), bidirectionele iteratoren (als voorwaartse iteratoren, maar kunnen ook verplaatst worden in achterwaartse richting) en random access iteratoren (deze kunnen vrijuit meerdere stappen in beide richtingen verplaatst worden in één operatie).

Algoritmes bewerken

Een groot deel van de algoritmes waarmee operaties zoals zoeken en sorteren geïmplementeerd worden, zijn deel van de STL. Ieder algoritme is specifiek geïmplementeerd voor de verschillende iteratortypes, waardoor het algoritme toegepast kan worden op iedere container die een bepaald iteratortype levert.

Functors bewerken

De STL bevat klassen die de functieoperator (operator()) overloaden. Deze klassen worden functors of functie-objecten genoemd. Deze kunnen gebruikt worden om functies een toestand te geven. Ook normale pointers naar functies kunnen gebruikt worden als functor.

Kritiek bewerken

Eisen aan de compiler bewerken

De gebruiksvriendelijkheid van de STL wordt in grote mate bepaald door de kwaliteit van de gebruikte C++ compiler:

  • Foutmeldingen die betrekking hebben op templates hebben de neiging om erg lang en moeilijk te ontcijferen te worden. Dit probleem wordt zo groot bevonden dat er enkele hulpprogramma's geschreven zijn die STL-gerelateerde foutmeldingen simplificeren en indenteren. Ook is er een voorstel voor de C++ standaard (genaamd concept checking) die dit probleem probeert te reduceren.
  • Onzorgvuldig gebruik van de STL templates kan leiden tot code bloat.
  • Het compileren van C++ met templates leidt tot verhoogde compilatietijd en geheugengebruik, soms zelfs magnituden hoger.

Referenties bewerken

Zie ook bewerken

  • Boost: een grote collectie van C++ bibliotheken die portable zijn en gecontroleerd worden op kwaliteit. Sommige bibliotheken van Boost worden toegevoegd in de volgende revisie van de C++ standaard.

Externe links bewerken

Overgenomen van "https://nl.wikipedia.org/w/index.php?title=Standard_Template_Library&oldid=65530734"