Т Е Х Н О Л О Г І Ї 1 страница

Else

Else

Endif

Endif

Endif

Endif

Endif

Endif

Endif

Endif

Endif

Endif

Endif

Endif

Else

Else

cout << "Такого слова у словнику немає.\n";

getch (); return 0;

}

Один з можливих варіантів виконання цієї програми

Введіть слово: дім

Визначення: Місце мешкання.

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

22.6. Алгоритми оброблення контейнерних даних

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

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

Табл. 22.5. Алгоритми STL

Алгоритм	Призначення
adjacent_find	Виконує пошук суміжних елементів, які співпадають усередині послідовності, і повертає ітератор для першого знайденого збігу
binary_search	Виконує двійковий пошук заданого значення усередині впорядкованої послідовності
copy	Копіює послідовність
copy_backward	Аналогічний алгоритму copy, за винятком того, що копіювання відбувається у зворотному порядку, тобто спочатку переміщаються елементи, які знаходяться у кінці послідовності
count	Повертає кількість елементів із заданим значенням у послідовності
count_if	Повертає кількість елементів, які задовольняють заданому предикату
equal	Визначає, чи однакові два діапазони
equal_range	Повертає діапазон, у який можна вставити елемент, не порушуючи порядок деякої послідовності
fill, fill_n	Заповнюють діапазон заданим значенням
find	У заданому діапазоні виконує пошук заданого значення і повертає ітератор для першого входження знайденого елемента
find_end	У заданому діапазоні виконує пошук заданої послідовності. Повертає ітератор, який відповідає кінцю шуканої послідовності
find_first_of	Виконує пошук першого елемента усередині заданої послідовності, який збігається з будь-яким елементом із заданого діапазону
find_if	У заданому діапазоні виконує пошук елемента, для якого визначений користувачем унарний предикат повертає значення true
for_each	Застосовує задану функцію до заданого діапазону елементів
generate, generate_n	Присвоюють значення, що повертаються деякою функцією-генератором, елементам із заданого діапазону
includes	Встановлює факт внесення всіх елементів однієї заданої послідовності в іншу задану послідовність
inplace_merge	Об'єднує один заданий діапазон з іншим. Обидва діапазони мають бути відсортовані у порядку зростання Після виконання алгоритму отримана послідовність сортується у порядку зростання
iter_swap	Змінює місцями значення, що адресуються ітераторами, які передаються як параметри
lexicographical_compare	Порівнює одну задану послідовність з іншою в лексикографічному порядку
lower_bound	Виконує пошук першого елемента у заданій послідовності, значення якого є не меншим від заданого значення
make_heap	Створює купу із заданої послідовності
max	Повертає максимальне з двох значень
max_element	Повертає ітератор для максимального елемента усередині заданого діапазону
merge	Об'єднує дві впорядковані послідовності, поміщаючи результат у третю послідовність
min	Повертає мінімальне з двох значень
min_element	Повертає ітератор для мінімального елемента усередині заданого діапазону
mismatch	Виконує пошук першого неспівпадання елементів у двох послідовностях і повертає ітератори для цих двох елементів
next_permutation	Створює наступну перестановку заданої послідовності
nth_element	Упорядковує задану послідовність так, щоби всі елементи, значення яких є меншим від значення Е, розміщувалися перед цим елементом, а всі елементи, значення яких є більшим від значення Е, розміщувалися після нього
partial_sort	Сортує заданий діапазон
partial_sort_copy	Сортує заданий діапазон, а потім копіює стільки елементів, скільки може поміститися в остаточну послідовність
partition	Сортує задану послідовність так, щоб всі елементи, для яких заданий предикат повертає значення true, розміщувалися перед елементами, для яких цей предикат повертає значення false
pop_heap	Змінює місцями перший і передостанній елементи заданого діапазону, а потім перебудовує купу
prev_permutation	Створює попередню перестановку послідовності
push_heap	Поміщає елемент у кінець купи
random_shuffie	Додає випадковий характер заданій послідовності
remove, remove_if, remove_copy, remove_copy_if	Видаляють елементи із заданого діапазону
replace, replace_copy, replace_if, replace_copy_if	Замінюють задані елементи з діапазону іншими елементами
reverse, reverse_copy	Змінює порядок слідування елементів у заданому діапазоні на протилежний
rotate, rotate_copy	Виконує циклічний зсув вліво елементів у заданому діапазоні
search	Виконує пошук однієї послідовності усередині іншої
search_n	Усередині деякої послідовності виконує пошук заданої кількості подібних елементів
set_difference	Створює послідовність, яка містить різницю двох впорядкованих множин
set_intersection	Створює послідовність, яка містить перетин двох впорядкованих множин
set_symmetric_difference	Створює послідовність, яка містить симетричну різницю двох впорядкованих множин
set_union	Створює послідовність, яка містить об'єднання двох впорядкованих множин
sort	Сортує заданий діапазон
sort_heap	Сортує купу у заданому діапазоні
stable_partition	Упорядковує задану послідовність так, щоб всі елементи, для яких заданий предикат повертає значення true, розміщувалися перед елементами, для яких цей предикат повертає значення false. Таке розбиття є стабільним, що означає збереження відносного порядку послідовності
stable_sort	Виконує стійке (стабільне) сортування заданого діапазону. Це означає, що однакові елементи не переставляються
swap	Змінює місцями задані два значення
swap_ranges	Виконує обмін елементів у заданому діапазоні
transform	Застосовує функцію до заданого діапазону елементів і зберігає результат у новій послідовності
unique, unique_copy	Видаляє елементи, які повторюються, із заданого діапазону
upper_bound	Знаходить останній елемент у заданій послідовності, який є не більшим від заданого значення

