Лабораторна робота № 10
Стандартна бібліотека шаблонів. Класи контейнери, ітератори, алгоритми.
Мета роботи: познайомитися із поняттями клас контейнер, ітератор, алгоритм.
Короткі теоретичні відомості
Стандартна бібліотека шаблонів
Стандартна бібліотека шаблонів (Standard Template Lіbrary – STL) входить у стандартну бібліотеку мови C++. Уся бібліотека побудована на шаблонах класів і функцій, що забезпечує можливість уніфікованої роботи з різними типами даних. Використання шаблонів у бібліотеці дозволяє не тільки однаково обробляти вбудовані типи С++, але й працювати з користувацькими типами даних, що не були відомі в момент розробки бібліотеки.
Якщо більш конкретно розглянути склад STL, то в ній можна виділити наступні компоненти:
Контейнери (contaіners) – це класи, призначені для зберігання сукупностей об’єктів (як вбудованих, так і визначених користувачем типів). Найпростіші види контейнерів (статичні і динамічні масиви) вбудовані безпосередньо в мову C++.
Ітератори (іterators) – це абстракція покажчика, тобто об'єкт, що може посилатися на інші об'єкти, що містяться в контейнері. Основні функції ітератора – забезпечення доступу до об'єкта, на який він посилається (розіменування), і перехід від одного елемента контейнера до іншого (ітерація, звідси і назва ітератора). Для вбудованих контейнерів у якості ітераторів використовуються звичайні вказівники. У випадку з більш складними контейнерами ітератори реалізуються у виді класів з набором перевантажених операторів.
Алгоритми (algorіthms) – це функції для маніпулювання об'єктами, що містяться в контейнері. Типові приклади алгоритмів – сортування та пошук. У STL реалізовано порядку 60 алгоритмів, які можна застосовувати до різних контейнерів, у тому числі до масивів, вбудованим у мову C++.
Контейнери
У наступній таблиці приведені основні класи контейнерів бібліотеки STL.
Тип контейнера
Клас контейнера
Деректива #include

Послідовні контейнери
(Sequence containers)
vector – масиви
< vector >


deque – двостороння черга
<deque>


lіst – списки
< lіst>

Асоціативні контейнери
(Associative containers)
map, multіmap – карти; це структури, подібні до масиву, але в яких роль "індексу" можуть відігравати не тільки цілі числа, але будь-які упорядковані типи
<map>


set, multіset – множини
<set>


bitset – множини як бітові набори
<bitset>

Адаптори
(Container adaptors)
queue – черги, організовані за принципом FIFO
priority queue – пріоритетні черги
<queue>


stack – стеки, організовані за принципом LIFO
<stack>


Як уже зазначалось, контейнер призначений для збереження об'єктів. Хоча внутрішня організація контейнерів дуже сильно відрізняється, кожен контейнер зобов'язаний надати строго визначений інтерфейс, через який з ним будуть взаємодіяти алгоритми. Цей інтерфейс забезпечують ітератори. Кожен контейнер зобов'язаний мати відповідний йому ітератор. Важливо підкреслити, що жодні додаткові функції-члени для взаємодії алгоритмів і контейнерів не використовуються. Це зроблено тому, що стандартні алгоритми повинні працювати в тому числі з вбудованими контейнерами мови C++, у яких є ітератори (вказівники), але немає нічого, крім них. Власне тому при написанні власного контейнера реалізація ітератора – необхідний мінімум.
Кожен контейнер реалізує визначений тип ітераторів. При цьому вибирається найбільш функціональний тип ітератора, що може бути ефективно реалізований для даного контейнера. "Ефективно" означає, що швидкість виконання операцій над ітератором не повинна залежати від кількості елементів у контейнері. Наприклад, для вектора реалізується ітератор з довільним доступом, а для списку – двонаправлений. Оскільки швидкість виконання операції [] для списку лінійно залежить від його довжини, ітератор з довільним доступом для списку не реалізується.
Незалежно від фактичної організації контейнера елементи, що зберігаються в ньому, можна розглядати як послідовність. Ітератор першого елемента в цій послідовності повертає функція begіn(), а ітератор елемента, що слідує за останнім – функція end(). Це дуже важливо, тому що всі алгоритми в STL працюють саме з послідовностями, заданими ітераторами початку і кінця. Крім звичайних ітераторів у STL існують зворотні ітератори (reverse іterator). Зворотній ітератор відрізняється тим, що переглядає послідовність елементів у контейнері в зворотному порядку. Іншими словами, операції + і – у нього міняються місцями. Це дозволяє застосовувати алгоритми як до прямої, так і до зворотної послідовності елементів.

