Створення класу зв’язних списків за допомогою шаблону

Розглянемо ще один приклад, в якому шаблони допомагають при створенні класів-сховищ даних. Для цього модифікуємо програму, що описує, створює і зберігає зв’язні списки. Будемо добиватися, щоб не тільки клас linklist був перероблений в шаблон, але щоб і структура link, яка реально зберігає кожен елемент даних, теж стала шаблоном.

 //шаблон звязних списків

 #include<iostream>

 #include<conio.h>

 using namespace std;

 ///////////

 template<class TYPE>

struct link

{TYPE data;

link* next;

};

 

/////////

template<class TYPE>

class linklist

{ private:

link<TYPE>*first;

public:

linklist()

{first=NULL;}

 

void additem(TYPE d);

void display();

};

 

/////////

template<class TYPE>

void linklist<TYPE>::additem(TYPE d)

{link<TYPE>* newlink=new link<TYPE>;

newlink->data=d;

newlink->next=first;

first=newlink;

}

 

template<class TYPE>

void linklist<TYPE>::display()

{

link<TYPE>* current=first;

while(current!=NULL)

{cout<<endl<<current->data;

current=current->next;

}

}

/////////

int main()

{

linklist<double> ld;

ld.additem(101.5);

ld.additem(202.5);

ld.additem(303.7);

ld.display();

 

linklist<char>lch;

 lch.additem('a');

 lch.additem('b');

 lch.additem('c');

 lch.display();

 cout<<endl;

 getch();

   return 0;

}

 

Програма 14.5

В main() ми визначаємо два зв’язних списки: один — для зберігання чисел типу doublr, інший — для зберігання символів (типу char). В кожен з них заносимо по три значення за допомогою методу additem() і виводимо всі значення на екран за допомогою display().

І клас linklist, і структура link використовуються шаблонним аргументом TYPE для підстановки довільного типу даних. Таким чином, не тільки linklist, але й link повинні бути саме шаблонами і починатися з рядка:

template<class TYPE>

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

Як і раніше, необхідно слідкувати за найменуванням класу (і структури) в різних частинах програми. Всередині його власної специфікації ми використовуємо тільки найменування класу (чи структури). У зовнішніх методах ми пишемо ім’я класу, а за ним — ім’я шаблонного аргументу

linklist<TYPE>

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

linklist<double> ld;

 

Зберігання типів користувача

Досі нам доводилося зберігати за допомогою шаблонних класів тільки базові типи даних. Тепер спробуємо виконати ті самі дії для типів користувача. Раніше ми створювали тип employce – працівників.

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

//звязний список з використанням шаблону

//тип користувача

#include<iostream>

#include<conio.h>

using namespace std;

const int LEN=80;

//////////

class employce

{private:

char name[LEN];

unsigned long number;

public:

friend istream& operator>>(istream& s,employce& e);

friend ostream& operator<<(ostream& s,employce& e);

};

////////////

istream& operator>>(istream& s,employce& e)

{cout<<"\n PIP: ";cin>>e.name;

cout<<" Nomer: ";cin>>e.number;

return s;

}

 

ostream& operator<<(ostream& s,employce& e)

{cout<<"\n Name: "<<e.name;

 cout<<"\n Number: "<<e.number;

 return s;

 }

///////////////

template<class TYPE>

Struct link

{

 TYPE data;

 link* next;

};

//////////////

template<class TYPE>

Class linklist

{

private:

link<TYPE>* first;

public:

Linklist()

{first=NULL;}

void additem(TYPE d);

void display();

};

/////////////

template<class TYPE>

void linklist<TYPE>::additem(TYPE d)

{link<TYPE>* newlink=new link<TYPE>;

newlink->data=d;

newlink->next=first;

first=newlink;

}

///////////

template<class TYPE>

void linklist<TYPE>::display()

{link<TYPE>* current=first;

while(current!=NULL)

{cout<<endl<<current->data;

current=current->next;

}

}

///////////

int main()

{ linklist<employce>lemp;

employce emptemp;

char ans;

do

{cin>>emptemp;

lemp.additem(emptemp);

cout<<"\nContinue (y/n)? ";

cin>>ans;

}while(ans!='n');

lemp.display();

cout<<endl;

getch();

   return 0;

}

 

Програма 14.6

 

В цій програмі ми перезавантажили оператори видобування і вставки:

