Бібліотека стандартних шаблонів STL (Standard Template Library). Загальні поняття. Контейнери. Алгоритми. Ітератори. Функтори

Дана тема є початком вивчення бібліотеки STL мови C++.

---

Зміст

• 1. Бібліотека STL. Загальні відомості
• 2. Контейнери. Загальні відомості. Перелік
• 3. Алгоритми. Загальні відомості
• 4. Ітератори. Загальні відомості
• 5. Функтори. Загальні відомості
• Споріднені теми

---

Пошук на інших ресурсах:

1. Бібліотека STL. Загальні відомості

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

Розрізняють такі основні складові (компоненти) бібліотеки STL:

• контейнери (container);
• алгоритми (algorithm);
• ітератори (iterator);
• функціональні об’єкти або функтори (functor).

Використання та поєднання цих складових дозволяє програмувати розв’язки дуже широкого кола задач програмування.

  ⇑

2. Контейнери. Загальні відомості. Перелік

У програмуванні контейнер – це об’єкт, що зберігає інші об’єкти всередині себе. Об’єкти, що зберігаються в контейнерах, можуть бути як базових (примітивних) типів так і екземпляри класів з відповідним необхідним функціоналом.

У бібліотеці STL реалізовано наступні контейнери:

• bitset – набір бітів;
• deque – двохстороння черга;
• list – лінійний список;
• map – асоціативний контейнер, побудований за принципом key:value, в якому кожному ключу key відповідає значення value;
• multimap – асоціативний контейнер, в якому одному значенню (key) відповідає декілька значень (value1, value2, …, valueN);
• multiset – множина, в якій той самий елемент може зустрічатись декілька разів;
• priority_queue – черга з пріоритетами;
• queue – черга;
• set – множина, в якій кожен елемент зустрічається тільки один раз;
• stack – стек;
• vector – динамічний масив.

  ⇑

3. Алгоритми. Загальні відомості

Вміст контейнерів обробляється з допомогою алгоритмів. Алгоритми дозволяють опрацьовувати контейнери на будь-який смак: ініціалізовувати, сортувати вміст контейнерів, перетворювати, реалізовувати різні види пошуку тощо.

Щоб мати доступ до алгоритмів, потрібно підключити відповідну бібліотеку

#include <algorithm>

Усі алгоритми є шаблонними функціями. Вони можуть бути застосовані до будь-якого типу контейнера. Нижче наведено перелік алгоритмів бібліотеки STL:

• adjacent_find – здійснює пошук пари сусідніх елементів, які співпадають між собою;
• binary_search – виконує бінарний пошук в упорядкованій послідовності;
• copy – копіює одну послідовність в іншу;
• copy_backward – робить те саме що й copy, тільки результуюча послідовність записується у зворотньому порядку;
• count – підраховує кількість входжень заданого елементу в послідовності;
• count_if – обчислює кількість входжень елементу в послідовності, що відповідає заданій умові;
• equal – визначає, чи співпадають елементи двох діапазонів;
• equal_range – повертає діапазон, який допускає вставку елементів без порушення порядку;
• fill, fill_n – заповнюють діапазон потрібними значеннями;
• find – здійснює пошук елементу в заданій послідовності, повертає позицію (ітератор) першого входження елементу в послідовності;
• find_end – здійснює пошук останнього входження підпослідовності, що міститься в заданому діапазоні;
• find_first_of – виконує пошук першого елементу підпослідовності, що співпадає з будь-яким елементом іншої підпослідовності;
• find_if – знаходить перший елемент послідовності, що співпадає з елементом з іншої послідовності;
• for_each – застосовує задану функцію до заданого діапазону елементів;
• generate, generate_n – присвоюють елементам діапазону значення, що повертаються функцією-генератором;
• include – визначає, чи містить одна послідовність іншу;
• inplace_merge – об’єднує два діапазони;
• iter_swap – здійснює обмін місцями двох значень, на які вказують аргументи;
• lexicographical_compare – здійснює лексикографічне порівняння двох послідовностей;
• lower_bound – визначає перший елемент послідовності, який не менше заданого значення;
• make_heap – на основі заданої послідовності створює “купу”;
• max – повертає максимум з двох значень;
• max_element – повертає позицію (ітератор), що встановлена на максимальний елемент послідовності;
• merge – об’єднує дві впорядковані послідовності. Результат записується в третю послідовність;
• min – з двох значень повертає мінімальне;
• min_element – повертає позицію (ітератор), яка встановлена на мінімальний елемент послідовності;
• mismatch – для двох заданих послідовностей знаходить перше неспівпадіння;
• next_permutation – формує наступну перестановку елементів послідовності;
• nth_element – впорядковує послідовність таким чином, що всі елементи, які менше заданого елементу, розміщуються перед цим елементом в послідовності;
• partial_sort – виконує сортування елементів у заданому діапазоні;
• partial_sort_copy – впорядковує елементи послідовності в заданому діапазоні, потім копіює в результуючу послідовність відсортовані елементи;
• partition – впорядковує послідовність так, щоб всі елементи, які відповідають заданій умові, розміщувались перед всіма іншими елементами цієї послідовності;
• pop_heap – міняє місцями перший та передостанній елементи та перебудовує “купу”;
• prev_permutation – відтворює попередню перестановку, що складається з елементів послідовності;
• push_heap – заштовхує елемент в кінець купи;
• random_shuffle – змінює послідовність в заданому діапазоні;
• remove – видаляє з вказаної послідовності елементи, які мають визначене значення;
• remove_if – видаляє з вказаної послідовності елементи згідно заданого предикату;
• remove_copy – копіює з вказаної послідовності елементи, що мають визначене значення, у задану послідовність;
• remove_copy_if – копіює з вказаної послідовності елементи в іншу область на основі заданого предикату;
• replace – замінює елементи заданого діапазону з одного значення на інше;
• replace_if – замінює елементи заданого діапазону на основі предикату;
• replace_copy_if – копіює елементи заданої послідовності в іншу область з заміною одного значення на інше;
• replace_copy – копіює елементи заданого діапазону в іншу послідовність, замінюючи елементи на основі заданого предикату іншим значенням;
• reverse – змінює порядок елементів послідовності на протилежний в межах заданого діапазону;
• reverse_copy – змінює порядок елементів в послідовності на протилежни і результат записує в іншу послідовність;
• rotate – виконує циклічний зсув вліво елементів послідовності в заданих межах;
• rotate_copy – виконує циклічний зсув вліво елементів послідовності, результат поміщає в іншу послідовність;
• search – виконує пошук підпослідовності в послідовності;
• search_n – знаходить n-е входження заданого елемента в послідовності;
• set_difference – для двох заданих послідовностей створює послідовність, що містить неспівпадаючі елементи (різниця множин);
• set_intersection – для двох заданих послідовностей створює послідовність, що містить співпадаючі елементи (перетин множин);
• set_symmetric_difference – створює послідовність, що є симетричною різницею двох послідовностей;
• set_union – створює послідовність, що є об’єднанням двох послідовностей;
• sort – впорядковує послідовність в заданому діапазоні;
• sort_heap – впорядковує “купу” всередині заданого діапазону;
• stable_partition – впорядковує послідовність в заданих межах таким чином, щоб всі елементи, які задовільняють заданій умові, передували всім іншим елементам. Розбиття послідовності фіксується;
• stable_sort – впорядковує послідовність в заданих межах таким чином, що рівні елементи не змінюють свої місця;
• swap – міняє місцями значення, що задані посиланнями;
• swap_ranges – міняє місцями елементи заданого діапазону;
• transform – для заданої послідовності виконує функцію до кожного елементу цієї послідовності. Результат зберігається в новій послідовності;
• unique – витягує дублікати з вказаної послідовності;
• unique_copy – робить копію з послідовності витягуючи з неї дублікати (однакові елементи);
• upper_bound – знаходить останній елемент послідовності, що не перевищує задане значення.

  ⇑

