Перекриття методів та алгоритмів

Інколи доводиться вибирати між методами та алгоритмами з однаковими іменами. Наприклад, алгоритму find() потрібний тільки вхідний ітератор, тому він може використовуватися з будь-яким контейнером. Але у множин і відображень є свій власний метод find() (чого немає у послідовних контейнерів). Яку ж версію find() слід вибрати? В загальному випадку, якщо вже наявний метод, що дублює своєю назвою алгоритм, то це зроблено тому, що алгоритм у даному випадку неефективний. Тому, напевно, при наявності такого вибору краще звернутися до методу.

 

Робота з ітераторами

Використовувати ітератори значно простіше, ніж розповідати про них. Розглянемо, як реально використовуються ітератори з тими чи іншими функціями.

Доступ до даних

В контейнерах, зв’язаних з ітераторами довільного доступу (векторах і чергах з двостороннім доступом), ітерація відбувається дуже просто за допомогою оператора []. Такі контейнери, як списки, що не підтримують довільного доступу, вимагають особливого підходу. Раніше ми використовували «деструктивне читання» (читання з руйнуванням даних) для виведення і одночасного виштовхування елементів ітератора. Практичніше було б визначити ітератор для контейнера. Розглянемо приклад 15.17.

 #include<iostream>

 #include<conio>

 #include<list>

 #include<algorithm>

 using namespace std;

int main()

{

int arr[]={2,4,6,8};

list<int>thelist;

for(int k=0;k<4;k++)

thelist.push_back(arr[k]);//заповнити список масивом

list<int>::iterator iter; //ітератор для цілочисельного списку

for(iter=thelist.begin();iter!=thelist.end();iter++)

cout<<*iter<<" "; //вивести список

cout<<endl;

getch();

return 0;

}

 

Програма 15.17

Програма просто виводить вміст контейнера thelist.

 

Ми визначаємо ітератор типу list<int>, що відповідає типу контейнера. Як і у випадку зі змінною-вказівником, до початку використання ітератора слід задати його значення. В циклі for проходить його ініціалізація значенням методу thelist.begin, це вказівник на початок контейнера. Ітератор може бути інкрементований оператором ++ для проходження по елементах, а оператором * можна здійснити його «розадресацію». Можна навіть порівнювати його з чим-небудь за допомогою оператора!= і виходити з циклу при досягненні ітератором кінця контейнера.

 

Вставка даних

Схожий код можна використати для розміщення даних серед існуючих елементів контейнера, як показано в прикладі 15.18.

#include<iostream>

#include<conio>

#include<list>

using namespace std;

int main()

{list<int>ilist(5);//порожній список для зберігання 5 елементів

list<int>::iterator it;

int data=0;

for(it=ilist.begin();it!=ilist.end();it++)

*it=data+=2;//заповнення списку даними

for(it=ilist.begin();it!=ilist.end();it++)

cout<<*it<<" ";

cout<<endl;

getch();

return 0;

}

 

Програма 15.18

 

Перший цикл заповнює контейнер цілими значеннями 2, 4, 6, 8, 10, демонструючи, що перезавантажувана операція * може стояти і зліва, і справа від знака рівності. Другий цикл призначений для виведення значень.

 

Алгоритми та ітератори

Алгоритми використовують ітератори у якості параметрів (інколи ще й значень, які повертають). Приклад 15.19 показує застосування алгоритму find() до списку. Ми знаємо, що це можливо, бо даному алгоритму потрібний лише вхідний ітератор.

#include<iostream>

#include<conio>

#include<algorithm>

#include<list>

using namespace std;

int main()

{

list<int>thelist(5);//порожній список з 5 елементів

list<int>::iterator iter;

int data=0;

for(iter=thelist.begin();iter!=thelist.end();iter++)

*iter=data+=2; //заповнення списку даними

iter=find(thelist.begin(),thelist.end(),8);//пошук 8

if(iter!=thelist.end())

cout<<"\nZnajdeno 8 \n";

else

cout<<"\nNe znajdeno 8 \n";

getch();

return 0;

}

 

Програма 15.19

 Алгоритм find() має три параметри. Перші два – це значення ітераторів, які визначають діапазон елементів, по яких може відбуватися пошук. Третій – шукане значення. Контейнер заповнюється тими самими значеннями, що й у попередньому прикладі. Потім використовується алгоритм find() для знаходження числа 8. Якщо він повертає значення ilist.end(), ми розуміємо, що досягнутий кінець контейнера і шуканий елемент не знайдений. В іншому випадку повинне повернутися число 8, це означає, що елемент знайдений.