>>  <<

Дані, одержані в результаті видобування з потоку, збережемо у тимчасовому об’єкті emptemp, перш ніж додавати їх до зв’язного списку.

Звернемо увагу на те, що клас linklist не потрібно ніяк модифікувати для того, щоб він зберігав об’єкти типу користувача.

Щоб визначити,, змінні якого типу можуть зберігатися в шаблонному класі, потрібно зрозуміти, які операції виконуються в його методах. Якщо методи класу використовують операції << (вставки) i >> (видобування), то треба перевірити, чи визначені вони по відношенню до даних нашого типу. Можливо, їх потрібно перезавантажити.

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

 

Підсумок

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

 

Питання по темі

1. Шаблони дозволяють зручним способом створювати сімейства:

а) змінних

б) функцій

в) класів

г) програм

 

2. Шаблонний аргумент завжди починається з ключового слова

а) class

б) function

в) templateclass

 

3. Чи істинним є твердження: шаблони автоматично створюють різні версії класу залежно від даних, введених користувачем?

а) так

б) ні, вони створюються в процесі компіляції

4. Шаблонний клас:

а) створюється для того, щоб працювати з різними контейнерами

б) працює з різними типами даних

в) генерує ідентичні об’єкти

г) генерує класи з різним числом методів

 

5. Чи може шаблон мати кілька аргументів?

а) так

б) ні

 

6. Реальний код шаблонної функції генерується при:

а) оголошенні функції у вихідному коді

б) визначенні функції у вихідному коді

в) виклику функції у вихідному коді

г) запуску функції під час роботи програми

 

7. Шаблони часто використовуються з класами, які:

а) зберігають дані

б) здійснюють ввід-вивід даних

в) складаються з даних різного типу

 

 Тема 15. Стандартна бібліотека шаблонів STL

 

Вступ

Вступ в STL

Контейнери

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

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

Методи

Адаптери контейнерів

Алгоритми

Ітератори

Алгоритми

Алгоритм find()

Алгоритм count()

Алгоритм sort()

Алгоритм search()

Алгоритм merge()

Функціональні об’єкти

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

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

Алгоритм for_each()

Алгоритм transform()

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

Вектори

Списки

Черги з двостороннім доступом

Ітератори

Ітератори як інтелектуальні вказівники

Відповідність алгоритмів контейнерам

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

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

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

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

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

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

Відображення та мультивідображення

Асоціативний масив

Збереження об’єктів користувача

Список об’єктів класу person

Функціональні об’єкти

Напередвизначені функціональні об’єкти

Створення власних функціональних об’єктів

Підсумок

Питання по темі

 

Вступ

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

Класи С++ являють собою чудовий механізм для створення бібліотеки структур даних. До стандарту С++ входить власна вбудована бібліотека класів-контейнерів. Вона називається Стандартною бібліотекою шаблонів (скорочено STL). STL є частиною Стандартної бібліотеки класів С++, її автори – Олександр Степанов і Менг Лі.

 

Вступ в STL

STL містить кілька основних сутностей. Три найважливіші з них – це контейнери, алгоритми та ітератори.

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

Під алгоритмами в STL розуміють процедури, що застосовуються до контейнерів для обробки їх даних у різні способи. Наприклад, є алгоритми сортування, копіювання, пошуку та об’єднання. Алгоритми представлені у STL у вигляді шаблонних класів, однак вони не є методами класів-контейнерів. Навпаки, це цілком незалежні функції. Однією з найпривабливіших рис STL є універсальність її алгоритмів. Їх можна використовувати не лише в об’єктах класів-контейнерів, а й у масивах і навіть у власних контейнерах. Тим не менше, контейнери містять і методи для розв’язку деяких специфічних задач.

Ітератори – це узагальнення концепції вказівників: вони посилаються на елементи контейнера. Їх можна інкрементувати як звичайні вказівники, і вони будуть послідовно посилатися на всі елементи контейнера. Ітератори – це ключова частина STL, оскільки вони зв’язують алгоритми з контейнерами. Їх можна уявляти собі у вигляді кабеля, що зв’язує комп’ютер з периферією.

На рисунку 10.1 показані три компоненти STL. Далі ми обговоримо їх детальніше.

Рисунок 15.1

 

 

Контейнери

