• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Параметричні (родові) алгоритми

Розглянемо два найпростіших параметричних (родових) алгоритми STL: алгоритми find та merge.

Алгоритм find, використовуваний для пошуку одного значення в якійсь послідовності, подає простий приклад, що ілюструє гнучкість алгоритмів STL. Його можна застосовувати з довільним контейнером STL. Для масиву маємо:

#include <iostream.h>

#include <string.h>

#include <algo.h>

#include <assert.h>

int main ()

{

cout <<«Параметричний алгоритм find для масиву» << end1;

char* s = «С++ краще, ніж С»;

int len = strlen(s);

//пошук першого входження символа (букви) «е»

char* where = find(&s[0], &s[len], `e´);

assert (*where == `e’ && * (where+1) == `t´);

}

Ця програма призначена для пошуку символа `e´ в масиві символів s[0], s[1], ..., s[len-1]. Якщо символ `e´ є в масиві s, то покажчик where встановлюється на перше входження цього символу в масив s, тобто в цьому разі *where = = `e´. Якщо символ `e´ в масиві s відсутній, то результатом find буде &s[len], тобто покажчик на позицію, наступну за масивом.

Тепер розглянемо випадок, коли рядок, в якому відшукується символ, розміщений не в масиві, а у векторі (vector) — контейнері, що так само, як і масив, надає доступ до елементів. Для пошуку символа у векторі можна взяти алгоритм find, який був використаний для пошуку в масиві:

#include <iostream.h>

#include <string.h>

#include <algo.h>

#include <vector.h>

#include <assert.h>

int main ()

{

cout <<«Параметричний алгоритм find для вектора.» << end1;

char* s = «С++ краще, ніж С»;

int len = strlen(s);

//ініціалізація вектора вмісту рядка s

vector<char> vector1(&s[0], &s[len]);

//пошук першого входження букви е

vector<char>::iterator

where = find(vector1.begin(),vector1.end(),`e´);

assert (*where == `e´ && * (where+1) == `t´);

}

Цього разу конструюємо вектор, який містить ті ж самі елементи, що й масив s, застосовуючи конструктор класу vector, що ініціалізує вектор значеннями елементів масиву S. Змінна where тут вже не типу char*; вона має тип vector<char>::iterator. Ітератори — це об’єкти, які можуть використовуватися для видачі всіх позицій послідовності об’єктів. Коли послідовність розміщується в масиві типу char, ітератори є покажчиками мови С++ (типу char*), але коли послідовність розміщується в якомусь контейнері, наприклад у векторі, тип відповідного ітератора має бути взятий з контейнерного класу: у кожному контейнерному класі С бібліотеки STL визначено тип ітератора С:: iterator, який може використовуватися з контейнерами типу С.

У всіх випадках виклику алгоритму find, як, скажімо,

where = find (first, last, value);

припускається, що

· ітератор first відмічає позицію в послідовності, з якої має початися пошук;

· last відмічає позицію в послідовності, на якій пошук має закінчитися.

Саме ці позиції і визначаються за допомогою функцій — членів begin та end класу vector (та всіх інших контейнерних класів STL).

Якщо елементи даних розглянуті у списку, алгоритм find має вигляд:

#include <iostream.h>

#include <string.h>

#include <list.h>

#include <algo.h>

#include <assert.h>

int main ()

{

cout <<«Параметричний алгоритм find для списку.» << end1;

char* s = «С++ краще, ніж С»;

int len = strlen (s);

//ініціалізація списку list 1 вмісту рядка s

list<char> list1 (&s[0], &s[len]);

//пошук першого входження букви е

list<char>::iterator

where = find (list1.begin(), list1.end(),`e´);

assert (*where == `e´ && * (+ + where) == `t´);

}

Між цією програмою та програмою попереднього прикладу, в якій використовується вектор, є одна істотна різниця, яка пов’язана з тим, що ітератор для списку не підтримує операції +, яка використовується у виразі *(where +1). Проте у STL потрібно, щоб всі ітератори підтримували операцію ++, і саме тому в програмі використано вираз *(++where).

Якщо дані розміщені у деці (deque), а дека є контейнером з вільним допуском, як і масиви та вектори, алгоритм find набирає вигляду:

#include <iostream.h>

#include <string.h>

#include <deque.h>

#include <algo.h>

#include <assert.h>

int main ()

{

cout <<«Параметричний алгоритм find для дека.» << end1;

char* s = «С++ краще, ніж С»;

int len = strlen (s);

//ініціалізація деці deque1 вмісту рядка s

deque<char> deque1(&s[0], &s[len]);

//пошук першого входження букви е

deque<char>::iterator

where = find(deque1.begin(),deque1.end(),`e´);

assert (*where == `e´ && * (+ + where) == `t´);

}

