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

Стандардната библиотека на предлошки (англиски: Standard Template Library (STL)) е програмска библиотека која е делумно вклучена во C++ стандардната библиотека. Содржи контејнери, итератори, алгоритми и функции. Поконкретно, C++ стандардната библиотека е заснована на STL издадено од SGI. Во двете библиотеки има содржини што ги нема во другата. SGI-овата STL библиотека е строго дефинирна како множество од хедери (headers), додека ISO C++ не специфицира хедер (header) содржина и овозможува имплементација или во хедерите или во вистинската библиотека.

Краток преглед

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

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

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

Содржина

Containers

STL содржи секвенцијални containers и асоцијативни containers. Стандардните секвенцијални containers се: вектор, deque и листа. Стандардните асоцијативни containers се: set, multiset, map и multimap.

Container	Опис
	Секвенци (Низи/Поврзани листи) – подредена колекција
вектор (vеctor)	динамичка низа, како C низа (способна за случаен пристап) со можност самата да ja промени големината при внесување или бришење на објект. Внесувањето и отстранувањето на елемент во/од векторот се извршува за константна временска величина. Внесувањето или бришењето на почетокот или на средината е линеарно со времето. Постои специјализација за bool типот на податоци која го оптимизира просторот со сместувањето на bool променливите како битови.
листа (list)	двојно поврзана низа, елементите не се складирани во допирна меморија. Спротивни особини од векторот. Бавен преглед и пристап (во линеарно време), но штом е пронајдена позиција, брзо внесување и бришење (константно време).
deque (double ended queue)	вектор со внесување/бришење на почетокот или на крајот во константно време, но нема гаранција за валидноста на итераторот по менувањето на deque.

Асоцијативни containers – неподредени збирови
set	Подреден set; внесувачки/бришачки елементи во set не ги поништуваат итераторите кои покажуваат во set-от.
multiset	Исто како и set-от
map	Подредена асоцијативна низа; овозможува maping од една податочна единица (копче) до друга (вредност). Типот на копчето мора да го имплементира операторот за споредување < или мора да биде специфицирана посебна функција за компараторот. Имплементираниот користи само-балансирачка дрво-структура за пребарување.
multimap	Исто како и map, само што овозможува и копчиња за копирање.
hash_set hash_multiset hash_map hash_multimap	Исто како и set, multiset, map, или multimap, секој посебно, но применето користи и hash table, копчињата не се подредени, но hash функцијата мора да постои за key типот. Овие containers не се дел од стандардната библиотека на C++, но се вклучени во SGI’s STL порширувањата и се вклучени во заедничките библиотеки како што се GNU C++ библиотеката во __gnu_cxx namespace. Овие се предвидени да се додадат во C++ стандардот како дел од TR1, со малку изменети имиња како: unordered_set, unordered_multiset, unordered_map and unordered_multimap.

Други типови на containers
bitset	Складира серии од битови слично со векторите со фиксни големини од логички тип на податоци. Имплементира bitwise операции и има недостаток на итератори. Не секвенца.
valarray	Слично како C-низа како вектор, но е дизајнирана за броење со голема брзина по цена на програмска удобност и за примена во главна цел.

Итератори

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

Можно е двонасочните итератори да се однесуваат како итератори со случаен пристап, на пример придвижување за 10 чекори нанапред може да се изведе со единечен чекор вкупно десет пати. Сепак, користењето на разбирлив итератор со случаен пристап нуди поефикасни предности. На пример, вектор би имал итератор со случаен пристап, но листата само двонасочен итератор.

Итераторите се major feature кои овозможуваат целосна примена на STL. На пример, алгоритам за извртување на низа може да биде имплементиран со користење на двонасочни итератори, а потоа истата имплементација може да се користи на листи, Вектори и deques. User-created containers мора да овозможи итератор кој е содржи еден од петте стандардни итераторски можности и сите алгоритми утврдени во STL можат да бидат искористени во container.

Сепак се ова има своја цена. На пример, пребарувањето во асоцијативен container како на пример map или set може да биде многу побавно користејќи итератори отколку со повикување на членовите на функциите понудени од самиот container. Ова се случува поради тоа што методите на асоцијативните container имаат предност во познавањето на внатрешната структура , којашто е непозната за алгоритмите што користат итератори.

Алгоритми

Голем број на алгоритми кои служат за операции како што се пребварување и подредување се предвидени во STL, секој кога е имплементиран има потреба од одредено ниво на итератор (и затоа ќе работи на било кој container кој обезбедува поврзување на итератори).

Функтори

STL вклучува класи кои го оптоваруваат функцискиот оператор ( operator() ). Класите кои го прават ова се викаат функтори или функциски објекти. Тие се корисни за задржување и враќање на состојбата на информациите во функциите кои се преминати во други функции. Обичните покажувачи во функции исто така можат да се користат како функтори.

Историјат

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

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

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

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

Оваа работа несомнено ќе продолжеше некое време како истражување или во најдобар случај ќе беше патентирана како HP библиотека ако Ендрју Кониг од Bell Labs не стана свесен за работата и го замоли Степанов да ги презентира главните идеи на собирот на ANSI/ISO комисијата во ноември 1993 година за стандардизација на C++. Одговорот на комисијата беше убедливо наклонет и дојде до барање од Кониг за формално предложување за време на состанокот во март 1994 година. И покрај огромниот временски притисок, Алекс и Менг успеаја да достават предлог план кој доби прелименарна дозвола на состанокот.

Комитетот имаше неколку предлози за промени и проширувања (некои од нив со големо значење) и мала група од комитетот се состана со Степанов и Ли за да им помогнат во завршните детали. За најголемото проширување (асоцијативни containers) мораше да биде покажано дека е доследно целосно да биде применето, задача која Степанов му ја испратил на Масер. Овој проект меожеше многу лесно да излезе од контрола во оваа точка, но Степанов и Ли повторно застанаја пред предизвикот и изготвија предлог кој доби завршно одобрување во јули 1994 година на состанокот на ANSI/ISO. Подоцна документот 17 од Степанов и Ли беше вклѕчен во ANSI/ISO C++ планот за стандардизација (1, дел од клаузулите од 17 до 27). Исто така имаше влијание врз други делови од C++ стандардната библиотека да бидат променети согласно со тоа, како што се стринговите и некои претходно присвоени стандарди од тие области.

Наспроти успехот на STL пред комисијата, остана отворено прашањето како STL ќе стане достапна и искористена. Со побарувачкиот дел од планот за стандардизација на STL кој бил јавно достапен, дилерите на компајлери и дилерите на независни софтверски библиотеки можеа да развијат нивна сопствена примена и да ги пласираат на пазарот како одвоени производи или како предности за нивните производи. Еден од авторите на првото издание, Атул Саини, беше еден од првите кои го сфатија комерцијалниот потенцијал и започна да го истражува како линија од бизнисот во неговата компанија Modena Software Incorporated, дури и пред STL да биде целосно прифатена од комисијата.

Изгледите за широко распространување на STL беа значително подобрени со одлуката на Хјулид-Пакард да ја направи нивната реализација слободно достапна на интернет во август 1994. Оваа реализација, развиена од Степанов, Ли и Масер за време на процесот на стандардизација, стана база за многу примени понудени од дилерите на компајлери и библиотеки во денешно време.