Як вже було сказано, контейнери являють собою різноманітні структури для збереження даних. При цьому неістотно, які саме дані зберігаються: базові типи int, float, char, чи об’єкти класів. STL включає в себе 7 основних типів контейнерів і ще три похідні типи. Навіщо нам стільки контейнерів і чому не можна обійтися масивом у всіх випадках, коли потрібно зберігати дані? Відповідь така: це неефективно. Працювати з масивом у багатьох випадках і складно, і занадто довго.

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

 

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

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

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

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

Третім представником послідовних контейнерів є черга з двостороннім доступом. Це комбінація стеку та звичайної черги. Стек організований за принципом «останнім ввійшов, першим вийшов», черга – навпаки: «першим ввійшов – першим вийшов». Черга з двостороннім доступом використовує комбінований порядок обміну даними. І вносити зміни в чергу з двостороннім доступом, і виходити з неї можна з двох сторін. Це доволі гнучкий інструмент, він цінний не лише сам собою, а також як база для стеку черг.

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

Таблиця 15.1

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

Контейнер	Характеристика	Плюси/мінуси
Звичайний масив	Фіксований розмір	Швидкісний випадковий доступ (за індексом) Повільна вставка або вилучення даних з середини Розмір не може бути змінений під час роботи програми
Вектор	Перерозподілюваний розширюваний масив	Швидкісний випадковий доступ (за індексом) Повільна вставка або вилучення даних з середини Швидкісна вставка або вилучення даних з хвоста
Список	Аналогічний до зв’язного списку	Швидкісна вставка або вилучення даних з будь-якого місця Швидкий доступ до обох кінців Повільний випадковий доступ
Черга з двостороннім доступом	Як вектор, але доступ з обох сторін	Швидкісний випадковий доступ. Повільна вставка або вилучення даних з середини. Швидкісна вставка або вилучення даних з хвоста або голови

 

.Реалізація на практиці контейнера STL не становить особливих труднощів. По-перше, треба включити в програму відповідний заголовочний файл. Передача інформації про те, які типи об’ктів будуть зберігатися, відбувається у вигляді передачі параметра в шаблон. Наприклад:

vector <int> avect; //створення вектора цілих чисел

або

list<airtime> atime_list; //створити список типу atime

В STL не потрібно специфікувати розміри контейнера. Вони самі турбуються про розміщення своїх даних в пам’яті.

 

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

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

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

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

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

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

В таблиці 10.2 зібрані всі асоціативні контейнери, що зберігаються в STL.

 

Таблиця 15.2

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

Контейнер	Характеристики
Множина	Зберігає тільки ключові об’єкти. Кожному значенню відповідає один ключ
Мультимножина	Зберігає тільки ключові об’єкти. Одному значенню може відповідати кілька ключів
Відображення	Асоціює ключовий об’єкт з об’єктом, що зберігає значення (цільовим). Одному значенню відповідає один ключ
Мультивідображення	Асоціює ключовий об’єкт з об’єктом, що зберігає значення (цільовим). Одному значенню може відповідати кілька ключів.

 

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

set <int> intSet; // створює множину значень int

або

multiset <employee> machinists; // створює мультимножину значень типу employee

 

Методи

Алгоритми – це робочі інструменти STL, що виконують складні операції типу сортування і пошуку. Однак для виконання простіших операцій, специфічних для конкретного контейнера, потрібні методи.

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

Таблиця 15.3

Деякі методи, спільні для всіх контейнерів

Ім’я	Призначення
size()	Повертає число елементів у контейнері
empty()	Повертає true, якщо контейнер порожній
max_size	Повертає максимально допустимий розмір контейнера
begin()	Повертає ітератор на початок контейнера (ітерації будуть відбуватися в прямому напрямку)
end()	Повертає ітератор на останню позицію в контейнері (ітерації в прямому напрямку закінчені)
rbegin()	Повертає ітератор на кінець контейнера (ітерації будуть відбуватися в зворотньому напрямку)
rend()	Повертає ітератор на початок контейнера (ітерації у зворотньому напрямку закінчені)

 

Адаптери контейнерів

