Standardní knihovna šablon - Standard Template Library

Další použití viz STL .

Standardní knihovna C ++
Kontejnery
Standardní knihovna C.

Standard Template Library ( STL ) je softwarová knihovna pro C ++ programovací jazyk, který ovlivnil mnoho částí standardní knihovny C ++ . Poskytuje čtyři komponenty nazývané algoritmy , kontejnery , funkce a iterátory .

STL poskytuje sadu běžných tříd pro C ++, jako jsou kontejnery a asociativní pole , které lze použít s jakýmkoli vestavěným typem a jakýmkoli uživatelem definovaným typem, který podporuje některé základní operace (například kopírování a přiřazování). Algoritmy STL jsou nezávislé na kontejnerech, což výrazně snižuje složitost knihovny.

STL dosahuje svých výsledků pomocí šablon . Tento přístup poskytuje polymorfismus v době kompilace, který je často účinnější než tradiční polymorfismus za běhu . Moderní kompilátory C ++ jsou vyladěny tak, aby minimalizovaly sankce za abstrakci vyplývající z intenzivního používání STL.

STL byla vytvořena jako první knihovna generických algoritmů a datových struktur pro C ++ se čtyřmi myšlenkami: generické programování , abstraktnost bez ztráty účinnosti, výpočetní model Von Neumann a sémantika hodnot .

Dějiny

Hlavní článek: Historie knihovny standardních šablon

V listopadu 1993 Alexander Stepanov představil knihovnu založenou na generickém programování výboru ANSI/ISO pro standardizaci C ++. Reakce výboru byla v drtivé většině příznivá a vedla k žádosti Andrewa Koeniga o formální návrh včas na zasedání v březnu 1994. Výbor měl několik žádostí o změny a prodloužení a členové výboru se setkali se Stepanovem a Meng Lee, aby jim pomohli vyřešit detaily. Požadavky na nejvýznamnější rozšíření ( asociativní kontejnery ) musely být prokázány jako konzistentní jejich úplnou implementací, úkolem, který Stepanov delegoval na Davida Mussera . Návrh obdržel konečné schválení na schůzi výboru ANSI/ISO v červenci 1994. Dokument Stepanov a Lee 17 byl následně začleněn do návrhové normy ANSI/ISO C ++ (1, části doložek 17 až 27).

Vyhlídky na včasné rozsáhlé šíření STL byly podstatně zlepšeny rozhodnutím společnosti Hewlett-Packard, aby byla jeho implementace volně dostupná na internetu v srpnu 1994. Tato implementace, vyvinutá Stepanovem, Lee a Musserem během procesu normalizace, se stala základem mnoho implementací, které dnes nabízejí dodavatelé překladačů a knihoven.

Složení

Kontejnery

STL obsahuje sekvenční kontejnery a asociativní kontejnery. Kontejnery jsou objekty, které ukládají data. Standardní sekvenční kontejnery zahrnují , a . Standardní asociativní kontejnery jsou , , , , , , a . Existují také kontejnerové adaptéry a , a , které jsou kontejnery se specifickým rozhraním, používají jako implementaci jiné kontejnery. vectordequelistsetmultisetmapmultimaphash_sethash_maphash_multisethash_multimap queuepriority_queuestack

Kontejner Popis
Jednoduché kontejnery
pár Párový kontejner je jednoduchý asociativní kontejner skládající se ze 2 -tice datových prvků nebo objektů, nazývaných „první“ a „druhý“ v daném pevném pořadí. 'Pár' STL lze přiřadit, zkopírovat a porovnat. Pole objektů přidělených na mapě nebo hash_map (popsáno níže) má ve výchozím nastavení typ 'pair', kde všechny 'první' prvky fungují jako jedinečné klíče, každý spojený s jejich 'druhým' hodnotovým objektem.
Sekvence (pole/ propojené seznamy ): seřazené kolekce
vektor dynamické pole , jako je C pole (tj schopné náhodný přístup ), s možností, aby se automaticky měnit velikost sám při vkládání nebo mazání objektu. Vložení prvku na konec vektoru na konci trvá amortizovaný konstantní čas . Odebrání posledního prvku trvá pouze konstantní čas, protože nedojde k žádné změně velikosti. Vkládání a mazání na začátku nebo uprostřed je lineární v čase.

