Standardna biblioteka šablona

Standardna biblioteka šablona (eng. Standard Template Library (STL)) je softverska biblioteka programskog jezika C++ koja je delimično uključena u S++ standardnu biblioteku. Obezbeđuje četiri komponente: kontejnere, iteratore, algoritme i funktore.

STL obezbeđuje gotov skup osnovnih klasa za C++, kao što su kontejneri i asocijativni nizovi, koji se može koristiti uz bilo koji ugrađeni tip i uz bilo koji korisnički definisan tip koji podržava neke osnovne operacije (kao što su kopiranje i dodela). STL algoritmi su nezavisni od kontejnera, što značajno smanjuje kompleksnost biblioteke.

STL ostvaruje rezultate kroz upotrebu šablona. Ovaj pristup obezbeđuje polimorfizam vremena kompajliranja koji je često efikasniji od tradicionalnog polimorfizma vremena pokretanja. Moderni C++ prevodioci podešeni su tako da minimalizuju bilo kakvu kaznu apstrakcije nastalu intenzivnom upotrebom STL-a.

STL je nastao kao prva biblioteka generičkih algoritama i struktura podataka za C++, sa četiri ideje na umu: generičko programiranje, apstrakcija bez gubitka efikasnosti, fon Nojmanova arhitektura i vrednosna semantika.

Kompozicija

Kontejneri

STL sadrži sekvencijalne kontejnere i asocijativne kontejnere. Standardni sekvencijalni kontejneri su: niz, red sa dva kraja, i lista. Standardni asocijativni kontejneri su: skup, multiskup, mapa (asocijativni niz) i multimapa. Postoje takođe i adapteri kontejnera: red, red sa prioritetom i stek, što su kontejneri sa specifičnim interfejsom, koji koriste druge kontejnere kao implementaciju.

Kontejner	Opis
	Jednostavni kontejneri
par (pair)	Par kontejner je jednostavni asocijativni kontejner koji se sastoji od uređenog para elemenata, sa imenima 'prvi' i 'drugi', tim redosledom. STL par se može dodeliti, kopirati i porediti.
	Sekvence (nizovi/povezane liste): uređene kolekcije
niz (vector)	dinamički niz, kao S niz (mogućnost slučajnog pristupa), sa sposobnošću automatske promene veličine pri ubacivanju ili brisanju objekta. Ubacivanju/brisanju elementa na kraj/sa kraja niza potrebno je konstantno vreme. Ubacivanje/brisanje na početak/sa početka (u sredinu/iz sredine) zahteva linearno vreme.
lista (list)	dvostruko povezana lista; suprotan performans od niza. Spora pretraga i pristup (linearno vreme), ali kad se pronađe pozicija, brzo ubacivanje i brisanje (konstantno vreme).
red sa dva kraja (deque)	niz sa ubacivanjem/brisanjem na početak ili kraj/sa početka ili kraja u konstantnom vremenu.
	Asocijativni kontejneri: neuređene kolekcije
skup (set)	matematički skup; ubacivanje/brisanje elemenata čuva iteratore. Obezbeđene su skupovne operacije unija, presek, razlika, simetrična razlika i test inkluzije.
multiskup (multiset)	isto kao skup, s tim što dozvoljava duplikate elemenata (matematički multiskup)
mapa (map)	asocijativni niz; obično se implementira korišćenjem samobalansirajućeg binarnog stabla pretrage
multimapa (multimap)	isto kao mapa, s tim što dozvoljava duplikate ključeva

Iteratori

STL implementira pet različitih tipova iteratora. To su ulazni iteratori (koji mogu da se koriste samo za čitanje niza vrednosti), izlazni iteratori (koji mogu da se koriste samo za ispis niza vrednosti), forward iteratori (koji se mogu čitati, u koje se može pisati i koji se mogu pomerati napred), dvosmerni iteratori (koji su kao forward iteratori, samo što se mogu takođe pomerati nazad) i iteratori sa slučajnim pristupom (koji se slobodno mogu pomerati neodređeni broj koraka u jednoj operaciji).

Moguće je da se dvosmerni iteratori ponašaju kao iteratori sa slučajnim pristupom, tako što, na primer, pomeranje napred za deset koraka može biti ostvareno pomeranjem napred deset puta za po jedan korak. Ipak, korišćenje različitih iteratora sa slučajnim pristupom nam nudi prednosti što se tiče efikasnosti. Na primer, niz može da ima iterator sa slučajnim pristupom, ali lista samo dvosmerni iterator.

Iteratori predstavljaju glavnu karakteristiku koja omogućava opštu primenu STL-a. Na primer, algoritam koji obrće niz može se implementirati korišćenjem dvosmernih iteratora, i onda se ista implementacija može primeniti na liste i redove sa dva kraja. Kontejneri napravljeni od strane korisnika bi trebalo jedino da obezbede iterator koji implementira jedan od pet standardnih iteratorskih interfejsa, i svi algoritmi obezbeđeni STL-om mogu se primeniti na kontejner.

