Standard Template Library
Standard Template Library (STL) je softwarová knihovna jazyka C++, která výrazně ovlivnila mnoho částí standardní knihovny C++. STL poskytuje čtveřici komponent – algoritmy, kontainery, funkční objekty (objekty, které mohou být volány jako funkce) a iterátory. Knihovna STL by měla být dodávána s každým překladačem jazyka C++.
STL poskytuje soubor základních tříd jazyka C++, jako jsou kontejnery či asociativní pole, které mohou pracovat s libovolnými datovými typy, ať už vestavěnými (int, bool,…) nebo uživatelsky definovanými datovými strukturami za předpokladu, že umožňují jisté základní operace (jako kopírování či přiřazení). STL algoritmy jsou nezávislé na kontejnerech, což značně snižuje složitost knihovny.
Základním mechanismem knihovny STL jsou šablony. Díky tomuto řešení je možné dosáhnout polymorfismu řešeného v rámci kompilace (compile-time polymorfismus). Ten je obvykle efektivnější než tradiční run-time polymorfismus. Moderní kompilátory jsou navíc přizpůsobeny k minimalizaci negativních následků abstrakce plynoucích z masivního použití STL.
STL knihovna byla první vytvořenou knihovnou generických algoritmů a datových struktur C++, která sleduje čtyři základní myšlenky: generické programování, abstrakce (bez ztráty efektivity kódu), přizpůsobení Von Neumannově architektuře a hodnotovou sémantiku.
Obsah knihovny
Kontejnery
STL obsahuje sekvenční kontejnery, asociativní kontejnery a kontejnerové adaptéry. Standardní sekvenční kontejnery zahrnují vektor (vector), obousměrnou frontu (deque) a seznam (list). Standardní asociativní kontejnery jsou set, multiset, bitset, map a multimap. Kontejnerové adaptéry představují třídy queue, priority_queue, a stack. Kontejnerové adaptéry nepředstavují doslova třídy kontejnerů, jde pouze o třídy, které poskytují specifické rozhraní a funkčně spoléhají na některý z kontejnerů.
| Kontejner | Popis |
|---|---|
| Jednoduché kontejnery | |
| pair | Kontejner „pair“ představuje jednoduchý asociativní kontejner tvořený uspořádanou dvojicí datových elementů nebo objektů. První z dvojice je označen „first“, druhý „second“. Jejich pořadí je vždy pevné. STL „pair“ může být přiřazen, kopírován, nebo porovnáván. Pole objektů alokované v kontejnerech „map“ nebo „hash_map“ (popsáno níže) je implicitně typu „pair“, element „first“ pak představuje unikátní klíč, zatímco element „second“ představuje hodnotu tomuto klíči přiřazenou. |
| Sekvenční kontejnery | |
| vector | Vector reprezentuje dynamické pole, které podobně jako běžné pole jazyka C umožňuje okamžitý přístup k libovolnému prvku. Vektor je schopen automaticky měnit svou velikost, je-li do něj vložen či z něj odebrán prvek. Tato schopnost samozřejmě vyžaduje jistý režijní výpočetní čas. Vložení či vyjmutí do/z vrcholu (zadní části) vektoru zabere amortizovaný konstantní čas. Vkládání či mazání ze začátku či z prostředku vektoru má pak lineární časovou náročnost. Pro datový typ bool existuje optimalizace vektoru, která umožňuje hodnoty uchovávat po jednotlivých bitech. |
| list | Obousměrný seznam, prvky nejsou uchovávány v celistvém bloku paměti, ale každý prvek obsahuje adresu prvku předchozího a následujícího. Co do efektivity je na tom seznam opačně než vektor – pomalé vyhledávání a přístup k prvkům (lineární náročnost), ale rychlé vkládání a mazání prvků (konstantní čas). |
| deque (double-ended queue) | Vector obohacený o možnost vkládání/mazání na začátku pole, tyto operace probíhají v konstantním amortizovaném čase, stejně jako vkládání/mazání na konci pole. |
| Kontejnerové adaptéry | |
| queue | Kontejner reprezentuje FIFO frontu s využitím operací push/pop/front/back. Jakýkoliv sekvenční kontejner zahrnující funkce front(), back(), push_back(), and pop_front() být použit také jako fronta „queue“ (např. list nebo deque). |
| priority_queue | Kontejner reprezentuje prioritní frontu s využitím operací push/pop/top (prvek s nejvyšší prioritou je na vrcholu „top“). Jakýkoliv sekvenční kontejner s přístupem k libovolnému prvku (random-access), který zahrnuje funkce front(), push_back() a pop_back(), může být použit také jako fronta „priority_queue“ (např. vector nebo deque). Prvky kontejneru mohou také podporovat porovnávání (pro určení prvku s vyšší prioritou). |
| stack | Kontejner reprezentuje LIFO zásobník s využitím operací push/pop/top (naposledy přidaný prvek je na vrcholu „top“). Jakýkoliv sekvenční kontejner, který zahrnuje funkce back(), push_back() a pop_back() může být použit také jako zásobník „stack“ (např. vector, list nebo deque). |
| Asociativní kontejnery | |
| set | Množina umožňující vkládání/mazání. |
| multiset | Množina stejná jako set, navíc umožňuje duplikování prvků. |
| map | Asociativní pole, jedna položka pracuje s párem klíč, hodnota. Pomocí klíče je pak v poli adresována příslušná hodnota. |
| multimap | Stejné jako map, navíc umožňuje duplikování prvků. |
| hash_set hash_multiset hash_map hash_multimap | Stejné jako set, multiset, map nebo multimap, ale implementováno s použitím hashovací tabulky. |
Iterátory
STL implementuje pět různých typů iterátorů. Jsou to vstupní iterátory, výstupní iterátory, dopředné iterátory, obousměrné iterátory a iterátory s libovolným přístupem (random-access iterátory).
Iterátory jsou důležitým nástrojem umožňujícím obecnost knihovny STL. Například algoritmus pro obrácení sekvence prvků může být implementován použitím obousměrných iterátorů a následně může být stejná implementace využita s použitím listu, vectoru či deque. Uživatelsky vytvořené kontajnery musí pouze poskytnout iterátor, který implementuje rozhraní jednoho z pěti standardních iterátorů a následně všechny algoritmy z STL mohou být na kontajner použity.
Algoritmy
V knihovně STL je zahrnuto velké množství algoritmů pro provádění operací jako hledání či třídění.
Funktory
STL inkluduje třídy, které přetěžují operátory (operátor ()). Třídy s touto schopností se nazývají funkční objekty nebo funktory. Jsou užitečné především pro získání a uchování stavové informace ve funkci, jenž je poslána nějaké další funkci. Jako funkční objekt může být použit i klasický pointer na funkci.
Implementace
- Originální STL implementace – Stepanov and Lee. 1994, Hewlett-Packard. Není nadále udržováno.
- SGI STL, založeno na implementaci Stepanov & Lee. 1997, Silicon Graphics. Není nadále udržováno.
- libstdc++ od gnu (dříve část libg++)
- libc++ od LLVM
- STLPort, založen na SGI STL
- Rogue Wave standard library (HP, SGI, SunSoft, Siemens-Nixdorf)
- Dinkum STL library by P.J. Plauger
- Apache C++ Standard Library
Reference
- Alexander Stepanov and Meng Lee, The Standard Template Library. HP Laboratories Technical Report 95-11(R.1), 14 November 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.)
- Alexander Stepanov. Notes on Programming. [s.l.]: [s.n.], 2007. Dostupné online. Stepanov reflects about the design of the STL.
- Nicolai M. Josuttis. The C++ Standard Library: A Tutorial and Reference. [s.l.]: Addison-Wesley, 2000. Dostupné online. ISBN 0-201-37926-0.
- Scott Meyers. Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. [s.l.]: Addison-Wesley, 2001. ISBN 0-201-74962-9.
- Al Stevens. Al Stevens Interviews Alex Stepanov. Dr. Dobb's Journal. 1995. Dostupné online [cit. 18 July 2007].
- David Vandevoorde and Nicolai M. Josuttis. C++ Templates: The Complete Guide. [s.l.]: Addison-Wesley Professional, 2002. ISBN 0-201-73484-2.
- Atul Saini and David R. Musser, STL Tutorial and Reference Guide: C+ + Programming with the Standard Template Library. Foreword by Alexander Stepanov; [Copyright Modena Software Inc.] Addison-Wesley ISBN 0-201-63398-1
Externí odkazy
- C/C++ STL reference, includes C++0x features
- STL programmer's guide guide from SGI
- Apache (formerly Rogue Wave) C++ Standard Library Class Reference
- Apache (formerly Rogue Wave) C++ Standard Library User Guide
- Bjarne Stroustrup on The emergence of the STL (Page 5, Section 3.1)