Ітератори
Ітератори використовуються для доступу до елементів контейнерів також, як вказівники використовуються для доступу до елементів масивів у С++. Ітератор є "розумним" покажчиком на елемент контейнера. На відміну від звичайного вказівника він пам'ятає повний тип даних на який посилається – з урахуванням типу контейнера, до елемента якого виконується звертання.
Ітератори, як було зазначено, є центральним механізмом, що забезпечує роботу з даними контейнерів. Вони є аналогом покажчиків і уможливлюють циклічний перебір всіх елементів контейнера. Існують різні види ітераторів, оскільки різні алгоритми по-різному звертаються до даних. Кожен клас контейнера може породжувати ітератори, необхідні для роботи притаманних йому алгоритмів.
У залежності від набору підтримуваних операцій розрізняють 5 типів ітераторів, що приведені в наступній таблиці.
Тип ітератора
Доступ
Розіменування
Ітерація
Порівняння

Ітератор виводу
(output іterator)
Тільки запис
*
++


Ітератор вводу
(іnput іterator)
Тільки читання
*, ->
++
= =, !=

Прямий ітератор
(Forward іterator)
Читання і запис
*, ->
++
= =, !=

Двонапрямлений ітератор
(bіdіrectіonal іterator)
Читання і запис
*, ->
++, --
= =, !=

Ітератор з довільним доступом
(random-access іterator)
Читання і запис
*, ->, []
++,--, +, -, +=, -=
= =, !=, <,
<=, >, >=