Чи можна за допомогою значення ітератора вияснити, де саме в контейнері розміщене число 8? Схоже що так. Можна знайти зміщення відносно початку (iter=ilist.begin()). Однак це не є легальним використанням ітератора для списку, оскільки ітератор повинен бути двонапрямленим, а, отже, над ним не можна виконувати жодних арифметичних операцій. Так можна чинити з ітераторами довільного доступу, наприклад, використовуваними з векторами і чергами.

В наступному прикладі алгоритм використовує ітератори в якості аргумента. тут алгоритм copy() використовується з вектором. Користувач визначає діапазон розміщень, які повинні бути скопійовані з одного вектора в інший. Програма здійснює це копіювання. діапазон обчислюється з допомогою ітераторів.

//використання ітераторів з алгоритмом copy()

#include<iostream>

#include<conio>

#include<algorithm>

#include<vector>

using namespace std;

int main()

{

int beginRange,endRange;

int arr[]={11,13,15,17,19,21,23,25,27,29};

vector<int>v1(arr,arr+10); //ініціалізований вектор

vector<int>v2(10); //неініціалізований вектор

cout<<"Vvedit diapazon copy, napr. 2 5 ";

cin>>beginRange>>endRange;

vector<int>::iterator iter1=v1.begin()+beginRange;

vector<int>::iterator iter2=v1.begin()+endRange;

vector<int>::iterator iter3;

//копіювати дані з v1 у v2

iter3=copy(iter1,iter2,v2.begin());

//iter3 - останній скопійований запис

iter1=v2.begin();

while(iter1!=iter3)

cout<<*iter1++<<" ";

cout<<endl;

getch();

   return 0;

}

 

Програма 15.20

 

Спеціалізовані ітератори

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

Адаптери ітераторів

В STL розрізняють три варіанти модифікації звичайного ітератора. Це зворотній ітератор, ітератор вставки та ітератор неініціалізованого зберігання. Зворотній ітератор дозволяє проходити контейнер у зворотньому напрямку. Ітератор вставки створений для зміни поведінки різних алгоритмів таких як copy() та merge(), так щоб вони саме вставляли дані, а не перезаписували існуючі. Ітератор неініціалізованого зберігання дозволяє зберігати дані в ділянці пам’яті, яка ще не ініціалізована. Він використовується у досить специфічних випадках, тому ми його не розглядатимемо.

 

Зворотні ітераоти

Припустімо, нам потрібно здійснювати ітерацію по контейнеру у зворотньому порядку. В такому випадку використовують зворотні ітератори. В програмі 15.21 показане застосування цього спеціалізованого ітератора для виведення вмісту списку у зворотньому порядку.

 //зворотній ітератор

 #include<iostream>

 #include<conio>

 #include<list>

 using namespace std;

 int main()

{int arr[]={2,4,6,8,10};

list<int>thelist;

for(int j=0;j<5;j++)

thelist.push_back(arr[j]);//перенести вміст масиву в список

list<int>::reverse_iterator rewit;//зворотній ітератор

rewit=thelist.rbegin(); //реверсна ітерація

while(rewit!=thelist.rend()) //по списку

cout<<*rewit++<<" "; //з виводом на екран

cout<<endl;

getch();

   return 0;

}

 

 

Програма 15.21

При використанні зворотнього ітератора слід використовувати методи rbegin() та rend(). Цікаво, що проходження ітератора почнеться з кінця, при цьому викликається метод rbegin(). До того ж, значення ітератора потрібно інкрементувати при русі від елемента до елемента. При використанні reverse_ iterator ми рухаємося від rbegin() до rend(), інкрементується ітератор.

 

Ітератори вставки

Деякі алгоритми, наприклад, copy(), дуже люблять перезаписувати існуючі дані в контейнері призначення. Наприклад, так відбувається в програмі 15.22. В ній копіюється вміст однієї черги з двостороннім доступом в іншу.

#include<iostream>

#include<conio>

#include<deque>

#include<algorithm>

using namespace std;

int main()

{int arr1[]={1,3,5,7,9};

int arr2[]={2,4,6,8,10};

deque<int>d1;

deque<int>d2;

for(int j=0;j<5;j++)

{d1.push_back(arr1[j]);

 d2.push_back(arr2[j]);

}

copy(d1.begin(),d1.end(),d2.begin());

for(int k=0;k<d2.size();k++)

cout<<d2[k]<<" ";

cout<<endl;

getch();

   return 0;

}

 

Програма 15.22

В результаті виконання програми вміст d2 заміняється вмістом d1. Часто саме це й вимагається за логікою роботи програми, але інколи було б краще, коли б алгоритм copy() не перезаписував, а вставляв дані в контейнер. Такої поведінки алгоритму можна добитися за допомогою ітератора вставки. В нього є три цікаві інструменти:

