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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Структура бібліотеки[ред.ред. код]

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

  1. Контейнер (container) - зберігання набору об'єктів в пам'яті.
  2. Ітератор (iterator) - забезпечення засобів послідовного доступу до вмісту контейнера.
  3. Алгоритм (algorithm) - визначення обчислювальної процедури.
  4. Адаптер (adaptor) - адаптація компонентів для забезпечення різного інтерфейсу.
  5. Функціональний об'єкт (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 [] Еквівалентні звичайним вказівникам: підтримують арифметику вказівників, синтаксис індексації масивів і усі форми порівняння.

Посилання[ред.ред. код]