Standardní knihovna šablon

Knihovna standardních šablon (STL) ( anglicky  Standard Template Library ) je sada konzistentních generických algoritmů , kontejnerů , prostředků pro přístup k jejich obsahu a různých pomocných funkcí v C++ .

Knihovna standardních šablon, než byla zahrnuta do standardu C++ , byla vývojem třetí strany, nejprve od HP a později od SGI . Jazykový standard to nenazývá „STL“, protože tato knihovna se stala nedílnou součástí jazyka, nicméně mnoho lidí stále používá tento název, aby jej odlišili od zbytku standardní knihovny (I/O streamy ( iostream ), C pododdíl atd.).

Projekt nazvaný STLPort , založený na SGI STL, udržuje třídy STL, iostream a string aktuální. Několik dalších projektů také vyvíjí soukromé využití standardní knihovny pro různé konstrukční úlohy. Každý výrobce kompilátorů C++ musí dodat nějakou implementaci této knihovny, protože je velmi důležitou součástí standardu a je široce používána.

Architekturu STL navrhli Alexander Stepanov a Meng Li.

Struktura knihovny

Knihovna má pět hlavních součástí:

1. Kontejner ( anglicky  container ) - uložení sady objektů do paměti.
2. Iterátor ( anglicky  iterator ) - poskytující prostředky pro přístup k obsahu kontejneru.
3. Algoritmus je  definice výpočetní procedury .
4. Adaptér ( anglicky  adapter ) - přizpůsobení komponent pro poskytování jiného rozhraní.
5. Funkční objekt ( anglicky  functor ) - skrytí funkce v objektu pro použití jinými komponentami.

Separace umožňuje snížit počet součástí. Například místo psaní samostatné funkce vyhledávání prvků pro každý typ kontejneru je k dispozici jediná verze, která funguje s každým z nich, pokud jsou splněny základní požadavky.

Kontejnery

Kontejnery STL lze rozdělit do čtyř kategorií: sekvenční, asociativní, kontejnery adaptérů a pseudokontejnery.

Kontejner	Popis
Sekvenční kontejnery
vektor [1]	Dynamické pole s náhodným přístupem podobné C s automatickou změnou velikosti, když je prvek přidán/odebrán. Přístup pomocí indexu pro . Přidání/odstranění prvku na konec vektoru trvá amortizovaný čas, stejná operace na začátku nebo uprostřed vektoru trvá . Standardní rychlé třídění pro . Hledání prvku iterací trvá . Existuje specializace vektorové šablony na typ bool , který vyžaduje méně paměti tím, že ukládá prvky jako bity, ale nepodporuje všechny funkce iterátorů.
seznam [2]	Dvojitě propojený seznam , jehož prvky jsou uloženy v libovolných částech paměti, na rozdíl od vektorového kontejneru, kde jsou prvky uloženy v souvislé oblasti paměti. Vyhledávání podle výčtu je pomalejší než u vektoru kvůli delší době přístupu k prvku. Přístup pomocí indexu pro . Kdekoli v kontejneru je vkládání a mazání velmi rychlé - v .
paluba [3]	Oboustranná fronta . Kontejner je jako vektor, ale se schopností rychle vkládat a odstraňovat prvky na obou koncích v . Implementováno jako dvojitě propojený seznam lineárních polí . Na druhou stranu, na rozdíl od vektoru, deque nezaručuje, že všechny jeho prvky budou umístěny v souvislé paměti , což znemožňuje bezpečné použití ukazatelové aritmetiky [4] pro přístup k prvkům kontejneru [5] [6] .
Asociativní kontejnery
soubor	Seřazená sada jedinečných prvků. Při vkládání/odebírání prvků množiny se iterátory ukazující na prvky této množiny nestávají neplatnými. Poskytuje standardní operace s množinami, jako je sjednocení, průnik, odčítání. Typ prvku sady musí implementovat operátor porovnání operator<nebo musí být poskytnuta funkce komparátoru. Implementováno na základě samovyvažovacího binárního vyhledávacího stromu .
multiset	Stejné jako sada, ale umožňuje ukládat duplicitní prvky.
mapa	Uspořádané asociativní pole dvojic prvků sestávající z klíčů a jejich odpovídajících hodnot. Klíče musí být jedinečné. Pořadí prvků je určeno klávesami. V tomto případě musí typ klíče implementovat operátor porovnání operator<, nebo musíte poskytnout funkci komparátoru.
multimapa	Stejné jako mapa, ale umožňuje uložit více stejných klíčů.
Adaptérové ​​nádoby
zásobník	Stoh  je kontejner, do kterého se přidávají a odebírají prvky z jednoho konce.
fronta	Fronta  je kontejner, z jehož jednoho konce můžete přidávat prvky a z druhého je odebírat.
prioritní_fronta	Prioritní fronta organizovaná tak, že největší prvek je vždy na prvním místě.
Pseudo kontejnery
bitset	Slouží k uložení bitových masek. Vypadá to na vector<bool>pevnou velikost. Velikost je pevná, když je deklarován objekt bitset. Bitset neobsahuje žádné iterátory. Optimalizováno pro velikost paměti.
základní_řetězec	Kontejner pro ukládání a zpracování řetězců. Ukládá prvky v řadě do paměti jako jeden blok, což umožňuje organizovat rychlý přístup k celé sekvenci. Položky musí být PODy . Zřetězení je definováno pomocí +.
valarray	Šablona se používá k ukládání číselných polí a je optimalizována pro dosažení zvýšeného výpočetního výkonu. Poněkud podobné vektoru, ale postrádá většinu standardních operací s kontejnery. Operace jsou definovány na dvou valarray a na valarray a skalárním (elementově). Tyto operace lze efektivně implementovat jak na vektorových procesorech, tak na skalárních procesorech s bloky SIMD .