• back_inserter, вставляє нові елементи в кінець

• front_inserter, вставляє нові елементи в початок

• inserter, вставляє елементи у вказане місце

Програма 15.23 показує, як здійснювати вставку в кінець контейнера.

//черги та ітератор вставки

#include<iostream>

#include<conio>

#include<deque>

#include<algorithm>

using namespace std;

int main()

{

int arr1[]={1,3,5,7,9};

int arr2[]={2,4,6};

deque<int>d1;

deque<int>d2;

for(int i=0;i<5;i++)

d1.push_back(arr1[i]);

for(int j=0;j<3;j++)

d2.push_back(arr2[j]);

//копіювати d1 в кінець d2

copy(d1.begin(),d1.end(),back_inserter(d2));

cout<<"\nd2: ";

for(int k=0;k<d2.size();k++)

cout<<d2[k]<<" ";

cout<<endl;

getch();

return 0;

}

 

Програма 15.23

Для вставки нових елементів в кінець використовується метод push_back(). При цьому нові елементи з вихідного контейнера d1 вставляються в кінець d2, після відповідних елементів. Контейнер d1 залишається без змін.

Якщо б ми вказали в програмі, що елементи слід вставляти в початок:

copy(d1.begin(),d1.end(),front_inserter(d2));

то нові елементи розмістилися б перед існуючими. Механізм, який стоїть за цим – це просто метод push_front(), який вставляє елементи в початок і «перевертає» їх порядок. Можна вставляти дані в довільне місце контейнера, використовуючи версію inserter ітератора. Наприклад, вставимо нові дані в початок d2:

copy(d1.begin(),d1.end(),inserter(d2,d2.begin()));

Першим параметорм inserter є ім’я контейнера, в який потрібно переносити елементи, другим – ітератор, що вказує позицію, починаючи з якої повинні вставлятися дані. Оскільки inserter використовує insert(), то порядок елементів не зміниться. Змінюючи другий параметр inserter, ми можемо вказати довільне місце контейнера.

Звернемо увагу на те, що front_inserter не може використовуватися з векторами, оскільки в них відсутній метод push_front(), доступ можливий лише до кінця такого контейнера.

 

Потокові ітератори

Потокові ітератори дозволяють інтерпретувати файли і пристрої вводу/виводу (потоки cin і cout), як ітератори. Отже, можна використовувати файли і пристрої вводу/виводу в якості параметрів алгоритмів.

Основне призначення вхідних і вихідних ітераторів – саме підтримка класів потокових ітераторів. З їхньою допомогою можна здійснювати застосування відповідних класів напряму до потоків вводу-виводу.

Існують два потокові ітератори: ostream_iterator та istream_iterator. Ми обмежимося розглядом першого з них.

 

Клас ostream_iterator

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

 

//демонстрація ostream_iterator

#include<iostream>

#include<conio>

#include<algorithm>

#include<list>

using namespace std;

int main()

{int arr[]={10,20,30,40,50};

list<int>thelist;

for(int j=0;j<5;j++)

thelist.push_back(arr[j]);//перевести масив у список

ostream_iterator<int>ositer(cout,", ");//ітератор ostream

cout<<"\nVmist spysku:";

copy(thelist.begin(),thelist.end(),ositer);//вивід списку

cout<<endl;

getch();

    return 0;

}

 

Програма 15.24

Ми визначаємо ітератор ostream для читання значень типу int. Двома параметрами конструктора є потік, в який записуватимуться значення, і рядок, що виводитиметься після кожного з них. Значенням потоку звичайно є ім’я файлу або cout, в даному випадку це cout. При записуванні в цей потік може використовуватися рядок-розділювач, що складається з довільних символів. Алгоритм copy() копіює вміст списку в потік cout. Ітератор вихідного потоку використовується в якості його третього аргументу і є іменем об’єкту призначення.

В програмі 15.25 показано, як використовувати цей підхід для запису вмісту контейнера в файл.

//демонстрація роботи ostream_iterator з файлами

#include<fstream>

#include<conio>

#include<algorithm>

#include<list>

using namespace std;

int main()

{

int arr[]={11,21,31,41,51};

list<int>thelist;

for(int j=0;j<5;j++)

thelist.push_back(arr[j]);

ofstream outfile("iter.dat");//створення файлового обєкту

ostream_iterator<int>ositer(outfile," ");//ітератор

//записати список в файл

copy(thelist.begin(),thelist.end(),ositer);

getch();

   return 0;

}

 

