Cesko.wiki Standard Template Library
Author
Albert FloresStandard 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). +more 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). +more 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 | 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“. +more 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 | 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 | 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 | 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. +more 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. +more 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. +more 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, [url=http://www. stepanovpapers. +morecom]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. )[/url] * Stepanov reflects about the design of the STL. * * * * * 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
[url=http://en. cppreference. +morecom/w/cpp/container]C/C++ STL reference[/url], includes C++0x features * [url=http://www. sgi. com/tech/stl/]STL programmer's guide[/url] guide from SGI * [url=http://stdcxx. apache. org/doc/stdlibref/index. html]Apache (formerly Rogue Wave) C++ Standard Library Class Reference[/url] * [url=http://stdcxx. apache. org/doc/stdlibug/index. html]Apache (formerly Rogue Wave) C++ Standard Library User Guide[/url] * [url=https://web. archive. org/web/20050429214624/http://www. research. att. com/~bs/DnE2005. pdf]Bjarne Stroustrup on The emergence of the STL[/url] (Page 5, Section 3. 1).