Функції користувача замість функціональних об’єктів

Функціональні об’єкти можуть працювати тільки з базовими класами С++ і з класами, для яких визначені відповідні оператори (<,>,+,-,==) Це не завжди зручно, оскільки інколи доводиться працювати з типами даних, для яких така умова не виконується. В такому випадку можна визначити власну функцію користувача для функціонального об’єкту. Наприклад, оператор < не визначений для звичайних рядків char*, але можна написати функцію, що використовує порівняння і використовувати її адресу (ім’я)  замість функціонального об’єкту. Програма 15.7 показує, як просортувати масив рядків char*.

#include<iostream>

#include<conio>

#include<string>

#include<algorithm>

using namespace std;

char* names[]={"Sergij","Andrij","Ulana","Tetana","Ivan","Ivanna"};

bool alpha_comp(char*,char*); //оголошення

int main()

{ sort(names,names+6,alpha_comp); //сортування рядків

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

cout<<names[j]<<endl;

getch();

   return 0;

}

bool alpha_comp(char* s1,char* s2)

{

return(strcmp(s1,s2)<0?true:false);

}

Програма 15.7

 

Третім параметром алгоритму sort() в даному випадку є адреса функції alpha_comp(), яка порівнює два рядки типу char* і повертає true чи false залежно від того, чи правильно для них виконується лексиграфічне порівняння.

В даному прикладі можна було обійтися без функції користувача, замінивши рядки типу char* рядками типу string. Для типу string є вбудовані функціональні об’єкти такі як less<>() i greater<>().

 

Додавання _if до аргументів

Деякі аргументи мають версії з закінченням _if. Їм потрібний додатковий параметр, який називається предикатом і є функціональним об’єктом чи функцією. Наприклад, алгоритм find() знаходить всі елементи, рівні вказаному значенню. Можна написати функцію, яка працює з алгоритмом find_if() і знаходить елементи з якимись додатковими параметрами.

В прикладі 15.8 використовуються об’єкти класу string. Алгоритму find_if() передається функція користувача isDon, щоб можна було знайти перший рядок в масиві, що має значення Ivan

#include<iostream>

#include<conio>

#include<string>

#include<algorithm>

using namespace std;

bool isDon(string name)

{return name==”Ivan”;}

 

string names[]={“Sergij”,”Andrij”,”Ulana”,”Tetana”,”Ivan”,”Ivanna”};

int main()

{string* ptr;

ptr=find_if(names,names+5,isDon);

if(ptr==names+5)

cout<<”Ivana nemae v spysku\n”;

else

cout<<”Ivan zapysanyj v pozycii “

<<(ptr-names)

<<” v spysku \n”;

getch();

   return 0;

}

 

Програма 15.8

 

Адреса функції isDon() – третій елемент алгоритму find_if(), а перші два, як звичайно, задають діапазон пошуку від початку до «післяостаннього» елементу масиву.

Алгоритм find_if() застосовує функцію is_Don() до кожного елементу з діапазону. Якщо is_Don() повертає true для якого-небудь елемента, то find_if() повертає значення ітератора для цього елементу. В протилежному випадку повертається вказівник на адресу «Післяостаннього» елементу масиву.

_if-версії є також в інших алгоритмів, наприклад, count(), replace(), remove().

 

Алгоритм for_each()

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

В прикладі 15.9 for_each() використовується для переведення всіх значень масиву з дюймів у сантиметри і виведення їх на екран. Ми пишемо функцію in_to_cm(), яка просто множить значення на 2.54, і передаємо адресу цієї функції в якості третього аргументу алгоритму.

#include<iostream>

#include<conio>

#include<algorithm>

using namespace std;

void in_to_cm(double); //оголошення

int main()

{double inches[]={3.5,6.2,1.0,12.75,4.33};

for_each(inches,inches+5,in_to_cm);

cout<<endl;

getch();

   return 0;

}

 

void in_to_cm(double in)

{cout<<(in*2.54)<<' ';}

Програма 15.9

Результати роботи програми виглядають так:

Алгоритм transform()