Програма 15.25

 Необхідно визначити файловий об’єкт класу ofstream та асоціювати його з конкретним файлом (в даному випадку з файлом iter.dat). При записуванні в файл між елементами вставляємо зручні розділювачі.

Виведення результату на екран в цій програмі не використовується, але ми можемо будь-яким текстовим редактором прочитати вміст файлу iter.dat.

 

Асоціативні контейнери

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

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

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

Дві основні категорії асоціативних контейнерів STL – це множини та відображення.

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

В множинах, як і у відображеннях, може зберігатися тільки один екземпляр кожного ключа. А кожному ключу, в свою чергу, відповідає унікальне значення. Такий підхід використовується в словниках, коли кожному слову відповідає лише одна стаття. Але в STL є спосіб обійти це обмеження. Мультимножини та мультивідображення аналогічні до споріднених контейнерів, але в них одному ключу може відповідати кілька значень.

Асоціативні контейнери мають кілька спільних методів з іншими контейнерами. Але даякі алгоритми, такі як lower_bound() та equal_range(), характерні лише для них. Крім того, деякі методи не можуть застосовуватися до асоціативних контейнерів. Серед них – сімейство методів проштовхування і виштовхування (push_back() та ін.). Дійсно, немає особливого сенсу в їх застосуванні до даної категорії контейнерів, оскільки все одно елементи повинні проштовхуватися і виштовхуватися в певному порядку, але не в кінець чи початок контейнера.

 

Множини і мультимножини

Множини часто використовують для збереження об’єктів класів користувачів. Але можна зберігати також об’єкти стандартних класів.

В програмі 15.28 продемонстрована множина, яка зберігає об’єкти класу string.

#include<iostream>

#include<set>

#include<string>

#include<conio>

using namespace std;

int main()

{string names[]={"Jane","Mary","Anne","Katy","Ruby"};

set<string,less<string> >nameSet(names,names+5);

set<string,less<string> >::iterator iter;

nameSet.insert("Yvette");

nameSet.insert("Rose");

nameSet.insert("Jane");//вставка елемента

nameSet.erase("Mary"); //видалення елемента

cout<<"\nRozmir="<<nameSet.size()<<endl;

iter=nameSet.begin();

while(iter!=nameSet.end())

cout<<*iter++<<endl;

string searchName;

cout<<"\nVvedit shukane imja: ";

cin>>searchName;

iter=nameSet.find(searchName);

if(iter==nameSet.end())

cout<<"Imja "<<searchName<<" vidsutne";

else

cout<<"Imja "<<*iter<<" najavne ";

cout<<endl;

getch();

   return 0;

}

Програма 15.28

Для визначення множини необхідно вказати тип збережених в ній об’єктів. В нашому випадку це об’єкти класу string. До того ж, необхідно вказати функціональний об’єкт, який використовуватиметься для впорядкування елементів множини. тут ми використали less<>, застосовуючи його до рядкових об’єктів.

Як бачимо, множина має інтерфейс, схожий на інші контейнери STL. Ми можемо ініціалізувати множину масивом, вставляти дані методом insert(), виводити їх за допомогою ітераторів.

Для знаходження елементів ми використали метод find() (Послідовні контейнери мають однойменний алгоритм).

Основною перевагою асоціативних контейнерів порівняно з послідовними є швидкість пошуку.

Розглянемо досит важливу пару методів, які можна використовувати лише з асоціативними контейнерами: lower_bound та upper_bound().

//тестування роботи з діапазонами в множинах

#include<iostream>

#include<conio>

#include<set>

#include<string>

using namespace std;

int main()

{set<string, less<string> > organic;

set<string, less<string> >::iterator iter;

organic.insert("Curine");

organic.insert("Curarine");

organic.insert("Melanin");

organic.insert("Pherol");

organic.insert("Cianimid");

organic.insert("Aphrodine");

iter=organic.begin(); //виведення множини

while(iter!=organic.end())

cout<<*iter++<<'\n';

string lower,upper;//виведення значень з діапазону

cout<<"\nVvedit diapazon napr. A Z";

cin>>lower>>upper;

iter=organic.lower_bound(lower);

while(iter!=organic.upper_bound(upper))

cout<<*iter++<<'\n';

getch();

   return 0;

}

 

Програма 15.29

Метод lower_bound() бере в якості аргументу значення того ж типу, що й ключ. Він повертає ітератор, що вазує на перший запис множинип, значення якого не менше за аргумент (що означає «не менше» в кожному конкретному випадку використовується конкретним функціональним об’єктом, що використовується при визначенні множини). Функція upper_bound() повертає ітератор, що вказує на елемент, значення якого більше, ніж аргумент. Обидві ці функції дозволяють задавати діапазон значинь в контейнері.