Existuje specializace pro typ bool , která optimalizuje prostor ukládáním hodnot bool jako bitů.

seznam dvojnásobně provázaný seznam ; prvky nejsou uloženy v souvislé paměti. Opačný výkon z vektoru. Pomalé vyhledávání a přístup (lineární čas), ale jakmile byla nalezena pozice, rychlé vložení a vymazání (konstantní čas).
slist
 jednotlivě spojené seznamu ; prvky nejsou uloženy v souvislé paměti. Opačný výkon z vektoru. Pomalé vyhledávání a přístup (lineární čas), ale jakmile byla nalezena pozice, rychlé vložení a vymazání (konstantní čas). Má o něco efektivnější vkládání a mazání a využívá méně paměti než dvakrát propojený seznam, ale lze jej pouze iterovat dopředu. Je implementován ve standardní knihovně C ++ jako . forward_list
deque ( dvojitá fronta ) vektor s vložením/vymazáním na začátku nebo konci v amortizované konstantní době , ale postrádající určité záruky platnosti iterátoru po změně deque.
Adaptéry kontejnerů
fronta Poskytuje rozhraní fronty FIFO z hlediska / / / operací. pushpopfrontback

Jakákoliv sekvence podpůrné operace , , , a mohou být použity k vytvoření instance fronty (například a ). front()back()push_back()pop_front()listdeque
prioritní fronta Poskytuje prioritní rozhraní front z hlediska operací (prvek s nejvyšší prioritou je nahoře). push/pop/top

Jakákoli sekvence náhodného přístupu podporující operace , a může být použita k vytvoření instance priority_queue (např. A ). Je implementován pomocí

haldy . front()push_back()pop_back()vectordeque

Prvky by navíc měly podporovat srovnání (aby bylo možné určit, který prvek má vyšší prioritu a měl by být vyskočen jako první).

zásobník Poskytuje rozhraní zásobníku LIFO, pokud jde o operace (poslední vložený prvek je nahoře). push/pop/top

Libovolné sekvence podporující operace , a lze použít k vytvoření instance zásobníku (např . , A ). back()push_back()pop_back()vectorlistdeque
Asociativní kontejnery : neuspořádané kolekce
soubor matematická množina ; vkládání/mazání prvků v sadě neznehodnotí iterátory ukazující v sadě. Poskytuje sjednocení operací sady , průnik , rozdíl , symetrický rozdíl a test zahrnutí. Typ dat musí implementovat operátor porovnání nebo musí být zadána funkce vlastního komparátoru; takový srovnávací operátor nebo porovnávací funkce musí zaručovat přísné slabé řazení , jinak není chování definováno. Obvykle se implementuje pomocí binárního vyhledávacího stromu s vlastním vyvažováním . <
více sad stejné jako sada, ale umožňuje duplicitní prvky (matematické vícenásobné ).
mapa asociativní pole ; umožňuje mapování z jedné datové položky (klíče) na jinou (hodnotu). Typ klíče musí implementovat operátor porovnání nebo musí být zadána funkce vlastního komparátoru; takový srovnávací operátor nebo porovnávací funkce musí zaručovat přísné slabé řazení , jinak není chování definováno. Obvykle je implementováno pomocí binárního vyhledávacího stromu s vlastním vyvažováním. <
multimapa stejné jako mapa, ale umožňuje duplicitní klíče.
hash_set
hash_multiset
hash_map
hash_multimap 		podobná sadě, více sadám, mapám nebo multimapám, ale implementována pomocí hashovací tabulky ; klíče nejsou uspořádány, ale pro typ klíče musí existovat hashovací funkce . Tyto typy byly vynechány ze standardu C ++; podobné kontejnery byly standardizovány v C ++ 11 , ale s různými názvy ( a ). unordered_setunordered_map
Jiné typy kontejnerů
bitset ukládá řadu bitů podobných vektoru boolov pevné velikosti. Implementuje bitové operace a postrádá iterátory. Žádná sekvence. Poskytuje náhodný přístup.
valarray Jiný datový typ pole, určený pro numerické použití (zejména pro reprezentaci vektorů a matic ); standard C ++ umožňuje specifické optimalizace pro tento zamýšlený účel. Podle Josuttise byl valarray špatně navržen lidmi, „kteří opustili výbor [standard C ++] dlouho před dokončením standardu“, a upřednostňovány jsou knihovny šablon výrazů . Navrhované přepsání valarrayové části standardu v tomto duchu bylo zamítnuto, místo toho se stalo povolení k jeho implementaci pomocí šablony výrazu.

