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

Стандартна бібліотека шаблонів (англ. Standard Template Library; STL) — бібліотека для C++, що містить набір узгоджених узагальнених алгоритмів, контейнерів, засобів доступу до їхнього вмісту і різних допоміжних функцій.

Стандартна бібліотека шаблонів до включення в стандарт C++ була сторонньою розробкою, на початку — фірми HP, а потім SGI. Стандарт мови не називає її «STL», оскільки ця бібліотека стала невід'ємною частиною мови, проте багато людей досі використовують цю назву, щоб відрізняти її від решти частини стандартної бібліотеки (потоки вводу/виводу (iostream), підрозділ Сі тощо).

Проект під назвою STLPort, заснований на SGI STL, здійснює постійне оновлення STL, IOstream і рядкових класів. Деякі інші проєкти також займаються розробкою приватних застосувань стандартної бібліотеки для різних конструкторських завдань. Кожен виробник компіляторів C++ обов'язково поставляє яку-небудь реалізацію цієї бібліотеки, оскільки вона є дуже важливою частиною стандарту і широко використовується.

Структура бібліотеки

У бібліотеці виділяють чотири основні компоненти:

1. Контейнер (container) — зберігання набору об'єктів в пам'яті.
2. Ітератор (iterator) — забезпечення засобів послідовного доступу до вмісту контейнера.
3. Алгоритм (algorithm) — визначення обчислювальної процедури.
4. Функціональний об'єкт (functor) — заховання функції в об'єкті для використання іншими компонентами.

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

Контейнери

Контейнери бібліотеки STL можна розділити на чотири категорії: послідовні, асоціативні, контейнери-адаптери і псевдоконтейнери.

Контейнер	Опис
Послідовні контейнери
vector	C-подібний динамічний масив довільного доступу з автоматичною зміною розміру при додаванні/видаленні елементу. Додавання-видалення елементу в кінець vector займає амортизоване $O(1)$ час, та ж операція на початку або середині vector — $O(n)$. Існує спеціалізація шаблону vector для типу bool, яка вимагає менше пам'яті за рахунок зберігання bool у вигляді бітів.
list	Двозв'язковий список, елементи якого зберігаються в довільних шматках пам'яті, на відміну від контейнера vector, де елементи зберігаються в безперервній області пам'яті. Повільний пошук і доступ за $O(n)$, в будь-якому місці швидка вставка і видалення за $O(1)$.
deque	Схожий на vector, але з можливістю швидкої вставки і видалення елементів на обох кінцях.
Асоціативні контейнери
set	Впорядкована множина унікальних елементів. При вставці/видаленні елементів множини ітератори, що вказують на елементи цієї множини, не стають недійсними. Забезпечує стандартні операції над множиною типу об'єднання, перетину, віднімання. Тип елементів множини повинен реалізовувати оператора порівняння operator< або потрібно надати функцію-компаратор. Реалізований на основі самобалансуючого дерева двійкового пошуку.
multiset	Те ж що і set, але дозволяє зберігати елементи, що повторюються.
map	Впорядкований асоціативний масив пар елементів, що складаються з ключів і відповідних ним значень. Ключі повинні бути унікальні. Порядок проходження елементів визначається ключами. При цьому тип ключа повинен реалізовувати оператора порівняння operator<, або потрібно надати функцію-компаратор.
multimap	Те ж що і map, але дозволяє зберігати ключі, що повторюються.
Контейнери-адаптери
stack	Стек — контейнер, в якому додавання і видалення елементів здійснюється з одного кінця.
queue	Черга — контейнер, з одного кінця якого можна додавати елементи, а з іншого — виймати.
priority_queue	Черга з пріоритетом, організована так, що найбільший елемент завжди стоїть на першому місці.
Псевдоконтейнери
bitset	Служить для зберігання бітових масок. Схожий на vector<bool> фіксованого розміру. Розмір фіксується тоді, коли оголошується об'єкт bitset. Ітераторів в bitset немає. Оптимізований за розміром пам'яті.
basic_string	Контейнер, призначений для зберігання і обробки рядків. Зберігає в пам'яті елементи підряд єдиним блоком, що дозволяє швидкий доступ до всієї послідовності.
valarray	Шаблон служить для зберігання числових масивів і оптимізований для досягнення підвищеної обчислювальної продуктивності. Деякою мірою схожий на vector, але в нім відсутня більшість стандартних для контейнерів операцій. Проте, в ньому реалізовані операції, які можна ефективно реалізувати як на векторних процесорах, так і на скалярних процесорах з блоками 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();	Результат не використовується	Лінійна	Після: а.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(рос.) — архів розсилки
• STL — Стандартная библиотека шаблонов. Руководство C++ программиста(рос.) — докладне керівництво
• Использование STL в C++(рос.)