Спеціалізовані контейнери можна створювати з базових за допомогою конструкції, що називається адаптером контейнера. Вони мають простіший інтерфейс, ніж звичайні контейнери. Спеціалізовані контейнери, реалізовані у STL – це стеки, черги і пріоритетні черги. Як відомо, для стеку характерний доступ тільки з одного кінця. Черга використовує для проштовхування один кінець, для виштовхування – інший. В пріоритетній ерзі дані проштовхуються спереду в довільному порядку, а виштовхуються у строгій відповідності з величиною збережуваного значення. Таким чином, пріоритетна черга автоматично сортує інформацію, яка в ній зберігається.

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

Таблиця 15.4

Контейнери, що реалізуються за допомогою адаптерів

Контейнер	Реалізація	Характеристики
Стек	Реалізується як вектор, список або черга з двостороннім доступом	Проштовхування і виштовхування даних тільки з одного кінця
Черга	Реалізується як список або черга з двостороннім доступом	Проштовхування з одного кінця, виштовхування з іншого
Пріоритетна черга	Реалізується як вектор або черга з двостороннім доступом	Проштовхування з одного кінця у випадковому порядку, виштовхування – впорядковане, з іншого кінця

Для практичного використання цих класів необхідно використовувати наче шаблон тв шаблоні. Наприклад, нехай маємо об’єкт класу «стек», що містить значення int, породжений класом «черга з двостороннім доступом» (deque)

stack< deque<int> >astak

Щоб компілятор не видавав повідомлення про помилку, інтерпретуючи >> як оператор, слід обов’язково робити пропуск між двома закриваючими кутовими дужками.

 

Алгоритми

Алгоритм – це функція, що здійснює певні дії над елементами контейнера. Як вже згадувалося, алгоритми в STL не є методами класів і навіть не є дружніми функціями по відношенню до контейнерів. В теперішньому стандарті мови – це незалежні шаблонні функції. Їх можна використовувати як при роботі зі звичайними масивами С++, так і з нашими власними класами-контейнерами (припускається, що у склад включені деякі базові функції).

В таблиці 10.5 показані деякі популярні алгоритми.

Таблиця 15.5

Деякі типові алгоритми STL

Алгоритм	Призначення
find	Повертає перший елемент з вказаним значенням
count	Рахує кількість елементів, що мають вказане значення
equal	Порівнює вміст двох контейнерів і повертає true, якщо всі відповідні елементи еквівалентні
search	Шукає послідовність значень в одному контейнері, яка відповідає такій же послідовності в іншому
copy	Копіює послідовність значень з одного контейнера в інший
swap	Обмінює значення, що зберігаються в різних місцях
iter_swap	Обмінює послідовність значень, що зберігаються в різних місцях
sort	Сортує значення у вказаному порядку
merge	Комбінує два сортовані діапазони значень для одержання найбільшого діапазону
accumulate	Повертає суму елементів у заданому діапазоні
for_each	Виконує задану функцію для кожного елемента контейнера

 

Наприклад, алгоритм sort сортує масив:

sort(arr,arr+8);

Ітератори

Ітератори – це сутності, що нагадують вказівники. Вони використовуються для одержання доступу до окремих даних (які звичайно називаються елементами) в контейнері. Аони часто використовуються для послідовного пересування по контейнеру від елемента до елемента (цей процес називається ітерацією). Ітератори можна інкрементувати за допомогою звичайного оператора ++, після виконання якого ітератор пересунеться на наступний елемент. Розадресування здійснюється оператором *, після чого можна одержати значення елемента, на який посилається ітератор. В STL ітератор являє собою об’єкт класу iterator.

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

Двонаправлений ітератор, відповідно, може пересуватися в обох напрямках і реагує як на ++, так і на --.

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

Є два спеціалізовані типи ітеротів. Це вхідний ітератор, який може вказувати на пристрій вводу (cin чи вхідний файл) і зчитувати послідовно елементи даних в контейнер, і вихідний контейнер, який відповідно вказує на пристрій виводу (cout) чи вихідний файл і виводить елементи з контейнера.

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

 

Алгоритми

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

 

Алгоритм find()

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

#include<iostream>

#include<conio>

#include<algorithm>

using namespace std;

int arr[]={11,22,33,44,55,66,77,88};

int main()

{ int *ptr;

ptr=find(arr,arr+8,44);

cout<<"Pershyj object zi znachennam 44 v pozycii "

<<(ptr-arr+1)<<endl;

getch();

   return 0;

}

 

Програма 15.1

Заголовочні файли

До програми включений заголовочний файл ALGORITHM. В цьому файлі містяться оголошення алгоритмів STL.

 