22.6.1. Підрахунок кількості елементів

Одна з найпопулярніших операцій, яку можна виконати для будь-якої послідовності елементів, – підрахувати їх кількість. Для цього можна використовувати один з алгоритмів: count () або count _ if (). Загальний формат цих алгоритмів має такий вигляд:

template < class InIter, class myType>

ptrdiff_t count (InIter start, InIter end, const myType & val);

template < class InIter, class UnPred >

ptrdiff_t count_if (InIter start, InIter end, UnPred pfn);

Алгоритм count () повертає кількість елементів, що дорівнює значенню val, у послідовності, межі якої задані параметрами start і end. Алгоритм count _ if (), діючи у послідовності, межі якої задані параметрами start і end, повертає кількість елементів, для яких унарний предикат pfn повертає значення true. Тип ptrdiff_t визначається як деякий різновид цілочисельного типу.

Використання алгоритмів count () і count _ if () продемонстровано у наведеному нижче коді програми.

Код програми 22.13. Демонстрація механізму використання алгоритмів count і count_if

#include <vcl>

#include <iostream> // Для потокового введення-виведення

#include <conio> // Для консольного режиму роботи

#include <vector> // Для роботи контейнерним класом "Вектор"

#include <algorithm> // Для роботи з алгоритмами бібліотеки STL

#include <cctype> // Для роботи з символьними аргументами

using namespace std; // Використання стандартного простору імен

/* Це унарний предикат, який визначає,

чи представляє даний символ голосний звук. */

// а б в г д е є ж з и і ї й к л м н о п р c т у ф х ц ч ш щ ю я ь

bool isvowel(char ch) {

ch = tolower (ch);

if (ch=='а' || ch=='е' || ch=='є' || ch=='и'

|| ch=='і' || ch=='ї' || ch=='о' || ch=='у'

|| ch=='ю' || ch=='я') return true;

return false;

}

int main ()

{

char str[] = "STL-програмування -- це сила!";

vector < char > vek;

unsigned int i;

for (i=0; str[i]; i++) vek. push_back (str[i]);

cout << "Послідовність: ";

for (i=0; i<vek. size (); i++) cout << vek[i];

cout << endl;

int n; char ch = 'н';

n = count (vek. begin (), vek. end (), ch);

cout << n << " символи '" << ch << "'\n";

n = count _ if (vek. begin (), vek .end (), isvowel);

cout << n << " символів представляють голосні звуки.\n";

getch (); return 0;

}

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

