Standard Template Library

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

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

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

Containers

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

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

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

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

Eisen aan de compiler

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

• Alexander Stepanov en Meng Lee, The Standard Template Library. HP Laboratories Technical Report 95-11(R.1), November 14, 1995. (Revised version of A. A. Stepanov and M. Lee: The Standard Template Library, Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project, May 1994.)
• Nicolai M. Josuttis, The C++ Standard Library: A Tutorial and Reference. Addison-Wesley. ISBN 0-201-37926-0.
• Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley. ISBN 0-201-74962-9.
• David Vandevoorde en Nicolai M. Josuttis, C++ Templates: The Complete Guide. Addison-Wesley Professional 2002. ISBN 0-201-73484-2.

Zie ook

• 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

• (en) C/C++ reference inclusief een deel over de STL
• (en) STL programmer's guide de officiële handleiding van SGI
• (en) Bjarne Stroustrup on The emergence of the STL (Pagina 5, sectie 3.1)
• (en) Apache stdcxx een overdraagbare Open Source implementatie gebaseerd op de Rogue Wave STL
• (en) STLport een multiplatform STL implementatie