Діапазони

Перші два аргументи оператора find визначають діапазон елементів, що переглядаються. Значення задаються ітераторами. В даному прикладі ми використали значення звичайних вказівників С++, що є окремими випадками ітераторів.

Перший параметр – це ітератор (тобто вказівник) першого значення, яке треба перевірити. Другий – ітератор останньої позиції (насправді він вказує позицію, наступну після останнього ітератора). Використовуваний при цьому синтаксис є варіацією на тему звичайного циклу for C++. Алгоритм find() звільнив нас від необхідності писати цикл for. Загалом же алгоритми заміняють собою складні і трудомісткі фрагменти програмного коду.

 

Алгоритм count()

Далі приведений приклад використовує алгоритм count(). Він підраховує, скільки елементів в контейнері мають дане значення.

#include<iostream>

#include<algorithm>

#include<conio>

using namespace std;

int arr[]={33,22,33,44,33,55,66,77};

int main()

{int n=count(arr,arr+8,33);//підрахунок к-сті входжень 33

cout<<"33 zustrichaetsa "<<n<<" raz v masyvi "<<endl;

getch();

   return 0;

}

Програма 15.2

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

 

Алгоритм sort()

Призначення цього алгоритму – сортування контейнера.

#include<iostream>

#include<algorithm>

#include<conio>

using namespace std;

int arr[]={33,22,33,44,33,55,66,77};

int main()

{sort(arr,arr+8); //сортування

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

cout<<arr[j]<<' ';

cout <<endl;

getch();

   return 0;

}

Програма 15.3

 

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

 

Алгоритм search()

Деякі алгоритми оперують одночасно двома контейнерами. Наприклад, якщо алгоритм find() шукає вказане значення в одному контейнері, алгоритм serch() шукає цілу послідовність значень, задану одним контейнером, в іншому контейнері. Приклад його використання приведено в програмі 15.4

#include<iostream>

#include<algorithm>

#include<conio>

using namespace std;

int source[]={11,44,33,11,22,33,11,22,44};

int pattern[]={11,22,33};

int main()

{ int *ptr;

ptr=search(source,source+9,pattern,pattern+3);

if(ptr==source+9)//зупинилися після останнього

cout<<"Spivpadinna ne znajdeno\n";

else

cout<<"Spivpadinna v pozycii "<<(ptr-source)<<endl;

getch();

   return 0;

}

 

Програма 15.4

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

 

Алгоритм шукає послідовність (11,12,13), задану масивом pattern, в масиві source. Якщо значення ітератора ptr опиняються за межами масиву source, виводиться відповідне повідомлення.

Параметрами алгоритму serch() і подібних на нього не зобов’язані бути контейнери одного типу. Вихідний контейнер може бути, наприклад, вектором, а маска пошуку – масивом. така універсальність є сильною стороною STL.

 

Алгоритм merge()

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

#include<iostream>

#include<conio>

#include<algorithm>

using namespace std;

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

int src2[]={1,3,5};

int dest[8];

int main()

{//обєднання src1 i src2 в dest

merge(src1,src1+5,src2,src2+3,dest);

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

cout<<dest[j]<<' ';

cout<<endl;

getch();

   return 0;

}

 

 

Програма 15.5

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

 

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

 

Функціональні об’єкти

Деяким алгоритмам в якості параметрів потрібні певні функціональні об’єкти. Функціональний об’єкт – це об’єкт шаблонного класу, в якому наявний єдиний метод: перезавантажувана операція {}. Його використання досить просте.

Нехай нам треба відсортувати масив чисел за зростанням чи спаданням. У прикладі 15.6 показано, як це робиться.

//сортування масиву double за спаданням

//використовується функціональний об'єкт greater<>()

#include<iostream>

#include<conio>

#include<algorithm>

#include<functional>

using namespace std;

double fdata[]={19.2,87.4,33.6,55.0,11.5,42.2};

int main()

{//сортування масиву double

sort(fdata,fdata+6,greater<double>());

for(int j=0;j<6;j++) //вивести відсортований масив

cout<<fdata[j]<<' ';

cout<<endl;

getch();

   return 0;

}

 

Програма 15.6

Алгоритм sort() звичайно сортує за зростанням, але використання функціонального об’єкту greater<>() в якості третього аргументу sort змінює порядок сортування

 

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