Цей алгоритм теж виконує якусь дію з кожним елементом трансформера, але ще й поміщає результат в інший або той сам контейнер. Функція користувача визначає, що саме робити з даними, причому тип повернутого нею результату повинен відповідати типу цільового контейнера. Приклад 15.10 аналогічний до попереднього, але замість виводу на екран функція in_to_cm() виводить значення сантиметрів в новий масив centi[], а потім головна програма виводить вміст цього масиву.

#include<iostream>

#include<conio>

#include<algorithm>

using namespace std;

 

int main()

{double inches[]={3.5,6.2,1.0,12.75,4.33};

double centi[5];

double in_to_cm(double); //оголошення

transform(inches,inches+5,centi,in_to_cm);

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

cout<<centi[j]<<' ';

cout<<endl;

getch();

   return 0;

}

 

double in_to_cm(double in)

{return(in*2.54);}

Програма 15.10

Ми розглянули деякі алгоритми STL. Є ще багато інших, але тепер зрозуміло, як вони працюють і як з ними поводитися.

 

Послідовні контейнери

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

Слід пам’ятати, що різні види контейнерів використовують методи з одинаковими іменами і характеристиками, тому, наприклад, метод push_back() для векторів працюватиме також зі списками й чергами.

 

Вектори

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

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

 

Методи push_back(), size() i operator[]

У програмі 15.11 приведено приклад найзагальніших векторних операцій

#include<iostream>

#include<vector>

#include<conio>

using namespace std;

int main()

{vector<int> v; //створити вектор типу int

v.push_back(10);

v.push_back(11);

v.push_back(12);

v.push_back(13);

v[0]=20;

v[3]=23;

for(int j=0;j<v.size();j++)

 cout<<v[j]<<' ';

 cout<<endl;

getch();

   return 0;

}

 

 

Програма 15.11

Для створення вектора v використовується штатний конструктор вектора без параметру. Як з будь-якими контейнерами STL, для задання типу змінних, які будуть зберігатися у векторі, використовується шаблонний формат, в даному випадку це тип int. Ми не визначаємо розмір контейнера, тому спочатку він рівний 0.

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

Як тільки у векторі з’являються які-небудь дані, до них відразу може бути одержаний доступ за допомогою перезавантаженого оператора []. Як бачимо, ми дістаємо доступ до довільного елементу вектора і можемо напряму працювати з ним.

v[0]=20;

v[3]=23;

Результат роботи програми виглядає так:

 

Метод size() повертає поточне число елементів, що містяться в контейнері. Для даної програми це 4. Це значення використовується в циклі for для виводу значень вектора на екран.

Ще один метод, max_size(), повертає максимальний розмір, до якого може бути розширений контейнер. Це число залежить від типу збережуваних в ньому даних.

 

Методи swap(), empty(), back() та pop_back()

Наступна програма 15.12 демонструє ще кілька методів та векторів.

#include<iostream>

#include<vector>

#include<conio>

using namespace std;

int main()

{ double arr[]={1.1,2.2,3.3,4.4};

vector<double>v1(arr,arr+4);

vector<double>v2(4);

v1.swap(v2);

while(!v2.empty()) //поки вектор не порожній

{cout<<v2.back()<<' ';//вивести останній елемент

v2.pop_back();//видалити його

}

cout<<endl;

getch();

   return 0;

}

 

Програма 15.12

В цій програмі ми використали два нові конструктори векторів. Перший

vector<double>v1(arr,arr+4);

ініціалізує вектор v1 значеннями звичайного масиву С++, переданого йому в якості аргументу. Аргументами цього конструктора є вказівники на початок масиву і на елемент «після останнього».

В другому конструкторі

vector<double>v2(4);

вектор v2 ініціалізується установкою його розміру. Ми встановили його рівним 4. Але значення самого вектора при ініціалізації не передається. Обидва вектори містять дані типу double.

Метод swap() обмінює дані одного вектора на дані іншого, при цьому порядок елементів не змінюється. Оператор

v1.swap(v2);

міняє вектор v2 на v1.

Метод back() повертає значення останнього елемента вектора. Ми виводимо його за допомогою cout(). Метод pop_back() видаляє останній елемент вектора.

