Стандардна библиотека шаблона

Стандардна библиотека шаблона (енг. Standard Template Library (STL)) је софтверска библиотека програмског језика C++ која је делимично укључена у С++ стандардну библиотеку. Обезбеђује четири компоненте: контејнере, итераторе, алгоритме и функторе.

STL обезбеђује готов скуп основних класа за C++, као што су контејнери и асоцијативни низови, који се може користити уз било који уграђени тип и уз било који кориснички дефинисан тип који подржава неке основне операције (као што су копирање и додела). STL алгоритми су независни од контејнера, што значајно смањује комплексност библиотеке.

STL остварује резултате кроз употребу шаблона. Овај приступ обезбеђује полиморфизам времена компајлирања који је често ефикаснији од традиционалног полиморфизма времена покретања. Модерни C++ преводиоци подешени су тако да минимализују било какву казну апстракције насталу интензивном употребом STL-а.

STL је настао као прва библиотека генеричких алгоритама и структура података за C++, са четири идеје на уму: генеричко програмирање, апстракција без губитка ефикасности, фон Нојманова архитектура и вредносна семантика.

Композиција

Контејнери

STL садржи секвенцијалне контејнере и асоцијативне контејнере. Стандардни секвенцијални контејнери су: низ, ред са два краја, и листа. Стандардни асоцијативни контејнери су: скуп, мултискуп, мапа (асоцијативни низ) и мултимапа. Постоје такође и адаптери контејнера: ред, ред са приоритетом и стек, што су контејнери са специфичним интерфејсом, који користе друге контејнере као имплементацију.

Контејнер	Опис
	Једноставни контејнери
пар (pair)	Пар контејнер је једноставни асоцијативни контејнер који се састоји од уређеног пара елемената, са именима 'први' и 'други', тим редоследом. STL пар се може доделити, копирати и поредити.
	Секвенце (низови/повезане листе): уређене колекције
низ (vector)	динамички низ, као С низ (могућност случајног приступа), са способношћу аутоматске промене величине при убацивању или брисању објекта. Убацивању/брисању елемента на крај/са краја низа потребно је константно време. Убацивање/брисање на почетак/са почетка (у средину/из средине) захтева линеарно време.
листа (list)	двоструко повезана листа; супротан перформанс од низа. Спора претрага и приступ (линеарно време), али кад се пронађе позиција, брзо убацивање и брисање (константно време).
ред са два краја (deque)	низ са убацивањем/брисањем на почетак или крај/са почетка или краја у константном времену.
	Асоцијативни контејнери: неуређене колекције
скуп (set)	математички скуп; убацивање/брисање елемената чува итераторе. Обезбеђене су скуповне операције унија, пресек, разлика, симетрична разлика и тест инклузије.
мултискуп (multiset)	исто као скуп, с тим што дозвољава дупликате елемената (математички мултискуп)
мапа (map)	асоцијативни низ; обично се имплементира коришћењем самобалансирајућег бинарног стабла претраге
мултимапа (multimap)	исто као мапа, с тим што дозвољава дупликате кључева

Итератори

STL имплементира пет различитих типова итератора. То су улазни итератори (који могу да се користе само за читање низа вредности), излазни итератори (који могу да се користе само за испис низа вредности), forward итератори (који се могу читати, у које се може писати и који се могу померати напред), двосмерни итератори (који су као forward итератори, само што се могу такође померати назад) и итератори са случајним приступом (који се слободно могу померати неодређени број корака у једној операцији).

Могуће је да се двосмерни итератори понашају као итератори са случајним приступом, тако што, на пример, померање напред за десет корака може бити остварено померањем напред десет пута за по један корак. Ипак, коришћење различитих итератора са случајним приступом нам нуди предности што се тиче ефикасности. На пример, низ може да има итератор са случајним приступом, али листа само двосмерни итератор.

Итератори представљају главну карактеристику која омогућава општу примену STL-а. На пример, алгоритам који обрће низ може се имплементирати коришћењем двосмерних итератора, и онда се иста имплементација може применити на листе и редове са два краја. Контејнери направљени од стране корисника би требало једино да обезбеде итератор који имплементира један од пет стандардних итераторских интерфејса, и сви алгоритми обезбеђени STL-ом могу се применити на контејнер.

