 |
|
Основний зміст роботи.
Написати чотири програми з використанням STL. Перша і друга програми повинні демонструвати роботу з контейнерами STL, третя і четверта — використання алгоритмів STL.
Основні теоретичні відомості.
Стандартна бібліотека шаблонів (STL).
STL забезпечує загально цільові, стандартні класи і функції, що реалізують найбільш популярні і широко використовувані алгоритми і структури даних.
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.Двохнаправлені літератори(biderectional_iterator) мають усі властивості forward-ітераторів, а також мають додаткову операцію декремента (--i, i--, *i--), що дозволяє їм проходити контейнер в обох напрямках.
5.Ітератори довільного доступу(random_access_iterator) мають усі властивості biderectional-ітераторів, а також підтримують операції порівняння та адресної арифметики, а саме безпосередній доступ за індексом.
i+=n, i+n, i-=n, i-n, i1-i2, i[n], i1<i2, i1<=i2, i1>i2, i1>=i2
У STL також підтримуються зворотні ітератори (reverse iterators). Зворотніми ітераторами можуть бути або двонаправлені ітератори, або ітератори довільного доступу, але минаючі послідовність у зворотному напрямку.
Надодачу до контейнерів, алгоритмів і ітераторів у STL підтримується ще кілька стандартних компонентів. Головними серед них є розподільники пам'яті, предикати і функції порівняння.
У кожного контейнера є визначений для нього розподільник пам'яті (allocator), що керує процесом виділення пам'яті для контейнера.
За замовчуванням розподільником пам'яті є об'єкт класу allocator. Можна визначити власний розподільник.
У деяких алгоритмах і контейнерах використовується функція особливого типу, що називається предикатом. Предикат може бути унарним і бінарним. Значення, що повертається: істина або неправда. Точні умови одержання того чи іншого значення визначаються програмістом. Тип унарних предикатів UnPred, бінарних – BinPred. Тип аргументів відповідає типу об'єктів, що зберігаються в контейнері.
Визначено спеціальний тип бінарного предиката для порівняння двох елементів. Він називається функцією порівняння (comparison function). Функція повертає істину, якщо перший елемент менше другого. Типом функції є тип Comp.
Особливу роль у STL грають об'єкти-функції.
Об'єкти-функції - це екземпляри класу, у якому визначена операція “круглі дужки” (). У ряді випадків зручно замінити функцію на об'єкт - функцію. Коли об'єкт – функція використовується як функцію, то для її виклику використовується operatot().
Приклад 1.
class less{
public:
bool operator()(int x,int y)
{return x<y;}
};
Класи-контейнери.
У STL визначені два типи контейнерів – послідовності й асоціативні контейнери.
Ключова ідеядля стандартних контейнерів полягає в тім, що коли це представляється розумним, вони повинні бути логічно взаємозамінними. Користувач може вибирати між ними, ґрунтуючись на розуміннях ефективності і потреби в спеціалізованих операціях. Наприклад, якщо часто потрібен пошук по ключі. можна скористатися map (асоціативним масивом). З іншого боку, якщо переважають операції, характерні для списків, можна скористатися контейнером list. Якщо додавання і видалення елементів часто виконується в кінці контейнера, варто подумати про використання черги queue, черги з двома кінцями deque, стека stack. За замовчуванням користувач повинний використовувати vector; він реалізований, щоб добре працювати для самого широкого діапазону задач.
Ідея звертання з різними видами контейнерів – і, у загальному випадку, із усіма видами джерел інформації – уніфікованим способом, веде до поняття узагальненого програмування. Для підтримки цієї ідеї STL містить множину узагальнених алгоритмів. Такі алгоритми рятують програміста від необхідності знати подробиці окремих контейнерів.
У STL визначені наступні класи-контейнери(у кутових дужках зазначені заголовні файли, де визначені ці класи):
bitset множину бітів <bitset.h>
vector динамічний масив <vector.h>
list лінійний список <list.h>
deque двостороння черга <deque.h>
stack стек <stack.h>
queue черга <queue.h>
priority_queueчерга з пріоритетом <queue.h>
map асоціативний список для збереження пар ключ/значення, де з кожним ключем зв'язане одне значення <map.h>
multimap з кожним ключем зв'язано два чи більше значення <map.h>
set множина <set.h>
multiset множина, у якій кожен елемент не обов'язково унікальний <set.h>
Огляд операцій
Типи
value_typeтип елемента
allocator_type тип розподільника пам'яті
size_type тип індексів, лічильника елементів і т.д.
iterator поводиться як value_type*
reverse_iterator переглядає контейнер у зворотному порядку
reference поводиться як value_type&
key_type тип ключа (тільки для асоціативних контейнерів)
key_compare тип критерію порівняння (тільки для асоціативних контейнерів)
mapped_type тип відображеного значення
Ітератори
begin() вказує на перший елемент
end() вказує на елемент, що випливає за останнім
rbegin() вказує на перший елемент у зворотній послідовності
rend() вказує на елемент, що випливає за останнім у зворотній послідовності
Доступ до елементів
front() посилання на перший елемент
back() посилання на останній елемент
operator[](i) доступ за індексом без перевірки
at(i) доступ за індексом з перевіркою
Включення елементів
insert(p,x) додавання х перед елементом, на який вказує р
insert(p,n,x) додавання n копій х перед р
insert(p,first,last) додавання елементів з [first:last] перед р
push_back(x) додавання х в кінець
push_front(x) додавання нового першого елемента (тільки для списків і черг із двома кінцями)
Видалення елементів
pop_back() видалення останнього елемента
pop_front() видалення першого елемента (тільки для списків і черг із двома кінцями)
erase(p) видалення елемента в позиції р
erase(first,last) видалення елементів з [first:last]
clear() видалення всіх елементів
Інші операції
size() число елементів
empty() контейнер порожній?
capacity()пам'ять, виділена під вектор (тільки для векторів)
reserve(n) виділяє пам'ять для контейнера під n елементів
resize(n) змінює розмір контейнера (тільки для векторів, списків і черг із двома кінцями)
swap(x) обмін місцями двох контейнерів
==, !=, < операції порівняння
Операції присвоювання
operator=(x) контейнеру привласнюються елементи контейнера х
assign(n,x) присвоювання контейнеру n копій елементів х (не для асоціативних контейнерів)
assign(first,last) присвоювання елементів з діапазону [first:last]
Асоціативні операції
operator[](k)доступ до елемента з ключем k
find(k) знаходить елемент із ключем k
lower_bound(k) знаходить перший елемент із ключем k
upper_bound(k) знаходить перший елемент із ключем великим k equal_range(k) знаходить lower_bound (нижню границю) і upper_bound (верхню границю) елементів із ключем k