Стандартна бібліотека шаблонів
Стандартна бібліотека шаблонів (англ. Standard Template Library; STL) — бібліотека для C++, що містить набір узгоджених узагальнених алгоритмів, контейнерів, засобів доступу до їхнього вмісту і різних допоміжних функцій.
Стандартна бібліотека шаблонів до включення в стандарт C++ була сторонньою розробкою, на початку — фірми HP, а потім SGI. Стандарт мови не називає її «STL», оскільки ця бібліотека стала невід'ємною частиною мови, проте багато людей досі використовують цю назву, щоб відрізняти її від решти частини стандартної бібліотеки (потоки вводу/виводу (iostream), підрозділ Сі тощо).
Проект під назвою STLPort, заснований на SGI STL, здійснює постійне оновлення STL, IOstream і рядкових класів. Деякі інші проєкти також займаються розробкою приватних застосувань стандартної бібліотеки для різних конструкторських завдань. Кожен виробник компіляторів C++ обов'язково поставляє яку-небудь реалізацію цієї бібліотеки, оскільки вона є дуже важливою частиною стандарту і широко використовується.
Структура бібліотеки ред.
У бібліотеці виділяють чотири основні компоненти:
- Контейнер (container) — зберігання набору об'єктів в пам'яті.
- Ітератор (iterator) — забезпечення засобів послідовного доступу до вмісту контейнера.
- Алгоритм (algorithm) — визначення обчислювальної процедури.
- Функціональний об'єкт (functor) — заховання функції в об'єкті для використання іншими компонентами.
Розділення дозволяє зменшити кількість компонентів. Наприклад, замість написання окремої функції пошуку елементу для кожного типу контейнера забезпечується єдина версія, яка працює з кожним з них, поки дотримуються основні вимоги.
Контейнери ред.
Контейнери бібліотеки STL можна розділити на чотири категорії: послідовні, асоціативні, контейнери-адаптери і псевдоконтейнери.
| Контейнер | Опис |
|---|---|
| Послідовні контейнери | |
| vector | C-подібний динамічний масив довільного доступу з автоматичною зміною розміру при додаванні/видаленні елементу. Додавання-видалення елементу в кінець vector займає амортизоване  час, та ж операція на початку або середині vector —  . Існує спеціалізація шаблону vector для типу bool, яка вимагає менше пам'яті за рахунок зберігання bool у вигляді бітів. |
| list | Двозв'язковий список, елементи якого зберігаються в довільних шматках пам'яті, на відміну від контейнера vector, де елементи зберігаються в безперервній області пам'яті. Повільний пошук і доступ за , в будь-якому місці швидка вставка і видалення за . |
| 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++(рос.)
 | Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її. |