4. Ітератори. Загальні відомості

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

Щоб використовувати ітератори потрібно підключити заголовок iterator

#include <iterator>

У C++ розрізняють 5 видів ітераторів:

• RandIter – ітератор довільного доступу – записує та витягує значення з контейнеру. Забезпечує довільний доступ до елементів контейнера;
• BiIter – двонаправлений ітератор – записує та витягує значення. Переміщується вперед і назад;
• ForIter – прямий ітератор – переміщується тільки вперед. Записує та витягує значення;
• InIter – ітератор вводу – тільки витягує значення. Переміщується тільки вперед;
• OutIter – ітератор виводу – тільки записує значення. Переміщується тільки вперед.

В бібліотеці <iostream> визначено наступні класи, що реалізують ітератори:

• iterator – базовий клас для всіх ітераторів;
• iterator_traits – представляє різні типи, що визначені ітератором;
• insert_iterator – забезпечує роботу ітераторів виводу, які вставляють об’єкти в контейнери;
• back_insert_iterator – забезпечує роботу ітераторів виводу, які вставляють об’єкти в кінець контейнера;
• front_insert_iterator – забезпечує роботу ітераторів виводу, які вставляють об’єкти на початок контейнера;
• reverse_iterator – підтримує роботу зворотних ітераторів;
• istream_iterator – підтримує роботу потокових ітераторів вводу;
• istreambuf_iterator – підтримує роботу потокових ітераторів вводу символів;
• ostream_iterator – підтримує роботу потокових ітераторів виводу;
• ostreambuf_iterator – підтримує роботу потокових ітераторів виводу символів.

  ⇑

5. Функтори. Загальні відомості

Для забезпечення гнучкої взаємодії між ітераторами, контейнерами та алгоритмами, використовуються функтори. Функтор – це клас, в якому реалізована операторна функція operator(). Завдяки функторам об’єкт класу представляється як функція.

Щоб використовувати функтори у програмі, потрібно підключити заголовок functional

#include <functional>

У бібліотеці STL функтори поділяються на дві категорії:

• бінарні – містять два аргументи;
• унарні – містять один аргумент.

Бібліотека STL містить наступні бінарні функтори:

• plus – додає (+) два аргументи;
• minus – віднімає (–) аргументи;
• multplies – множить (*) два аргументи;
• divides – ділить (/) аргументи;
• modulus – повертає результат операції % для двох аргументів;
• equal_to – порівнює два аргументи на рівність (==);
• not_equal_to – порівнює два аргументи на нерівність (!=);
• greater – визначає, чи перший аргумент більше другого (>);
• greater_equal – визначає, чи перший аргумент більше або рівне другого (>=);
• less – визначає, чи перший аргумент менше другого (<);
• less_equal – визначає, чи перший аргумент менше або рівне другого (<=);
• logical_and – застосовує до аргументів логічне “I” (AND);
• logical_or – застосовує до двох аргументів логічне “АБО” (OR).

Також визначені два унарні функтори:

• logical_not – застосовує до аргументу логічне “НІ” (NOT);
• negate – змінює знак свого аргументу на протилежний.

  ⇑

---

Споріднені теми

• Шаблон класу. Ключове слово template. Переваги використання шаблонів. Аргументи в шаблонах. Приклади

  ⇑

---