Iterátory

STL implementuje pět různých typů iterátorů . Jedná se o vstupní iterátory (které lze použít pouze ke čtení posloupnosti hodnot), výstupní iterátory (které lze použít pouze k zápisu posloupnosti hodnot), dopředné iterátory (které lze číst, zapisovat a posouvat vpřed), obousměrné iterátory (které jsou jako dopředné iterátory, ale mohou se také pohybovat dozadu) a náhodný přístup iterátor s(který se může volně pohybovat libovolný počet kroků v jedné operaci).

Základní koncept STL je rozsah, který je dvojicí iterátorů, které označují začátek a konec výpočtu, a většina algoritmických šablon knihovny, které fungují na datových strukturách, má rozhraní, která používají rozsahy.

Je možné, aby obousměrné iterátory fungovaly jako iterátory s náhodným přístupem, takže posun vpřed o deset kroků by bylo možné provést pouhým pohybem vpřed o krok v době celkem desetkrát. Zřetelné iterátory s náhodným přístupem však nabízejí výhody účinnosti. Například vektor by měl iterátor náhodného přístupu, ale seznam by měl pouze obousměrný iterátor.

Iterátory jsou hlavní funkcí, která umožňuje obecnost STL. Algoritmus pro obrácení sekvence lze například implementovat pomocí obousměrných iterátorů a poté stejnou implementaci lze použít pro seznamy, vektory a deques . Uživatelsky vytvořené kontejnery musí poskytovat pouze iterátor, který implementuje jedno z pěti standardních rozhraní iterátoru, a všechny algoritmy uvedené v STL lze použít na kontejner.

Tato obecnost má také někdy svou cenu. Například provádění vyhledávání na asociativním kontejneru , jako je mapa nebo sada, může být pomocí iterátorů mnohem pomalejší než voláním členských funkcí nabízených samotným kontejnerem. Důvodem je, že metody asociativního kontejneru mohou využívat výhodu znalosti vnitřní struktury, která je pro algoritmy využívající iterátory neprůhledná.

Algoritmy

V STL je k dispozici velké množství algoritmů pro provádění aktivit, jako je vyhledávání a třídění, každý implementovaný tak, aby vyžadoval určitou úroveň iterátoru (a proto bude fungovat na jakémkoli kontejneru, který poskytuje rozhraní iterátorů). Vyhledávací algoritmy jako a používají binární vyhledávání a podobné třídicí algoritmy vyžadují, aby typ dat musel implementovat operátor porovnání nebo aby byla zadána funkce vlastního komparátoru; takový srovnávací operátor nebo porovnávací funkce musí zaručovat přísné slabé řazení . Kromě toho jsou k dispozici algoritmy pro vytváření haldy z řady prvků, generování lexikograficky seřazených permutací řady prvků, sloučení seřazených rozsahů a provedení spojení , průniku , rozdílu seřazených rozsahů. binary_searchlower_bound<

Funkce