Ітератор з довільним доступом реалізує повний набір операцій, що застосовуються до звичайних вказівників.
Алгоритми
Бібліотека STL надає основні види алгоритмів:
Математичні (розрахунок сум, добутків, генерація випадкових значень)
Пошуку (мінімальне значення, пошук послідовності, підрахунок числа значень)
Сортування
Роботи з послідовностями (об'єднання послідовностей, порівняння, обробки послідовності типовою операцією)
Як уже зазначалось алгоритми призначені для маніпулювання елементами контейнера. Будь-який алгоритм розглядає вміст контейнера як послідовність, що задається ітераторами першого і наступного за останнім елементів. Ітератори забезпечують інтерфейс між контейнерами й алгоритмами, завдяки чому і досягається гнучкість і універсальність бібліотеки STL.
Кожен алгоритм використовує ітератори визначеного типу. Наприклад, алгоритм простого пошуку (fіnd) переглядає елементи підряд, поки потрібний не буде знайдений. Для такої процедури цілком достатньо літератора вводу. З іншого боку, алгоритм більш швидкого двійкового пошуку (bіnary_search) повинен мати можливість переходити до будь-якого елемента послідовності, і тому вимагає ітератора з довільним доступом. Цілком природно, що замість менш функціонального ітератора можна передати алгоритмові більш функціональний, але не навпаки.
Нижче наведений приклад контейнерного класу створеного користувачем.
#include <iostream>
using namespace std;
class Stack{
int items[10];
int sp;
public:
friend class StackIter;
Stack()
{
sp = - 1;
}
void push(int in)
{
items[++sp] = in;
}
int pop()
{
return items[sp--];
}
bool isEmpty()
{
return (sp == - 1);
}
};
class StackIter{
const Stack &stk;
int index;
public:
StackIter(const Stack &s): stk(s)
{
index = 0;
}
void operator++()
{
index++;
}
bool operator()()
{
return index != stk.sp + 1;
}
int operator *()
{
return stk.items[index];
}
};
bool operator == (const Stack &l, const Stack &r)
{
StackIter itl(l), itr(r);
for (; itl(); ++itl, ++itr)
if (*itl != *itr) break;
return !itl() && !itr();
}
int main()
{
Stack s1;
int i;
for (i = 1; i < 5; i++)
s1.push(i);
Stack s2(s1), s3(s1), s4(s1), s5(s1);
s3.pop();
s5.pop();
s4.push(2);
s5.push(9);
cout << "1 == 2 is " << (s1 == s2) << endl;
cout << "1 == 3 is " << (s1 == s3) << endl;
cout << "1 == 4 is " << (s1 == s4) << endl;
cout << "1 == 5 is " << (s1 == s5) << endl;
return 0;
}
Результат виконання програми
1 == 2 is 1
1 == 3 is 0
1 == 4 is 0
1 == 5 is 0 Press any key to continue

ДОДАТОК до лабораторної роботи №10.
Приклад побудови програми з використанням стандартної бібліотеки STL.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
const int N=10;
void main()
{
vector<int> v(N); //створення обєкту типу vector
vector<int>::iterator vv;//оголошення ітератора
for(int i = 0; i < v.size(); i++) {
v[i]=(rand()%25)*3;
}
cout<<endl;
for(vv=v.begin(); vv!=v.end(); vv++){
cout<<" "<<*vv;
} // методи begin() та end() повертають ітератор, //відповідно, на початок та кінець елементів контейнера
cout<<endl;
int j;
cout<<"\nVvedit element dla poshuku:";
cin>>j;
vv=find(vv=v.begin(),vv= v.end(), j);//виклик функції
// find() пошуку елементу контейнера
cout<<" vv="<<*vv<<endl;
}
Результат виконання програми:
48 51 27 0 57 72 9 24 36 42
Vvedit element dla poshuku: 57
vv=57
Press any key to continue…..



Завдання
Виконати завдання складається з двох етапів.
Перший етап виконання роботи полягає у побудові програми розв’язання задачі згідно вказаних варіантів з використанням шаблонів-класів <vector> (клас масиву) , <algorithm> (клас алгоритмів) та ітератора бібліотеки STL. Використання шаблонів-класів здійснюється шляхом включення відповідних заголовочних файлів. Слід також використати основні методи контейнерних класів:
begin()- повернення ітератора до початкового елементу масиву контейнера,
end()- повернення ітератора на позицію останнього елементу контейнера,
size()-повернення кількості елементів масиву контейнера
Бібліотека STL підтримує відповідний клас ітераторів, що містять основні методи(функції) роботи ітераторів, такі як:
pd++, ++pd - інкременти,переміщення ітератора по всім елементам контейнера,
*pd- розіменування ітератора,тобто повернення або присвоєння значення елемента контейнера,а також інші функії, такі як присвоєння одного ітератора іншому (pd1= pd2) або порівняння двох ітераторів(pd1== pd2).
Запис у програмі при оголошенні ітератора, для прикладу, матиме вигляд:
vector<class T>:: iterator pd;
де vector –шаблон класу, <class T>- базовий тип елементів даних контейнера, ::- унарна операція області видимості, iterator-ключове слово, pd-ім’я ітератора.
Другий етап роботи полягатиме у побудові програми розв’язання задачі згідно вказаних варіантів з використанням власного шаблону-класу <VECTOR> (клас контейнера масиву) та дружнього класу ітератора. Контейнерний клас повинен містити дані масиву та основні методи, що були вище обумовлені, як основні методи контейнерних класів. Клас ітераторів повинен мітити основні функції роботи ітераторів, що також обумовленні вище. При виконанні завдання звертайте увагу на вищенаведені приклади.
Варіант 1В масиві обчислити різницю елементів масиву, що розташовані між першим від'ємним та другим додатним елементами.
Варіант 2 Дана прямокутна матриця. Визначити кількість від'ємних елементів в тих рядках, які містять хоча б один нульовий елемент;
Варіант 3 У довільній матриці обчислити кількість елементів масиву, рівних нулю;
Варіант 4 В одновимірному масиві елементів, обчислити суму модулів елементів, які розташовані після першого додатного елемента.
Варіант 5 У матриці обчислити суму елементів масиву, що розташовані між першим і другим додатними елементами.
Варіант 6
Дана прямокутна матриця. Визначити номер рядка, в якому знаходиться найдовша серія з однакових елементів