Послідовність: STL-програмування -- це сила!

2 символи н

8 символів представляють голосні звуки.

Програма починається із створення вектора, який містить рядок "STL-програмування – це сила!". Потім використовується алгоритм count () для підрахунку кількості букв 'н' у цьому векторі. Після цього викликається алгоритм count _ if (), який підраховує кількість символів, що представляють голосні звуки з використанням як предикату функції isvowel (). Звернемо Вашу увагу на те, як закодований цей предикат. Всі унарні предикати отримують як параметр об'єкт, тип якого збігається з типом елементів, що зберігаються у контейнері, для якого і створюється цей предикат. Предикат повинен повертати значення ІСТИНА або ФАЛЬШ.

22.6.2. Видалення і заміна елементів

Іноді корисно згенерувати нову послідовність, яка складатиметься тільки з певних елементів початкової послідовності. Одним з алгоритмів, який може справитися з цим завданням, є remove_copy (). Його загальний формат має такий вигляд:

template < class ForIter, class OutIter, class myType>

OutIter remove_copy (InIter start, InIter end,

OutIter result, const myType & val);

Алгоритм remove_copy () копіює з вилученням із заданого діапазону елементи, які дорівнюють значенню val, і поміщає результат у послідовність, яка адресується параметром result. Алгоритм повертає ітератор, який вказує на кінець результату. Контейнер-приймач повинен бути достатньо великим, щоб прийняти отриманий результат.

Щоб у процесі копіювання у послідовності один елемент замінити іншим, використовується алгоритм replace_copy (). Його загальний формат має такий вигляд:

template < class ForIter, class OutIter, class myType>

OutIter replace_copy (InIter start, InIter end,

OutIter result, const myType & old, Const myType &new);

Алгоритм replace_copy () копіює елементи із заданого діапазону у послідовність, яка адресується параметром result. У процесі копіювання відбувається заміна елементів, які мають значення old, елементами, які мають значення new. Алгоритм поміщає результат у послідовність, яка адресується параметром result, і повертає ітератор, який вказує на кінець цієї послідовності. Контейнер-приймач повинен бути достатньо великим, щоб прийняти отриманий результат.

У наведеному нижче коді програми продемонстровано механізм використання алгоритмів remove_copy () і replace_copy (). Під час її виконання створюється послідовність символів, з якої віддаляються всі букви 'е'. Потім виконується заміна всіх букв 'е' буквами 'x'.

Код програми 22.14. Демонстрація механізму використання алгоритмів remove_copy і replace_copy

#include <vcl>

#include <iostream> // Для потокового введення-виведення

#include <conio> // Для консольного режиму роботи

#include <vector> // Для роботи контейнерним класом "Вектор"

#include <algorithm> // Для роботи з алгоритмами бібліотеки STL

using namespace std; // Використання стандартного простору імен

int main ()

{

char str[] = "Це дуже простий тест.";

vector < char > vek, vek2(30);

unsigned int i;

for (i=0; str[i]; i++) vek. push_back (str[i]);

// **** Демонстрація алгоритму remove_copy ****

cout << "Вхідна послідовність: ";

for (i=0; i<vek. size (); i++) cout << vek[i];

cout << endl;

// Видаляємо всі букви 'е'.

remove_copy (vek. begin (), vek .end (), vek2. begin (), 'т');

cout << "Після видалення букв 'т': ";

for (i=0; vek2[i]; i++) cout << vek2[i];

cout << endl << endl;

// **** Демонстрація алгоритму replace_copy ****

cout << "Вхідна послідовність: ";

for (i=0; i<vek. size (); i++) cout << vek[i];

cout << endl;

// Замінюємо букви 'е' буквами 'Х'.

replace_copy (vek. begin (), vek .end (), vek2. begin (), 'o', 'x');

cout << "Після заміни букв 'е' буквами 'X': ";

for (i=0; vek2[i]; i++) cout << vek2[i];

cout << endl << endl;

getch (); return 0;

}

