Стандартты үлгілердің кітапханасы

Стандартты үлгілердің кітапханасы (STL) (ағылш . Standard Template Library ) - келісілген жалпыланған Алгоритмдер мен контейнерлердің жиынтығы, олардың құрамына кіретін құралдар, және C++ - тың әртүрлі қосалқы функцияларының жиынтығы.

Стандартты үлгілер кітапханасы, C ++ стандарты қосылғанға дейін, бастапқыда — HP фирмасының, содан кейін SGI-ның бөгде әзірлемесі болды. Тіл стандарты "STL" деп атамайды, өйткені бұл кітапхана тілдің ажырамас бөлігіне айналды, алайда көптеген адамдар осы атауды стандартты кітапхананың қалған бөлігінен (енгізу-шығару ағындары (iostream), С бөлімшесі және т.б.) ажырату үшін әлі күнге дейін пайдаланады.

SGI STL — де негізделген STLPort деп аталатын жоба: STL, iostream және жол кластарын үнемі жаңартады. Кейбір басқа жобалар түрлі конструкторлық тапсырмалар үшін стандартты кітапхананың жеке қолдануларын әзірлеумен айналысады. Әрбір c++ компиляторлар өндірушісі міндетті түрде осы кітапхананы жүзеге асырады, өйткені ол стандарттың өте маңызды бөлігі болып табылады және кеңінен қолданылады.

STL архитектурасын Александр Степанов және Менг Ли әзірледі.

Тарихы

1993 жылдың қарашасында Александр Степанов ANSI/ISO комитетіне әмбебап бағдарламалауға негізделген c++ стандарттау бойынша Кітапхананы ұсынды. Комитеттің жауабы көптеген қолайлы болды және Эндрю Кениг 1994 жылдың наурыз айында кеңеске ресми ұсыныс беруді сұрады. Комитетте өзгерістер мен ұзартулар туралы бірнеше өтініш болды және Комитет мүшелері Степановпен және Мэн Лимен кездесті. Ең маңызды кеңейтулерге (ассоциативті контейнерлерге) қойылатын талаптар оларды іске асыру жолымен толық көлемде дәлелденуі тиіс және бұл міндет Степанов Дэвид Мюссерге тапсырды. Бұл ұсыныс 1994 жылдың шілдесінде ANSI/ISO комитетінің отырысында түпкілікті мақұлдау алды. Кейіннен 17 Степанов пен Ли құжаты ANSI/ISO C++ стандартының жобасына (1, 17-27 тармақтардың бөліктері) енгізілді.

STL ерте кең таралуының келешегі 1994 жылдың тамызында Hewlett-Packard компаниясының оны енгізуді Интернетте еркін қол жетімді ету шешімін қабылдауымен айтарлықтай жақсарды. Стандарттау процесінде Степанов, Ли және Мюссер әзірлеген бұл іске асыру бүгінде компиляторлар мен кітапханалардың жеткізушілері ұсынатын көптеген іске асырудың негізі болды.

STL—дің негізгі компоненттері

STL негізінен төменде аталған келесі компоненттерден тұрады:

1) Контейнерлер (ағылш. container)

Контейнер-бұл деректер құрылымының белгілі бір түрінің объектілерінің жиынтығы. STL-да бізде array, vector, queue, deque, list, map, set және т.б. сияқты контейнерлік кластардың әртүрлі түрлері бар.

Контейнерлер табиғатына қарай серпінді және объектілердің әртүрлі түрлерін сақтау үшін пайдаланылуы мүмкін.

2) Алгоритмдер (ағылш. algorithm)

Алгоритмдер-бұл контейнерлерге әсер ететін әдістер немесе Функциялар. STL ұсынатын алгоритмдерді пайдалана отырып, біз контейнерлік класс объектілерінің мазмұнын іздеу, сұрыптау, өзгерту, түрлендіру немесе инициализациялау әдістерін пайдалана аламыз.

STL ұсынатын Алгоритмдер Алгоритмдер алгоритмдерді өзі жазу орнына күрделі деректер құрылымымен тікелей жұмыс істей алатын кірістірілген функциялары бар.

Мысалы, STL-дегі reverse () функциясы байланысқан тізімнің реверсіне пайдаланылуы мүмкін.

3) Итераторлар (ағылш. iterator)

Итераторлар-бұл өте маңызды және ерекше STL. Итераторлар-бұл контейнер объектілері бойынша қозғалу үшін пайдаланылатын конструкциялар. Біз массивтерді қадамдық іріктеу үшін пайдаланатын индекстер сияқты, итераторлар контейнерлік кластағы объектілерге әрекет етеді және деректерді қадамдық іріктеу үшін пайдаланылуы мүмкін.

Контейнерлер