Kontejnery používají k ukládání prvků sémantiku objekt po hodnotě. Jinými slovy, po přidání kontejner získá kopii prvku. Pokud je vytvoření kopie nežádoucí, použije se kontejner ukazatelů na prvky. Prvky jsou přiřazeny pomocí operátoru přiřazení a jsou zničeny pomocí destruktoru. V tabulce jsou uvedeny základní požadavky na prvky v kontejnerech:

Všechny "plné" standardní kontejnery splňují určitý soubor požadavků (nebo konvencí). Níže uvedená tabulka předpokládá, že C je třída kontejneru obsahující objekty typu T.

Iterátory

Knihovna STL používá jako prostředníka pro přístup k prvkům zobecněnou abstrakci zvanou iterátor . Každý kontejner udržuje „svůj vlastní“ druh iterátoru, což je „modernizovaný“ inteligentní ukazatel [7] , který „ví“, jak přistupovat k prvkům konkrétního kontejneru. Standard C++ definuje pět kategorií iterátorů, které jsou popsány v následující tabulce:

Viz také

• C++ šablony
• Generické programování
• Posílit

Poznámky

1. ↑ std::vektor . Datum přístupu: 14. února 2016. Archivováno z originálu 27. listopadu 2015. (neurčitý)
2. ↑ std:list
3. ↑ std::deque . Získáno 14. února 2016. Archivováno z originálu 5. února 2016. (neurčitý)
4. ↑ Syntaxe ukazatelů v C++ . Získáno 14. února 2016. Archivováno z originálu 11. března 2016. (neurčitý)
5. ↑ Knihovna iterátoru (downlink) . Získáno 14. února 2016. Archivováno z originálu 5. února 2016. (neurčitý) 
6. ↑ Koncepty C++: Iterátor . Získáno 14. února 2016. Archivováno z originálu 19. února 2016. (neurčitý)
7. ↑ Typy iterátorů : Výstup vs. vstup vs. dopředu vs. Iterátor náhodného přístupu . Získáno 14. února 2016. Archivováno z originálu 23. února 2016. (neurčitý)

Odkazy

•  Zdroj odkazu na třídu a metodu SGI STL
• STL krok za krokem  (rus.)  - články Artema Kaeva
• Základy C++. Knihovna STL Archivována 27. února 2007 na Wayback Machine  (Russian)  - archiv konference
• STL - Standardní knihovna šablon. C++ programátor's guide  (rus.)  - podrobný průvodce
• Použití STL v C++  (ruština)

Literatura

• Scott Meyers. Efektivní využití STL = Effective STL. - Petr, 2002. - S.  224 . — (Knihovna programátorů). — ISBN 5-94723-382-7 .
• David R. Musser, Gilmer J. Durge, Atul Seini. C++ a STL: Referenční příručka = Výukový program a referenční příručka STL: Programování v C++ se standardní šablonou. — 2. vydání. - M. : "Williams" , 2010. - S. 432. - (C ++ v řadě Depth). — ISBN 5-89818-027-3 .
• Leen Ammeraal. STL pro programátory C++ = STL pro programátory C++. - DMK Press, 1999. - S. 240. - ISBN 5-256-00704-1 .