Ipak, opštost ponekad ima i svoju cenu. Na primer, izvršavanje pretrage na asocijativnom kontejneru kao što je mapa ili skup može biti dosta sporije korišćenjem iteratora nego pozivanjem članova funkcija ponuđenih od samog kontejnera. Ovo se dešava zato što metode asocijativnog kontejnera mogu imati prednost u poznavanju unutrašnje strukture, što je nepoznato algoritmima koji koriste iteratore.

Algoritmi

Veliki broj algoritama za izvršavanje operacija kao što su pretraga i sortiranje obezbeđeni su u STL-u, svaki implementiran tako da zahteva određeni nivo iteratora (i zato će raditi na bilo kom kontejneru koji obezbeđuje vezu ka iteratorima).

Funktori

STL sadrži klase koje opterećuju funkciju operator (operator()). Instance takvih klasa zovu se funktori ili funkcijski objekti. Funktori dozvoljavaju parametrizaciju ponašanja funkcije (na primer kroz argumente prosleđene funktorskom konstruktoru).

Istorijat

Arhitektura STL-a je većinski kreacija Aleksandra Stepanova. 1979. godine on je počeo da razrađuje svoje početne ideje generičkog programiranja i da istražuje njihov potencijal za razvoj softvera. Iako je Dejvid Maser razvio i branio neke aspekte generičkog programiranja još 1971. godine, ono je bilo ograničeno na specijalizovaniju oblast razvoja softvera (računska algebra).

Stepanov je prepoznao pun potencijal generičkog programiranja i ubedio tadašnje kolege iz General Electric Research and Development-a (uključujući, prvobitno, Dejvida Masera i Dipaka Kapura) da bi generičko programiranje trebalo da bude vođeno kao osnova razvoja softvera. U ono vreme nije postojala realna podrška za generičko programiranje ni na jednom programskom jeziku.

Prvi veći jezik koji obezbeđuje takvu podršku bio je Ada, sa svojim generičkim jedinicama. 1985. godine, programski jezik Eiffel postao je prvi objektno-orijentisan koji uključuje bitnu podršku za generičke klase, kombinovanu sa idejom nasleđivanja iz objektno-orijentisanog programiranja. Do 1987. Stepanov i Maser su razvili i objavili Ada biblioteku za procesiranje lista koja je sadržala rezultate većine njihovih istraživanja na temu generičkog programiranja. Međutim, Ada nije dostigla odobravanje van odbrambene industrije i C++ je bio prikladniji za širu upotrebu i obezbeđivanje podrške za generičko programiranje, iako je kao jezik bio relativno nov. Drugi razlog za okretanje S++-u, koji je Stepanov odmah prepoznao, bio je S/S++ model računanja koji dozvoljava veoma fleksibilan pristup korišćenja pokazivača, koji je ključan za postizanje opštosti bez gubitka efikasnosti.

Bilo je potrebno više istraživanja i eksperimentisanja, ne samo za razvijanje individualnih komponenti, već i za razvijanje celokupne arhitekture sastavne biblioteke zasnovane na generičkom programiranju. Prvo u AT&T Belovim laboratorijama, kasnije i u Hewlett-Packard Research laboratorijama, Stepanov je eksperimentisao sa mnoštvom arhitektonskih i algoritamskih formulacija, prvo u S-u, kasnije i u S++-u. Maser je sarađivao u ovom istraživanju i 1992. godine Meng Li se pridružio Stepanovom projektu u HP i postao glavni saradnik.

Ovaj rad bi se nesumnjivo nastavio na neko vreme kao istraživački projekat ili bi, u najboljem slučaju, završio u HP vlasničkoj biblioteci, da Endru Kenig iz Belovih laboratorija nije postao svestan tog rada i pitao Stepanova da prezentuje glavne ideje na sastanku ANSI/ISO odbora za S++ standardizaciju, u novembru 1993. Odgovor odbora bio je veoma povoljan.

Odbor je imao nekoliko zahteva za promene i ekstenzije, i mala grupa njegovih članova srela se sa Stepanovim i Lijem radi pružanja pomoći oko razrade detalja. Zahtevi za najznačajniju ekstenziju (asocijativni kontejneri) morali su da se pokažu konzistentnim, što je urađeno njihovom potpunom implementacijom, posao koji je Stepanov predao Maseru. Stepanov i Li proizveli su predlog koji je konačno odobren na sastanku ANSI/ISO odbora u julu 1994.

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 (2007). Notes on Programming. Stepanov reflects about the design of the STL.
• Nicolai M. Josuttis . The C++ Standard Library: A Tutorial and Reference. Addison-Wesley. 2000. ISBN 978-0-201-37926-6.
• Scott Meyers . Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley. 2001. ISBN 978-0-201-74962-5.
• David Vandevoorde and Nicolai M. Josuttis . C++ Templates: The Complete Guide. Addison-Wesley Professional. 2002. ISBN 978-0-201-73484-3.
• Atul Saini and David R. Musser (1996). STL Tutorial and Reference Guide: C+ + Programming with the Standard Template Library. Foreword. Addison-Wesley. ISBN 978-0-201-63398-6.