12. Введення в стандартну бібліотеку шаблонів

Матеріал цього розділу містить інформацію про те, який за останні роки є найважливішим доповненням у мові програмування C++. Йдеться про стандартну бібліотеку шаблонів (Standard Template Library – STL). Саме внесення бібліотеки STL у мову програмування C++ було основною подією, яка наполегливо обговорювалася у період стандартизації мови C++. Бібліотека STL надає користувачу шаблонні класи і функції загального призначення, які реалізують багато популярних і часто використовуваних алгоритмів і структур даних. Наприклад, вона містить підтримку векторів, списків, черг і стеків, а також визначає різні функції, які забезпечують до них доступ. Оскільки бібліотека STL складається з шаблонних класів, то алгоритми і структури даних можна застосовувати до даних практично будь-якого типу.

Бібліотека STL – це результат розроблення стандартного програмного забезпечення, який увібрав у себе одні з найскладніших засобів мови програмування C++. Щоб розуміти вміст бібліотеки STL і уміти ним користуватися, необхідно досконало засвоїти весь матеріал, викладений у попередніх розділах. Особливо добре потрібно орієнтуватися в шаблонах. Відверто кажучи, шаблонний синтаксис, який використовує бібліотека STL, може спочатку налякати програмістів-початківців, хоча він виглядає дещо складнішим, ніж є насправді. Незважаючи на те, що матеріал цього розділу є не набагато важчим за будь-який інший, наведений у цьому навчальному посібнику, проте не варто засмучуватися від того, якщо щось на перший погляд Вам видасться незрозумілим. Трохи терпіння під час перегляду прикладів і певної уваги у процесі їх детального аналізу приведе до того, що незабаром Ви зрозумієте, як за незвичним синтаксисом ховається строга простота бібліотеки STL.

STL – достатньо велика бібліотека, і всі її засоби неможливо викласти в одному розділі. Повний опис бібліотеки STL зі всіма її особливостями і методами програмування займає цілу книгу. Мета представленого тут матеріалу – познайомити студентів з основними операціями, принципами проектування і основами STL-програмування. Засвоївши матеріал цього розділу, студент зможете самостійно легко вивчити іншу частину бібліотеки STL.

У цьому розділі також описано ще один важливий клас C++ – клас string. Він призначений для визначення рядкового типу даних, який дає змогу обробляти символьні рядки подібно до того, як обробляються дані інших типів за допомогою операторів. Клас string тісно пов'язаний з бібліотекою STL.

12.1. Огляд стандартної бібліотеки шаблонів

Незважаючи на великий розмір стандартної бібліотеки шаблонів (STL) та інколи лякливий синтаксис, насправді її засоби достатньо легко використовувати, якщо зрозуміти, як вона побудована і з яких елементів складається. Тому, перш ніж переходити до перегляду прикладів, познайомимося з основними складовими бібліотеки STL.

Ядро стандартної бібліотеки шаблонів містить три основні елементи: контейнери, алгоритми і ітератори. Вони працюють спільно один з іншим, надаючи тим самим користувачу готові розв'язки різних задач програмування.

Контейнери - це об'єкти, які містять інші об'єкти.

Існує декілька різних типів контейнерів. Наприклад, клас vector визначає динамічний масив, клас queue створює двосторонню чергу, а клас list забезпечує роботу з лінійним списком. Ці контейнери називають послідовними контейнерами і є базовими в бібліотеці STL. Окрім базових, бібліотека STL визначає асоціативні контейнери, які дають змогу ефективно знаходити потрібні значення на основі за даних ключових значень (ключів). Наприклад, клас map забезпечує зберігання пар "ключ-значення" і надає змогу знаходити потрібне значення за заданим унікальним ключем.

Кожен контейнерний клас визначає набір функцій, які можна застосовувати для роботи з ним. Наприклад, контейнер списку містить функції, призначені для виконання вставлення, видалення і об'єднання елементів. А стек містить функції, які дають змогу поміщати значення у стек і витягувати їх із нього.

Їх можливості містять засоби ініціалізації, сортування, пошуку і перетворення вмісту контейнерів. Багато алгоритмів працюють із заданим діапазоном елементів контейнера.

Ітератори – це об'єкти, які тією чи іншою мірою діють подібно до покажчиків. Вони дають змогу циклічно здійснювати запит до вмісту контейнера практично так само, як це робиться за допомогою покажчика під час циклічного доступу до елементів масиву. Існує п'ять типів ітераторів.

Табл. 12.1. Типи ітераторів