Результати виконання цієї програми є такими:

Вхідна послідовність: Це дуже простий тест.

Після видалення букв 'е': Ц дуж простий тст.

Вхідна послідовність: Це дуже простий тест.

Після заміни букв 'е' буквами 'X': ЦХ дужХ простий тХст.

22.6.3. Реверсування послідовності

У програмах часто використовують алгоритм reverse (), який у діапазоні, заданому параметрами start і end, змінює порядок слідування елементів на протилежний. Його загальний формат має такий вигляд:

template < class BiIter > void reverse (BiIter start, BiIter end);

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

Код програми 22.15. Демонстрація механізму використання алгоритму reverse

#include <vcl>

#include <iostream> // Для потокового введення-виведення

#include <conio> // Для консольного режиму роботи

#include <vector> // Для роботи контейнерним класом "Вектор"

#include <algorithm> // Для роботи з алгоритмами бібліотеки STL

using namespace std; // Використання стандартного простору імен

int main ()

{

vector < int > vek;

unsigned int i;

for (i=0; i<10; i++) vek. push_back (i);

cout << "Початкова послідовність: ";

for (i=0; i<vek. size (); i++) cout << vek[i] << " ";

cout << endl;

reverse (vek. begin (), vek .end ());

cout << "Реверсована послідовність: ";

for (i=0; i<vek. size (); i++) cout << vek[i] << " ";

getch (); return 0;

}

Результати виконання цієї програми є такими:

Початкова послідовність: 0 1 2 3 4 5 6 7 8 9

Реверсована послідовність: 9 8 7 6 5 4 3 2 1 0

22.6.4. Перетворення послідовності

Одним з найцікавіших алгоритмів є transform (), оскільки він дає змогу модифікувати кожен елемент у діапазоні відповідно до заданої функції. Алгоритм transform () використовується у двох загальних форматах:

template < class InIter, class OutIter, class Funс >

OutIter transform (InIter start, InIter end,

OutIter result, Funс unaryfunc);

template < class InIter1, class InIter2, class OutIter, class Funс >

OutIter transform (InIter1 start1, InIter1 end1,

InIter 2 start2, OutIter result, Funс binaryfunc);

Алгоритм transform () застосовує функцію до діапазону елементів і зберігає результат у послідовності, яка задається параметром result. У першій формі діапазон задається параметрами start і end. Використовувана для перетворення функція задається параметром unaryfunc. Вона приймає значення елемента як параметр і повинна повернути перетворене значення. У другому форматі алгоритму перетворення виконується з використанням бінарної функції, яка приймає як перший параметр значення призначеного для перетворення елемента з послідовності, а як другий параметр – елемент з другої послідовності. Обидві версії повертають ітератор, який вказує на кінець остаточної послідовності.

У наведеному нижче коді програми використовується проста функція перетворення xform (), яка підносить до квадрату кожен елемент списку. Звернемо Вашу увагу на те, що остаточна послідовність зберігається у тому ж списку, який містив початкову послідовність.

Код програми 22.16. Демонстрація механізму використання алгоритму transform

#include <vcl>

#include <iostream> // Для потокового введення-виведення

#include <conio> // Для консольного режиму роботи

#include <list> // Для роботи зі списками

#include <algorithm> // Для роботи з алгоритмами бібліотеки STL

using namespace std; // Використання стандартного простору імен

// Проста функція перетворення.

int xform (int i) {

return i * i; // Квадрат початкового значення

}

int main ()

{

list < int > x1;

int i;

// Поміщаємо значення у список.

for (i=0; i<10; i++) x1. push_back (i);

cout << "Початковий список x1: ";

list < int >:: iterator p = x1. begin ();

while (p!= x1 .end ()) {

cout << *p << " ";

p++;

}

cout << endl;

// Перетворення списку x1.

p = transform (x1. begin (), x1 .end (), x1. begin (), xform);

cout << "Перетворений список x1: ";

p = x1. begin ();

while (p!= x1 .end ()) {

cout << *p << " ";

p++;

}

getch (); return 0;

}

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

