Частина 1. Алгоритми, які не змінюють значень та порядка слідування елементів (немодифікуючі алгоритми). Пошук. Приклади
Зміст
- 1. Алгоритм find. Визначення, чи є елемент в послідовності
- 2. Алгоритм find_if. Визначити перше значення, що відповідає заданій умові
- 3. Алгоритм find_first_of. Пошук першого елементу підпослідовності, що співпадає з будь-яким іншим елементом послідовності
- 4. Алгоритм find_end. Пошук останнього входження підпослідовності, що міститься в заданому діапазоні
- 5. Алгоритм adjanced_find. Пошук пари сусідніх елементів, які співпадають між собою
- 6. Алгоритм search. Пошук підпослідовності в послідовності
- 7. Алгоритм search_n. Пошук підпослідовності в послідовності з задаванням кількості елементів n
- Споріднені теми
Пошук на інших ресурсах:
1. Алгоритм find. Визначення, чи є елемент в послідовності
Алгоритм find знаходить позицію першого входження елементу з заданим значенням у заданому діапазоні. Поширена реалізація алгоритму має таке оголошення
template <class InputIterator, class Type> InputIterator find( InputIterator first, InputIterator last, const Type& value);
тут
- first, last – вхідні ітератори, які задають відповідно початок та кінець діапазону, який розглядається;
- value – шукане значення.
Приклад.
#include <iostream> #include <vector> #include <queue> #include <list> #include <algorithm> using namespace std; void main() { // Алгоритм find - пошук значення в контейнері // 1. Пошук рядка у масиві vector vector<string> V; V.push_back("abc"); V.push_back("abcd"); V.push_back("def"); V.push_back("jklmn"); V.push_back("jprst"); vector<string>::const_iterator p = find(V.begin(), V.end(), "def"); if (p == V.end()) cout << "\"def\" is not found" << endl; else cout << "\"def\" is found" << endl; // 2. Пошук числа в списку list<double> L{ 2.8, 3.3, 4.5, 1.7, 2.2 }; list<double>::iterator pL; pL = find(L.begin(), L.end(), 4.5); if (pL != L.end()) cout << "The number is found." << endl; else cout << "The number is not found" << endl; }
⇑
2. Алгоритм find_if. Визначити перше значення, що відповідає заданій умові
Алгоритм find_if знаходить позицію першого входження елементу, що відповідає заданій умові у заданому діапазоні.
Поширена реалізація алгоритму має наступну загальну форму
template <class InputIterator, class UnaryPredicate> InputIterator find_if( InputIterator first, InputIterator last, UnaryPredicate pred);
де
- first, last – вхідні ітератори, які задають відповідно початок та кінець діапазону, який розглядається;
- pred – унарний предикат (об’єкт функції) або лямбда-вираз, що задає умову, якій повинен відповідати шуканий елемент.
Приклад 1.
Знаходиться перший елемент, який має значення більше 10.
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Оголосити унарний предикат bool More_10(int value) { return value > 10; } void main() { // Алгоритм find_if. Визначити перше число, що більше за 10 vector<int> V = { 4, 8, 9, 2, 10, 15 }; vector<int>::iterator p1; p1 = find_if(V.begin(), V.end(), More_10); if (p1 != V.end()) cout << "*p1 = " << *p1 << endl; else cout << "Not found" << endl; }
Результат
*p1 = 15
Приклад 2. Використовується лямбда-вираз для пошуку першого числа яке більше за 10.
#include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; void main() { // Алгоритм find_if. Визначити перше число, що більше за 10 // на основі лямбда-виразу vector<int> V = { 4, 8, 9, 2, 10, 15 }; vector<int>::iterator p1; // Тут використовується лямбда-вираз: [](int t) { return t > 10; } p1 = find_if(V.begin(), V.end(), [](int t) { return t > 10; }); if (p1 != V.end()) cout << "*p1 = " << *p1 << endl; else cout << "Not found" << endl; }
⇑
3. Алгоритм find_first_of. Пошук першого елементу підпослідовності, що співпадає з будь-яким іншим елементом послідовності
Алгоритм find_first_of виконує пошук будь-якого з декількох значень у цільовому діапазоні. Також можна задавати критерій пошуку з допомогою визначеного предикату або лямбда-виразу.
template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_first_of( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_first_of( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
тут
- first1, last1 – прямі ітератори, що вказують діапазон для пошуку;
- first2, last2 – прямі ітератори, що вказують діапазон для порівняння;
- pred – бінарний предикат або лямбда-вираз, що задає умову при якій два елементи вважаються еквівалентними один одному. Предикат повертає true у випадку відповідності.
Приклад.
#include <iostream> #include <queue> #include <vector> #include <list> #include <functional> #include <algorithm> using namespace std; // Предикат, що визначає умову виконання алгоритму find_first_of bool More_Than(int a, int b) { // пошук співпадіння до тих пір, поки // перше значення не стане більше другого, // тобто елемент першої послідовності не стане // більше елементу другої послідовності return a > b; } int main() { // Алгоритм find_first_of - пошук першого елементу підпослідовності, // що співпадає з будь-яким іншим елементом послідовності. // 1. Використання алгоритму без предикату // 1.1. Оголосити два вектори та вивести їх vector<int> V1 = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 }; vector<int> V2 = { 4, 5 }; vector<int>::iterator it = V1.begin(); cout << "V1 => "; while (it != V1.end()) { cout << *it << " "; it++; } cout << endl; it = V2.begin(); cout << "V1 => "; while (it != V2.end()) { cout << *it << " "; it++; } cout << endl; // 1.2. Оголосити ітератор на результуючий елемент vector<int>::iterator resItem; // 1.3. Виклик алгоритму без предикату чи лямбда-виразу resItem = find_first_of(V1.begin(), V1.end(), V2.begin(), V2.end()); // 1.4. Вивести значення на яке вказує resItem if (resItem == V1.end()) cout << "resItem -> V1.end()" << endl; else cout << "resItem -> " << *resItem << endl; // 1.5. Вивести послідовність починаючи з resItem vector<int>::iterator it2 = resItem; cout << "resItem: "; while (it2 != V1.end()) { cout << *it2 << " "; it2++; } cout << endl; // 2. Використати алгоритм з предикатом More_Than // 2.1. Оголосити нові два вектори vector<int> V3 = { 1, 3, 5, 7, 9, 10 }; vector<int> V4 = { 2, 4, 6 }; // 2.2. Вивести ці вектори it = V3.begin(); cout << "V3 => "; while (it != V3.end()) { cout << *it << " "; it++; } cout << endl; it = V4.begin(); cout << "V4 => "; while (it != V4.end()) { cout << *it << " "; it++; } cout << endl; // 2.3. Оголосити новий ітератор-результат vector<int>::iterator resItem2; // 2.4. Викликати алгоритм find_first_of з предикатом resItem2 = find_first_of(V3.begin(), V3.end(), V4.begin(), V4.end(), More_Than); // 2.5. Вивести значення на яке вказує resItem2 if (resItem2 == V3.end()) cout << "resItem2 -> V3.end()" << endl; else cout << "resItem2 -> " << *resItem2 << endl; // 2.6. Вивести послідовність починаючи з resItem2 vector<int>::iterator it3 = resItem2; cout << "resItem2: "; while (it3 != V3.end()) { cout << *it3 << " "; it3++; } }
Результат
V1 => 2 1 3 2 4 5 2 1 3 0 V1 => 4 5 resItem -> 4 resItem: 4 5 2 1 3 0 V3 => 1 3 5 7 9 10 V4 => 2 4 6 resItem2 -> 3 resItem2: 3 5 7 9 10
⇑
4. Алгоритм find_end. Пошук останнього входження підпослідовності, що міститься в заданому діапазоні
Алгоритм find_end шукає в діапазоні останню підпослідовність, що співпадає з заданою послідовністю.
Алгоритм має наступні перевантажені реалізації
template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class Pred> ForwardIterator1 find_end( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Pred pred);
тут
- first1, last1 – прямі ітератори, що вказують діапазон для пошуку;
- first2, last2 – прямі ітератори, що вказують діапазон для порівняння;
- pred – бінарний предикат або лямбда-вираз, що задає умову при якій два елементи вважаються еквівалентними один одному. Предикат повертає true у випадку відповідності.
Приклад.
#include <iostream> #include <queue> #include <vector> #include <list> #include <functional> #include <algorithm> using namespace std; int main() { // Алгоритм find_end - пошук останнього входження підпослідовності, // що міститься в заданому діапазоні. // 1. Використання алгоритму без предикату - пошук послідовності { 2, 1, 3 } // 1.1. Оголосити вектор з 10 елементів та вивести його vector<int> V = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 }; vector<int>::iterator it = V.begin(); cout << "V => "; while (it != V.end()) { cout << *it << " "; it++; } cout << endl; // 1.2. Створити ітератори на початок та кінець підпослідовності: { 2, 1, 3 } vector<int>::iterator itBegin = V.begin(); vector<int>::iterator itEnd = itBegin; itEnd++; itEnd++; // itEnd -> V[2] = 3 // 1.3. Викликати алгоритм find_end - отримати ітератор на початок підпослідовності vector<int>::iterator itRes = find_end(V.begin(), V.end(), itBegin, itEnd); // 1.4. Вивести послідовність, яка слідує перед itRes it = V.begin(); cout << "Before itRes: "; while (it != itRes) { cout << *it << " "; it++; } cout << endl; // 1.5. Вивести значення, на яке вказує itRes if (itRes == V.end()) cout << "Subsequence not found." << endl; else cout << "itRes -> " << *itRes << endl; // 2 // 2. Використання алгоритму з лямбда-виразом - пошук послідовності { 2, 1 } // 2.1. Оголосити результуючий ітератор vector<int>::iterator itRes2; // 2.2. Налаштувати ітератори itBegin, itEnd itBegin = V.begin(); itEnd = itBegin; itEnd++; // itBegin..itEnd => { 2, 1 } // 2.3. Викликати алгоритм find_end itRes2 = find_end( V.begin(), V.end(), itBegin, itEnd, [](int a, int b) // лямбда-вираз, тут можна задати іншу умову { return a == b; } ); // 2.4. Вивести вектор до ітератора itRes2 it = V.begin(); cout << "Before itRes2: "; while (it != itRes2) { cout << *it << " "; it++; } cout << endl; // 2.5. Вивести вектор починаючи з itRes2 it = itRes2; cout << "itRes2 -> "; while (it != V.end()) { cout << *it << " "; it++; } cout << endl; }
Результат
V => 2 1 3 2 4 5 2 1 3 0 Before itRes: 2 1 3 2 4 5 itRes -> 2 Before itRes2: 2 1 3 2 4 5 itRes2 -> 2 1 3 0
⇑
5. Алгоритм adjanced_find. Пошук пари сусідніх елементів, які співпадають між собою
Загальна форма перевантажених реалізацій алгоритму
template <class ForwardIterator> ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last); template <class ForwardIterator , class BinaryPredicate> ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
де
- first – переадресація ітератора в позиції першого елементу в діапазоні для пошуку;
- last – переадресація ітератора в позиції за останнім елементом в діапазоні для пошуку;
- pred – бінарний предикат, що задає умову якій повинні відповідати значення сусідніх елементів в діапазоні [first; last-1].
Приклад.
#include <iostream> #include <vector> #include <list> #include <functional> #include <algorithm> using namespace std; bool Is_Less(int a, int b) { // розглядається пара, в якій // попередній елемент більше за наступний на 1 return a == b + 1; } int main() { // Алгоритм adjacent_find - пошук пари сусідніх елементів, які співпадають між собою // 1. Використання adjanced_find без предикату // 1.1 Створити послідовність чисел та вивести її на консоль vector<int> V1 = { 6, 8, 7, 1, -1, 3, 3, 4, 5, 5, 8, 1 }; cout << "V1 => "; for (int i : V1) cout << i << " "; cout << endl; // 1.2. Оголосити ітератор на пару, яка співпадає vector<int>::iterator it1; // 1.3. Викликати алгоритм adjanced_find it1 = adjacent_find(V1.begin(), V1.end()); // 1.4. Вивести результат if (it1 != V1.end()) cout << "*it1 = " << *it1 << endl; // *it1 = 3 else cout << "it1->V1.end()" << endl; // 2. Використання adjacent_find з предикатом Is_Less // 2.1. Оголосити ітератор на пару, яка співпадає vector<int>::iterator it2; // 2.2. Викликати алгоритм it2 = adjacent_find(V1.begin(), V1.end(), Is_Less); // 2.3. Вивести результат if (it2 != V1.end()) cout << "*it2 = " << *it2 << endl; else cout << "it2->V1.end()" << endl; // 3. Використання adjanent_find з лямбда-виразом // 3.1. Оголосити ітератор позиції vector<int>::iterator it3; // 3.2. Викликати алгоритм з вказанням лямбда-виразу it3 = adjacent_find( V1.begin(), V1.end(), [](int a, int b) { // задати умову: a і b - непарні числа return (a % 2 == 1) && (b % 2 == 1); } ); // 3.3. Обробити результат if (it3 != V1.end()) cout << "*it3 = " << *it3 << endl; // 7 else cout << "it3->V1.end()" << endl; }
Результат
V1 => 6 8 7 1 -1 3 3 4 5 5 8 1 *it1 = 3 *it2 = 8 *it3 = 7
⇑
6. Алгоритм search. Пошук підпослідовності в послідовності
З допомогою алгоритму search виконується пошук підпослідовності в заданій послідовності. Найбільш поширені реалізації алгоритму мають вигляд
template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 BinaryPredicate pred);
тут
- first1, last1 – прямі ітератори, що задають діапазон пошуку;
- first2, last2 – прямі ітератори, що задають діапазон для порівняння;
- pred – бінарний предикат (функція), що визначає умову, яка визначає рівність (еквівалентність) двох елементів між собою.
Приклад.
#include <iostream> #include <algorithm> #include <list> using namespace std; // Предикат, який визначає рівність двох елементів bool Is_Equal(int a, int b) { // критерій рівності елементів, // елемент другої послідовності на 1 більше за ел-т першої послідовності return a == b + 1; } int main() { // Алгоритм search - пошук підпослідовності в послідовності // 1. Створити список чисел list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; list<int> L2 = { 2, 3, 4 }; // 2. Викликати пошук на основі використання предикату Is_Equal // 2.1. Отримати ітератор на результуючий контейнер list<int>::iterator it; it = search(L1.begin(), L1.end(), L2.begin(), L2.end(), Is_Equal); // 2.2. Обробити результат if (it == L1.end()) cout << "There is no match."; else cout << *it << endl; // 3 // 3. Викликати пошук без використання предикату // 3.1. Отримати ітератор на результуючий контейнер it = search(L1.begin(), L1.end(), L2.begin(), L2.end()); // 3.2. Обробити результат if (it == L1.end()) cout << "There is no match."; else cout << *it << endl; // 2 }
Результат
3 2
⇑
7. Алгоритм search_n. Пошук підпослідовності в послідовності з задаванням кількості елементів n
Алгоритм search_n здійснює пошук першої підпослідовності в діапазоні заданої кількості елементів, що мають визначене значення. Відповідність цього значення можна задавати бінарним предикатом.
Найбільш поширені реалізації алгоритму наступні
template <class ForwardIterator1, class Diff2, class Type> ForwardIterator1 search_n( ForwardIterator1 first1, ForwardIterator1 last1, Diff2 count, const Type& value); template <class ForwardIterator1, class Diff2, class Type, class BinaryPredicate> ForwardIterator1 search_n( ForwardIterator1 first1, ForwardIterator1 last1, Diff2 count, const Type& value, BinaryPredicate pred);
де
- first1, last1 – прямі ітератори, що задають діапазон для пошуку;
- count – розмір шуканої послідовності;
- value – значення елементів шуканої послідовності.
Приклад.
#include <iostream> #include <algorithm> #include <list> using namespace std; // Предикат, який визначає рівність двох елементів bool Is_Equal(int a, int b) { // критерій рівності елементів, // елемент другої послідовності на 1 більше за ел-т першої послідовності return a == b + 1; } int main() { // Алгоритм search_n - пошук підпослідовності в послідовності // 1. Створити список чисел list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; list<int> L2 = { 2, 3, 4 }; // 2. Викликати пошук на основі використання предикату Is_Equal // 2.1. Оголосити ітератор на результуючий контейнер list<int>::iterator it; // 2.2. Визначити, чи зустрічається число 5 тільки 1 раз в послідовності L1: { 5 } it = search_n(L1.begin(), L1.end(), 1, 4, Is_Equal); // 4+1 = 5 // 2.3. Обробити результат if (it == L1.end()) cout << "There is no match { 5 }."; else cout << *it << endl; // 5 // 2.4. Визначити, чи зустрічається число 3 підряд 2 рази: { 3, 3 } it = search_n(L1.begin(), L1.end(), 2, 2, Is_Equal); // 2.5. Обробити результат if (it == L1.end()) cout << "There is no match { 3, 3 }." << endl; else cout << *it << endl; // 3. Викликати пошук без використання предикату // 3.1. Визначити, чи зустрічається число 7 тільки 1 раз it = search_n(L1.begin(), L1.end(), 1, 7); // 3.2. Обробити результат if (it == L1.end()) cout << "There is no match {7}. "; else cout << *it << endl; // 7 }
Результат
5 There is no match { 3, 3 }. 7
⇑
Споріднені теми
- Алгоритми для роботи з даними, що представлені за принципом “купи” (heap). Алгоритми make_heap, push_heap, pop_heap, sort_heap
- Алгоритми визначення мінімуму і максимуму. Алгоритми min, min_element, max, max_element, lexicographical_compare
- Алгоритми перестановок. Алгоритми next_permutation, prev_permutation
- Немодифікуючі алгоритми. Пошук. Алгоритми find, find_if, find_first_of, find_end, adjanced_find, search, search_n
- Немодифікуючі алгоритми. Алгоритми count, count_if, equal, equal_range, mismatch
- Алгоритми для роботи з множинами. Алгоритми includes, set_union, set_intersection, set_difference, set_symmetric_difference
⇑