Ітератори	Опис
Довільного досту­пу (random access)	Зберігають і зчитують значення: дають змогу організувати довіль­ний доступ до елементів контейнера
Двонаправлені (bi­directional)	Зберігають і зчитують значення: забезпечують інкрементно-дек- ременгне переміщення
Однонаправлені (forward)	Зберігають і зчитують значення: забезпечують тільки інкрементне переміщення елементами контейнера
Вхідні (GetPut)	Зчитують, але не записують значення; забезпечують тільки інкре­ментне переміщення елементами контейнера
Вихідні (output)	Записують, але не зчитують значення; забезпечують тільки інкре­ментне переміщення елементами контейнера

У загальному випадку ітератор з більшими можливостями доступу, можна використовувати замість ітератора з меншими можливостями. Наприклад, однонаправлений ітератор може замінити вхідний ітератор ідерементувати. До них можна застосовувати оператор перейменування адреси

*. Ітератори оголошуються за допомогою типу iterator, який визначається різними контейнерами.

Бібліотека STL підтримує реверсивні ітератори, які є або двонаправленими, або ітераторами довільного доступу, даючи змогу переміщатися елементами послідовності у зворотному порядку. Отже, якщо реверсивний ітератор вказує на кінець послідовності, то після інкрементування він вказуватиме на елемент, розташований перед кінцем послідовності.

Під час посилання на різні типи ітераторів у описах шаблонів у цьому навчальному посібнику буде використано такі терміни:

Термін	Наданий ітератор
Bilter	Двонаправленнй
Forlter	Однонаправлений
Inlter	Вхідний
OutLter	Вихідний
Randlter	Довільного доступу

Бібліотека STL опирається не тільки на контейнери, алгоритми і ітератори, але і на інші стандартні компоненти. Основними з них є розподільники пам'яті, предикати і функції порівняння.

Кожен контейнер має свій розподільник пам'яті (allocator). Розподільники керують виділенням пам'яті під елементи контейнера. Стандартний розподільник – це об'єкт класу allocator, але у разі потреби (у спеціалізованих додатках) можна визначати власні розподільники. Здебільшого стандартного розподільника є цілком достатньо для реалізації програмних задумів.

Деякі алгоритми і контейнери використовують спеціальний тип функції, так званий предикат (predicate). Існує два варіанти предикатів: унарний і бінарний. Унарний предикат приймає один аргумент, а бінарний – два. Ці функції повертають значення ІСТИНА/ФАЛЬШ, але точні умови, які примусять їх повернути дійсне або помилкове значення, визначаються програмістом. В іншій частині цього розділу, коли знадобиться унарна функція-предикат, на це буде вказано за допомогою типу UnPred. У разі потреби використання бінарного предиката застосовуватиметься тип BinPred. У бінарному предикаті аргументи завжди розташовані у порядку перший, другий стосовно функції, яка викликає цей предикат. Як для унарного, так і для бінарного предикатів аргументи повинні містити значення, тип яких збігається з типом об'єктів, які зберігає цей контейнер.

Деякі алгоритми і класи використовують спеціальний тип бінарного предиката, який порівнює два елементи. Функції порівняння повертають значення true, як-що їх перший аргумент менший від другого. Функції порівняння ідентифікуються за допомогою типу Comp.

Крім заголовків, потрібних різним класам STL, стандартна бібліотека C++ містить заголовки <utility> і <functional>, які забезпечують підтримку STL. Наприклад, у заголовку <utility> визначається шаблонний клас pair, який може зберігати пару значень. Будемо використовувати клас pair нижче у цьому розділі.

Шаблони у заголовку <functional> дають змогу створювати об'єкти, які визначають функцію operator(), називаються об'єктами-функціями. Їх у багатьох випадках можна використовувати замість покажчиків на функції. Існує декілька вбудованих об'єктів-функцій, оголошених у заголовку <functional>. Нижче наведено деякі з них:

plus	minus	multiplies	divides	modulus
negate	equal_to	not_equal_to	greater	greater_equal
less	less_equal	logical_and	logical_or	logical_not

Можливо, найширше використовується об'єкт-функція less, який визначає, за яких умов один об'єкт менший від іншого. Об'єкти-функції можна використовувати замість реальних покажчиків на функції в алгоритмах бібліотеки STL, про які піде мова нижче. Використовуючи об'єкти-функції замість покажчиків на функції, бібліотека STL у деяких випадках генерує ефективніший програмний код. Матеріал цього розділу не передбачає використання об'єктів-функцій, тому ми не застосовуватимемо їх безпосередньо. Детальний опис об'єктів-функцій можна знайти в книзі Герберта Шілдта "Полный справочник по C++".