Дещо дивно, що pop_back() тільки видаляє останній елемент вектора, але не повертає його значення, як pop() при роботі зі стеком. Тому слід використовувати pop_back() i back() в парі.

Деякі методи, наприклад, swap(), існують і у вигляді алгоритмів. В таких випадках краще вибрати метод. Робота з методом для конкретного контейнера звичайно є ефективнішою. Інколи є сенс використовувати і те і інше.. Наприклад, такий підхід можна використовувати для обміну елементів двох контейнерів різних типів.

 

Методи insert() та erase()

Ці методи, відповідно, вставляють і видаляють дані при звертанні до довільної позиції контейнера. Їх не рекомендується використовувати з векторами, оскільки при кожній вставці чи видаленні доводиться перекроювати всю структуру – розширювати чи стискати вектор. Тим не менше, коли швидкість не відіграє особливої ролі, використовувати ці методи можна і потрібно. Наступний приклад показує, як це робиться.

#include<iostream>

#include<vector>

#include <conio>

using namespace std;

int main()

{int arr[]={100,110,120,130};

int j;

vector<int>v(arr,arr+4); //ініціалізувати вектор масивом

cout<<"\nPered vstavkou: ";

for(j=0;j<v.size();j++)

cout<<v[j]<<' ';

v.insert(v.begin()+2,115); //вставити 115 в позицію 2

cout<<"\nPisla vstavky: ";

for(j=0;j<v.size();j++)

cout<<v[j]<<' ';

v.erase(v.begin()+2); //видалити елемент з 2-ї позиції

cout<<"\nPisla vydalenna: ";

for(j=0;j<v.size();j++)

cout<<v[j]<<' ';

cout<<endl;

getch();

   return 0;

}

 

Програма 15.13

Метод insert() в даній версії має 2 параметри: майбутнє розміщення нового елементу в контейнері і значення елемента. Додаємо 2 позиції до результату виконання методу begin(), щоб перейти до елемента №2 (третій елемент в контейнері, рахуючи від 0). Елементи від точки вставки до кінця контейнера зсовуються, щоб було місце для розміщення вставлювання. Розмір контейнера автоматично збільшується на одиницю.

Метод erase() видаляє елемент з вказаної позиції. Решта елементів зсовується, розмір контейнера зменшується на одиницю.

Результат роботи програми:

 

Списки

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

 

Методи push_front(), front() і pop_front()

Програма 15.14 демонструє вставку, читання і видобування даних

#include<iostream>

#include<conio>

#include<list>

using namespace std;

int main()

{list <int> ilist;

ilist.push_back(30);//вставка елементу в кінець

ilist.push_back(40);

ilist.push_front(20);//вставка елементу в кінець

ilist.push_front(10);

int size=ilist.size();//число елементів

cout<<"size="<<size<<endl;

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

{cout<<ilist.front()<<" "; //читати дані

                       //з початку

ilist.pop_front();//видобування даних з початку

}

cout<<endl;

getch();

   return 0;

}

 

Програма 15.14

Результат роботи програми

В ході роботи програми ми вставляємо дані в кінець і початок списку таким чином, щоб при виведенні на екран і видаленні з початку зберігався такий їх порядок: 10 20 30 40

Пам’ятаймо, що довільний доступ до елементів списку використовувати небажано, оскільки він занадто повільний для нормальної обробки даних. Тому оператор [] для списків навіть не визначений. Якщо б довільний доступ був реалізований, цьому оператору довелося б проходити весь список, переміщаючись від посилання до посилання аж до досягнення потрібного елементу. Це була б дуже повільна операція. Якщо нам потрібний контейнер з довільним доступом, то краще використовувати вектор або черги з двостороннім доступом.

Списки доцільно використовувати при частих опраціях вставки і видалення десь в середині списку. При цих операціях використовувати вектори або черги нелогічно, оскільки всі елементи над точкою вставки чи видалення повинні бути зсунуті. Що ж стосується списків, то при цих операціях достатньо буде поміняти значення всього кількох вказівників.