Початковий список x1: 0 1 2 3 4 5 6 7 8 9

Перетворений список x1: 0 1 4 9 16 25 36 49 64 81

Як бачите, кожен елемент у списку x1 тепер зведений у квадрат.

22.6.5. Дослідження алгоритмів

Описані вище алгоритми є тільки малою частиною всього вмісту бібліотеки STL. І звичайно ж, Вам потрібно самим досліджувати інші алгоритми. Заслуговують уваги, наприклад, такі, як set_union () і set_difference (). Вони призначені для оброблення вмісту такого контейнера, як множина. Цікаві також алгоритми next_permutation () і prev_permutation (). Вони створюють наступну і попередню перестановки елементів заданої послідовності. Час, витрачений на вивчення алгоритмів бібліотеки STL, – це час, витрачений не дарма!

22.7. Використання класу string

Як уже зазначалося вище, мова програмування C++ не підтримує вбудований рядковий тип. Проте він надає два способи оброблення рядків. По-перше, для представлення рядків можна використовувати традиційний символьний масив, що завершується нулем. Рядки, що створюються у такий спосіб (він Вам вже знаком), іноді називають С-рядками. По-друге, можна використовувати об'єкти класу string, і саме цей спосіб розглядається у цьому розділі.

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

Насправді клас string є спеціалізацію більш загального шаблонного класу basic_string. Існує дві спеціалізації типу basic_string: тип string, який підтримує 8-бітові символьні рядки, і тип wstring, який підтримує рядки, утворені двобайтовими символами. Найчастіше у звичайному програмуванні використовуються рядкові об'єкти типу string. Для використання рядкових класів C++ необхідно приєднати до програми заголовок < string >.

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

char s1[80], s2[80], s3[80];

s1 = "один"; // так робити не можна

s2 = "два"; // так робити не можна

s3 = s1 + s2; // помилка

Як зазначено у коментарях до цієї програми, y мові програмування C++ неможливо використовувати оператор присвоєння для додання символьному масиву нового значення (за винятком настанови| ініціалізації), а також не можна застосовувати оператор додавання "+" для конкатенації двох рядків Ці операції можна виконати за допомогою бібліотечних функцій.

strcpy (s1, "one");

strcpy (s2, "two");

strcpy (s3, s1);

strcpy (s3, s2);

Оскільки символьний масив, що завершується нулем, формально не є саме самостійним типом даних, до нього не можна застосувати С++-оператори. Це позбавляє "вишуканості" навіть самі елементарні операції з рядками. І саме нездатність обробляти рядки, що мають завершальний нуль-символ, за допомогою стандартних С++-операторів при вела до розробки стандартного рядкового класу. Пригадайте: створюючи клас у мові програмування C++, ми визначаємо новий тип даних, який можна повністю інтегрувати у С++-среду Це, звичайно ж, означає, що для нового класу можна перевантажувати оператори. Таким чином, вводячи в мову стандартний рядковий клас, ми створюємо можливість для оброблення рядків так само, як і даних будь-якого іншого типу, а саме за допомогою операторів.

Проте існує ще одна причина, що реабілітує створення стандартного класу string: безпека. Руками недосвідченого або необережного програміста дуже ліг до забезпечити вихід за межі масиву, який містить рядок з тим, що завершує нулем. Розглянемо, наприклад, стандартну функцію копіювання strcpy (). Ця функція не передбачає механізм перевірки факту порушення меж масиву приймача. Якщо початковий масив містить більше символів, ніж може прийняти масив приймач, то в результаті цієї помилки дуже вірогідна повна відмова системи. Як буде-показано нижче, стандартний клас string не допускає виникнення подібних помилок

Дата добавления: 2014-11-29