Лекції по C / C ++: Стандартна бібліотека шаблонів (STL)
Капітан Очевидність підказує:
STL - це спосіб програмувати, чи не навчаючи типові алгоритми
- Контейнери (containers) - це об'єкти, призначені для зберігання набору елементів. Наприклад, вектор, лінійний список, безліч. Асоціативні контейнери (associative containers) дозволяють за допомогою ключів отримати швидкий доступ до зберігаються в них значень. У кожному класі-контейнері визначено набір функцій для роботи з ними. Наприклад, контейнер "список" містить функції для вставки, видалення і злиття елементів.
- Алгоритми (algorithms) виконують операції над вмістом контейнера. Існують алгоритми для ініціалізації, сортування, пошуку, заміни вмісту контейнерів. Багато алгоритми призначені для роботи з послідовністю (sequence), яка являє собою лінійний список елементів всередині контейнера.
- Ітератори (iterators) - це об'єкти, які по відношенню до контейнера грають роль покажчиків. Вони дозволяють отримати доступ до вмісту контейнера і сканувати його елементи, приблизно так само, як покажчики використовуються для доступу до елементів масиву. З ітераторами можна працювати так само, як з покажчиками. До них можна застосовувати операції *, інкремент, декремент. Тип ітератора iterator визначений в різних контейнерах.
Існує п'ять типів ітераторів:
1. Ітератори введення (input iterator) підтримують операції рівності, разименованія і инкремента: ==. =, * I, ++ i, i ++, * i ++. Спеціальним випадком ітератора введення є istream_iterator.
2. Ітератори виведення (output iterator) підтримують операції разименованія, допустимі тільки з лівого боку привласнення, і инкремента: ++ i, i ++, * i = t, * i ++ = t. Спеціальним випадком ітератора виведення є ostream_iterator.
3. Однонаправлені ітератори (forward iterator) підтримують всі операції ітераторів введення / виведення і, крім того, дозволяють без обмеження застосовувати присвоювання: ==. =, =, * I, ++ i, i ++, * i.
4. Двонаправлені ітератори (bidirectional iterator) мають всі властивості forward-ітераторів, а також мають додаткову операцію декремента (--i, i--, * i--), що дозволяє їм проходити контейнер в обох напрямках.
У STL також підтримуються зворотні ітератори (reverse iterators). Зворотними ітераторами можуть бути або двонаправлені ітератори, або ітератори довільного доступу, що проходять послідовність у зворотному напрямку.
Крім контейнерів, алгоритмів і ітераторів, в STL підтримується ще кілька стандартних компонентів.
Головними серед них є розподільники пам'яті, предикати і функції порівняння.
У кожного контейнера є певний для нього розподільник пам'яті (allocator), який управляє процесом виділення пам'яті для контейнера. За замовчуванням розподільником пам'яті є об'єкт класу allocator. Можна визначити власний розподільник.
У деяких алгоритмах і контейнерах використовується функція особливого типу, звана предикатом. Предикат може бути унарним і бінарним. Значення, що повертається предиката - істина або брехня. Точні умови отримання того чи іншого значення визначаються програмістом. Тип унарних предикатів UnPred, бінарних - BinPred. Тип аргументів відповідає типу зберігаються в контейнері об'єктів.
Визначено спеціальний тип бінарного предиката для порівняння двох елементів. Він називається функцією порівняння (comparison function). Функція повертає істину, якщо перший елемент менше другого. Типом функції є тип Comp:
Особливу роль в STL грають функційні об'єкти (функтори). Функційні об'єкти - це екземпляри класу, в якому визначена операція "круглі дужки" (). У ряді випадків зручно замінити функцію на об'єкт-функцію. Коли об'єкт функції використовується в якості опції, то для її виклику використовується operator (). Наведемо закінчений приклад коду, що реалізує даний підхід.
Приклад 1. Видалення рядків зі списку за допомогою функтора.
У STL визначено два основних типи контейнерів: послідовності і асоціативні контейнери. Різниця між ними полягає в тому, що для послідовностей має значення порядок проходження елементів (вектор, стек, чергу), а для асоціативних контейнерів - немає (асоціативний масив, безліч).
Ключова ідея для стандартних контейнерів полягає в тому, що вони повинні бути взаємозамінними, якщо це розумно для вирішення завдання. Користувач може вибирати між контейнерами, грунтуючись на міркуваннях ефективності і потреби в спеціалізованих операціях. Наприклад, якщо часто потрібно пошук по ключу, можна скористатися асоціативним масивом map. З іншого боку, якщо переважають операції, характерні для списків, можна скористатися обліковим контейнером list. Якщо додавання і видалення елементів зазвичай проводиться в початок або кінець контейнера, доречно застосування черзі queue, двосторонньої черги deque або стека stack. За замовчуванням користувач зазвичай застосовує контейнер vector, він реалізований, щоб добре працювати для широкого діапазону завдань.
Ідея звернення з різними видами контейнерів уніфікованим способом веде до поняття узагальненого програмування. Для підтримки цієї ідеї STL містить безліч готових узагальнених алгоритмів. Такі алгоритми позбавляють програміста від необхідності знати подробиці внутрішнього устрою окремих контейнерів.
Коротко опишемо основні можливості STL, докладніше з ними можна познайомитися в стандартній довідці або на сайті cplusplus.com.
Вектор vector в STL визначено як динамічний масив з доступом до її елементів за індексом.
де T - тип призначених для зберігання даних. Allocator задає розподільник пам'яті, який за замовчуванням є стандартним. У класі vector визначені наступні конструктори:
Приклади виклику цих конструкторів:
Загальні принципи роботи з вектором наступні:- Для будь-якого об'єкта, який буде зберігатися у векторі, повинен бути визначений конструктор за замовчуванням. Крім того, для об'єкта повинні бути визначені оператори теги: c ++ навчальний