Контейнер	Сипаттамасы
Дәйекті контейнерлер
vector	C-элементті қосу / жою кезінде өлшемнің Автоматты өзгеруімен еркін қатынаудың динамикалық массиві. 1) </math>индексі бойынша қатынау. Қосу-vector соңында элементті жою амортизацияланған $O(1)$ уақыт, Vector — $O(n)$ басында немесе ортасында бірдей операция алады. Стандартты жылдам сұрыптау $O(n\log(n))$ . Элементті таңдау $O(n)$ алады. Vector үлгісінің [[[bool] түрі үшін мамандануы бар, ол бит түрінде элементтерді сақтау есебінен аз жадты талап етеді, бірақ ол итераторлармен жұмыс істеудің барлық мүмкіндіктерін қолдамайды.
list	Элементтер жадтың үздіксіз аймағында сақталатын vector контейнеріне қарағанда, элементтері жадтың еркін кесектерінде сақталатын қос байланыс тізімі. Элементке қол жеткізу уақытының көп болуына байланысты векторға қарағанда аралықты іздеу баяу. $O(n)$ индексі бойынша қатынау. Контейнердің кез — келген жерінде қою және жою өте тез - $O(1)$ үшін.
deque	Екі жақты кезек. Контейнер vector сияқты, бірақ $O(1)$ екі ұшында элементтерді жылдам қою және жою мүмкіндігі бар. Сызықтық массивтердің екі байланысқан тізімі түрінде іске асырылған. Екінші жағынан, [[[vector]] - ке қарағанда, екі жақты кезек барлық элементтердің үздіксіз жады учаскесінде орналасуына кепілдік бермейді, бұл контейнер элементтеріне кіру үшін көрсеткіштер арифметикасын қауіпсіз пайдалануға мүмкіндік бермейді.
Ассоциативті контейнерлер
set	Көптеген бірегей элементтер. Көптеген элементтерді кірістіру/жою кезінде осы жиын элементтерін көрсететін итераторлар жарамсыз болмайды. Біріктіру, қиылысу, азайту типтерінің жиындарына стандартты операцияларды қамтамасыз етеді. Жиын элементтерінің түрін салыстыру операторы `operator<` іске асыруы керек немесе компаратор функциясын ұсыну керек. Екілік іздеудің өзін-өзі теңгеруші ағашының негізінде жүзеге асырылған.
multiset	Set сияқты, бірақ қайталанатын элементтерді сақтауға мүмкіндік береді.
map	Кілттерден тұратын және оларға сәйкес мәндердің жұптарының реттелген ассоциативті массиві. Кілттер бірегей болуы керек. Элементтердің жүру тәртібі кілттермен анықталады. Бұл ретте кілттің түрін салыстыру операторы `operator<` іске асыруы тиіс немесе компаратор функциясын ұсыну қажет.
multimap	Map сияқты, бірақ бірнеше бірдей кілттерді сақтауға мүмкіндік береді.
Адаптер-контейнерлер
stack	Элементтерді қосу және жою бір ұшынан жүзеге асырылатын Стек — контейнер.
queue	Кезек — бір шетінен элементтерді қосуға, ал екіншісінен алуға болатын контейнер.
priority_queue	Ең үлкен элемент әрқашан бірінші орында тұрады, ол кезекте басымдық беріліп ұйымдастырылған.
Псевдоконтейнерлер
bitset	Бит маскаларын сақтау үшін қызмет етеді. `vector<bool>` тіркелген өлшемге ұқсас. Өлшемі bitset объектісі жарияланған кезде белгіленеді. Bitset-те итераторлар жоқ. Жад өлшемі бойынша оңтайландырылған.
basic_string	Жолдарды сақтауға және өңдеуге арналған Контейнер. Элементтерді бір блок қатарынан сақтайды, бұл барлық бірізділікке жылдам қатынауды ұйымдастыруға мүмкіндік береді. Элементтер Ipod ' ami болуы керек. +Көмегімен конкатенация анықталды.
valarray	Үлгі сандық массивтерді сақтауға арналған және жоғары есептеу өнімділігіне жету үшін оңтайландырылған. Кейбір дәрежеде vector ұқсас, бірақ онда контейнерлер үшін стандартты операциялардың көпшілігі жоқ. Екі valarray және valarray және скаляр (элемент) бойынша операциялар анықталды. Бұл операцияларды векторлық процессорларда да, блоктары бар скалярлық процессорларда да тиімді жүзеге асыруға болады SIMD.

Элементтерді сақтауға арналған контейнерлерде объектілерді мәні бойынша беру семантикасы қолданылады. Басқаша айтқанда, контейнер қосылған кезде элемент көшірмесін алады. Егер көшірмені жасау қажет емес болса, элементтерге көрсеткіштер контейнерін пайдаланады. Элементтерді беру оператордың көмегімен жүзеге асырылады, ал оларды жою деструкторды пайдалана отырып жүргізіледі. Кестеде контейнерлердегі элементтерге қойылатын негізгі талаптар келтірілген:

Әдіс	Сипаттамасы	Ескертпе
Көшірме құрастырушысы	Ескі элементке ұқсас жаңа элемент жасайды	Әрбір элементті контейнерге кірістіру кезінде қолданылады
Беру операторы	Элементтің мазмұнын бастапқы элементтің көшірмесімен ауыстырады	Элементтің әрбір модификациясында қолданылады
Деструктор	Элементті бұзады	Элементті әрбір жою кезінде қолданылады
Әдепкі Конструктор	Элементті аргументсіз жасайды	Белгілі бір операциялар үшін ғана қолданылады
operator==	Екі элементті салыстырады	Operator== екі контейнер үшін қолданылады
operator<	Элементтердің қайсысы азырақ екенін анықтайды	Operator < екі контейнер үшін қолданылады

Барлық " толыққанды " стандартты контейнерлер талаптардың (немесе келісімдердің) белгілі бір жиынтығын қанағаттандырады. Төменде келтірілген кестеде Т типті объектілерді қамтитын контейнердің с-сыныбы.

Өрнек	Қайтарылатын түрі	Күрделілігі	Ескертпе
C::value_type	T	Компиляция уақыты
C::reference	T	Компиляция уақыты
C::const_reference		Компиляция уақыты
C::pointer	C көрсететін көрсеткіш түрі:: reference	Компиляция уақыты	Т көрсеткіш
C::iterator	C көрсететін көрсеткіш түрі:: reference	Компиляция уақыты	Шығару итераторынан басқа, кез келген түрдегі Итератор
C::const_iterator	ТC көрсететін көрсеткіш түрі::const_reference	Компиляция уақыты	Шығару итераторынан басқа, кез келген түрдегі Итератор
C::size_type	Таңбасыз бүтін түрі	Компиляция уақыты
C obj;		Тұрақты	obj.size() == 0 — дан кейін
C obj1; obj1 = obj2;		Сызықтық	obj1 == obj2 — дан кейін
C obj; (&obj)->~C();	Нәтиже пайдаланылмайды	Сызықтық	obj.size() == 0 — дан кейін
obj.begin()		Тұрақты
obj.end()		Тұрақты
obj1 == obj2	Bool-ға қайтатын	Сызықтық
obj1 != obj2	Bool-ға қайтатын	Сызықтық
obj.size()	size_type	Типке байланысты	Контейнердің бос екенін тексеру үшін қолдануға болмайды
obj.empty()	Bool-ға қайтатын	Тұрақты
obj1 < obj2	Bool-ға қайтатын	Сызықтық
obj1 > obj2	Bool-ға қайтатын	Сызықтық
obj1 <= obj2	Bool-ға қайтатын	Сызықтық
obj1 >= obj2	Bool-ға қайтатын	Сызықтық
obj.swap(obj2)	void	Тұрақты

Итераторлар

Кітапханада STL қол жеткізу үшін элементтері делдал ретінде пайдаланылады жалпылама абстракция итератор деп аталады . Әрбір контейнер нақты контейнердің элементтеріне қалай қол жеткізуге болатынын білетін "жаңартылған" интеллектуалды көрсеткіш болып табылатын Итератор түрін қолдайды. C стандарты келесі кестеде сипатталған итераторлардың бес санатын анықтайды :

Категория	Қолдау көрсетілетін операциялар	Ескертпе
Кіру	`operator ++, operator *, operator ->`, көшірме құрастырушысы, `operator =, operator ==, operator !=`	Бір бағытта оқуға қолжетімділікті қамтамасыз етеді. Тағайындау операторы мен көшірме құрастырушысының көмегімен тағайындау немесе көшіру мүмкіндігін береді
Шығу	`operator ++, operator*`, көшірме құрастырушысы	Бір бағытта жазу үшін қол жеткізуді қамтамасыз етеді. Оларды теңдікке салыстыруға болмайды.
Бір бағытты	`operator ++, operator *, operator ->`, көшірме құрастырушысы, әдепкі құрастырушы, `operator =, operator ==, operator !=`	Бір бағытта оқу және жазу үшін қол жеткізуді қамтамасыз етеді. Тағайындау операторы мен көшірме құрастырушысы арқылы тағайындау немесе көшіру мүмкіндігін береді. Оларды теңдікке салыстыруға болады.
Қос бағытты	`operator++, operator--, operator*, operator ->`, көшірме құрастырушысы, әдепкі құрастырушы, `operator =, operator ==, operator !=`	Бір бағытты итераторлар үшін сипатталған барлық функцияларды қолдайды (жоғарыда қараңыз). Сонымен қатар, олар алдыңғы элементке өтуге мүмкіндік береді.
Еркінше қатынау	`operator ++, operator --, operator *, operator ->`, көшірме құрастырушысы, әдепкі құрастырушы, `operator =, operator ==, operator !=, operator +, operator -, operator =, operator -=, operator <, operator >, operator <=, operator >=, operator []`	Кәдімгі көрсеткіштерге эквивалентті: көрсеткіштер арифметикасын, массивтерді индекстеу синтаксисін және салыстырудың барлық нысандарын қолдайды.

Дереккөздер

Сыртқы сілтемелер

SGI STL кластары мен әдістерінің анықтамасы
STL по шагам Артем Каев мақалалары
Основы C++. Библиотека STL Мұрағатталған 27 ақпанның 2007 жылы. — тарату мұрағаты
STL — Стандартная библиотека шаблонов. Руководство C++ программиста — толық нұсқаулық
C++ тілінде STL пайдалану
C++ —тағы STL итераторларына шолу