Ипак, општост понекад има и своју цену. На пример, извршавање претраге на асоцијативном контејнеру као што је мапа или скуп може бити доста спорије коришћењем итератора него позивањем чланова функција понуђених од самог контејнера. Ово се дешава зато што методе асоцијативног контејнера могу имати предност у познавању унутрашње структуре, што је непознато алгоритмима који користе итераторе.

Алгоритми

Велики број алгоритама за извршавање операција као што су претрага и сортирање обезбеђени су у STL-у, сваки имплементиран тако да захтева одређени ниво итератора (и зато ће радити на било ком контејнеру који обезбеђује везу ка итераторима).

Функтори

STL садржи класе које оптерећују функцију оператор (operator()). Инстанце таквих класа зову се функтори или функцијски објекти. Функтори дозвољавају параметризацију понашања функције (на пример кроз аргументе прослеђене функторском конструктору).

Историјат

Архитектура STL-а је већински креација Александра Степанова. 1979. године он је почео да разрађује своје почетне идеје генеричког програмирања и да истражује њихов потенцијал за развој софтвера. Иако је Дејвид Масер развио и бранио неке аспекте генеричког програмирања још 1971. године, оно је било ограничено на специјализованију област развоја софтвера (рачунска алгебра).

Степанов је препознао пун потенцијал генеричког програмирања и убедио тадашње колеге из General Electric Research and Development-a (укључујући, првобитно, Дејвида Масера и Дипака Капура) да би генеричко програмирање требало да буде вођено као основа развоја софтвера. У оно време није постојала реална подршка за генеричко програмирање ни на једном програмском језику.

Први већи језик који обезбеђује такву подршку био је Ada, са својим генеричким јединицама. 1985. године, програмски језик Eiffel постао је први објектно-оријентисан који укључује битну подршку за генеричке класе, комбиновану са идејом наслеђивања из објектно-оријентисаног програмирања. До 1987. Степанов и Масер су развили и објавили Ada библиотеку за процесирање листа која је садржала резултате већине њихових истраживања на тему генеричког програмирања. Међутим, Ada није достигла одобравање ван одбрамбене индустрије и C++ је био прикладнији за ширу употребу и обезбеђивање подршке за генеричко програмирање, иако је као језик био релативно нов. Други разлог за окретање С++-у, који је Степанов одмах препознао, био је С/С++ модел рачунања који дозвољава веома флексибилан приступ коришћења показивача, који је кључан за постизање општости без губитка ефикасности.

Било је потребно више истраживања и експериментисања, не само за развијање индивидуалних компоненти, већ и за развијање целокупне архитектуре саставне библиотеке засноване на генеричком програмирању. Прво у AT&T Беловим лабораторијама, касније и у Hewlett-Packard Research лабораторијама, Степанов је експериментисао са мноштвом архитектонских и алгоритамских формулација, прво у С-у, касније и у С++-у. Масер је сарађивао у овом истраживању и 1992. године Менг Ли се придружио Степановом пројекту у HP и постао главни сарадник.

Овај рад би се несумњиво наставио на неко време као истраживачки пројекат или би, у најбољем случају, завршио у HP власничкој библиотеци, да Ендру Кениг из Белових лабораторија није постао свестан тог рада и питао Степанова да презентује главне идеје на састанку ANSI/ISO одбора за С++ стандардизацију, у новембру 1993. Одговор одбора био је веома повољан.

Одбор је имао неколико захтева за промене и екстензије, и мала група његових чланова срела се са Степановим и Лијем ради пружања помоћи око разраде детаља. Захтеви за најзначајнију екстензију (асоцијативни контејнери) морали су да се покажу конзистентним, што је урађено њиховом потпуном имплементацијом, посао који је Степанов предао Масеру. Степанов и Ли произвели су предлог који је коначно одобрен на састанку ANSI/ISO одбора у јулу 1994.

Референце

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.