STL obsahuje třídy, které přetěžují volání funkce operator ( ). Instance takových tříd se nazývají funktory nebo funkční objekty . Funktory umožňují parametrizovat chování přidružené funkce (např. Prostřednictvím argumentů předaných konstruktoru funktoru ) a lze je použít k zachování informací o stavu přidruženého per-funktoru společně s funkcí. Jelikož lze funktory i ukazatele funkcí vyvolat pomocí syntaxe volání funkce, jsou zaměnitelné jako argumenty pro šablony, když se odpovídající parametr zobrazí pouze v kontextech volání funkcí. operator()

Zvláště běžným typem funktoru je predikát . Algoritmy například berou unární predikát, který funguje na prvcích sekvence. Algoritmy jako sort, partial_sort, nth_element a všechny tříděné kontejnery používají binární predikát, který musí poskytovat přísné slabé uspořádání , to znamená, že se musí chovat jako test členství v tranzitivním, nereflexivním a asymetrickém binárním vztahu . Pokud není zadán žádný, tyto algoritmy a kontejnery používají ve výchozím nastavení méně , což zase volá méně než operátor <. find_if

Kritika

Kvalita implementace kompilátorů C ++

Kvalita implementace (QoI) kompilátoru C ++ má velký dopad na použitelnost STL (a šablonového kódu obecně):

  • Chybové zprávy zahrnující šablony bývají velmi dlouhé a obtížně dešifrovatelné. Tento problém byl považován za natolik závažný, že byla napsána řada nástrojů, které zjednodušují a vytisknou chybové zprávy související s STL, aby byly srozumitelnější.
  • Neopatrné používání šablon může vést k nadýmání kódu . Tomu bylo zabráněno speciálními technikami v rámci implementace STL (např. Interním použitím prázdných* kontejnerů a jinými technikami „dietních šablon“) a zdokonalením technik optimalizace překladačů. Tento příznak je však podobný naivnímu ručnímu kopírování sady funkcí pro práci s jiným typem, protože oběma se lze vyhnout opatrně a dobrou technikou.
  • Instance šablony může zvýšit dobu kompilace a využití paměti výměnou za typické omezení rozhodování za běhu (např. Prostřednictvím virtuálních funkcí). Dokud se technologie kompilátoru dostatečně nezlepší, lze tento problém odstranit jen částečně pečlivým kódováním, vyhýbáním se určitým idiomatům a prostým nepoužíváním šablon tam, kde nejsou vhodné nebo kde je upřednostňován výkon při kompilaci.

Jiné problémy

  • Inicializace kontejnerů STL s konstantami ve zdrojovém kódu není tak snadná jako datové struktury zděděné z C (adresováno v C ++ 11 pomocí seznamů inicializátorů ).
  • Kontejnery STL nejsou určeny k použití jako základní třídy (jejich destruktory jsou záměrně nevirtuální); odvozování z kontejneru je častou chybou.
  • Koncept iterátorů jak je provádí STK může být obtížné pochopit na první pohled: například když poukázal hodnota, na kterou se iterační odstraněn, iterační sám je pak již není platný. Toto je běžný zdroj chyb. Většina implementací STL poskytuje režim ladění, který je pomalejší, ale může vyhledat takové chyby, pokud jsou použity. Podobný problém existuje v jiných jazycích, například v Javě . Rozsahy byly navrženy jako bezpečnější a flexibilnější alternativa k iterátorům.
  • Určité vzory iterací se nemapují na model iterátoru STL. Například API pro výčet zpětných volání nelze vytvořit tak, aby odpovídala modelu STL, bez použití korutin , které jsou závislé na platformě nebo nejsou k dispozici, a budou mimo standard C ++ do C ++ 20.
  • Soulad kompilátoru nezaručuje, že objekty Allocator používané pro správu paměti pro kontejnery budou fungovat s chováním závislým na stavu. Přenosná knihovna například nemůže definovat typ alokátoru, který bude stahovat paměť z různých fondů pomocí různých objektů alokátorů tohoto typu. (Meyers, str. 50) (řešeno v C ++ 11 ).
  • Sada algoritmů není úplná: například algoritmus byl vynechán, přestože byl přidán v C ++ 11 .copy_if

Implementace

Viz také

Poznámky

Reference

externí odkazy