Ітератори. Алгоритми

Ітератори

Ітератори використовуються для доступу до елементів контейнерів також, як вказівники використовуються для доступу до елементів масивів у С++. Ітератор є "розумним" покажчиком на елемент контейнера. На відміну від звичайного вказівника він пам'ятає повний тип даних на який посилається – з урахуванням типу контейнера, до елемента якого виконується звертання.

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

У залежності від набору підтримуваних операцій розрізняють 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

Приклад побудови програми з використанням стандартної бібліотеки 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; } Результат виконання програми:

Завдання

Виконати завдання складається з двох етапів.

Перший етап виконання роботи полягає у побудові програми розв’язання задачі згідно вказаних варіантів з використанням шаблонів-класів <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

Дана прямокутна матриця. Визначити номер рядка, в якому знаходиться найдовша серія з однакових елементів

⇐ Предыдущая 1 23