Ця програма ідентична програмі для вектора, з тією лише різницею, що замість контейнера типу вектор (vector) використовується контейнер типу (deque): ітератор дека підтримує операцію +.

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

Гнучкість параметричних алгоритмів STL значно більша, ніж та, що її ілюструє приклад алгоритму find. Розглянемо параметричний алгоритм marge, який повніше демонструє можливості STL. Цей алгоритм зливає дві впорядковані послідовності елементів деякого (одного й того самого) типу в одну, зберігаючи впорядкованість елементів у результуючій послідовності. Нехай виклик алгоритму marge має вигляд:

marge (first1, last1, first2, last2, result);

причому

· ітератори first1 та last1 позначають початок та кінець першої початкової послідовності елементів типу Т;

· ітератори first2 та last2 розміщують другу початкову послідовність, елементи якої також мають тип Т;

· обидві початкові послідовності впорядковані за операцією (відношенням)<, визначеною для типу Т;

· result визначає початок послідовності, в якій має бути розміщений результат процедури.

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

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

#include <iostream.h>

#include <string.h>

#include <deque.h>

#include <list.h>

#include <algo.h>

#include <assert.h>

list<char> lst(char* s)

//Перетворює рядок s до структури list<char>

{

list<char> x;

while (*s!=`\0´)

x.push_back(*s++);

return x;

}

deque<char> deq(char* s)

//Перетворює рядок s до структури deque<char>

{

deque<char> x;

while (*s!=`\0´)

x.push_back(*s++);

return x;

}

intr main ()

{

cout <<«Параметричний алгоритм merge для «

<<«масиву, списку та деки << end1;

char* s = «acegikm»;

int len = strlen(s);

list<char> list1 = lst(«bdfhjlnopqrstuvwxyz»);

//ініціалізація деки deque1 26 копиями букви Х

deque<char> deque1(26,`x’);

//злиття масиву s та списку list1, результат в deque1

merge(&s[0], &s[len]), list1.begin(),list1.end(),

deque1.begin());

assert (deque1 == deq(«abcdefghjklmnopqrstuvwxyz»);

}

У цій програмі створюється дека deque 1 для розміщення результату злиття масиву s та списку list 1, причому всі три послідовності впорядковані лексикографічно.

Можна також виконувати злиття за порціями. У наведеному прикладі далі розглядувана програма модифікується так, щоб забезпечити злиття перших 5 символів s та перших 10 символів дека deque1 з розміщенням результату у списку list1 (зауважимо, що в новій програмі дека та список міняються ролями).

#include <iostream.h>

#include <string.h>

#include <deque.h>

#include <list.h>

#include <algo.h>

#include <assert.h>

list<char> lst(char* s)

//Перетворює рядок s до структури list<char>

//(порожній символ, що закінчує рядок, до структури

//не включається).

{

list<char> x;

while (*s!=`\0´)

x.push_back(*s++);

return x;

}

deque<char> deq(char* s)

//Перетворює рядок s до структури deque<char>

//(порожній символ, що закінчує рядок, до структури

//не включається).

{

deque<char> x;

while (*s!=`\0´)

x.push_back(*s++);

return x;

}

int main ()

{

cout << "Параметричний алгоритм merge, \n"

<<«що об’єднує частини масиву та деки і \n»

<<розміщує результат до списку.» << end1;

char* s = «acegikm»;

int len = strlen(s);

deque<char> deque1 = deq(«bdfhjlnopqrstuvwxyz»);

//ініціалізація списку list1 26 копіями букви Х

list<char> list1 (26,`x´);

//злиття перших 5 букв масиву s та перших 10 букв деки

//deque1, вміщує результат у список list1.

merge(&s[0], &s[5], deque1.begin(), deque1.begin()

+10, list1.begin());

assert (list1 == lst(«abcdefghjklmnopqrstuvwxyz»);

}

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

Переглядів: 358