C++. STL. Алгоритми, які не змінюють значень та порядка слідування елементів

Частина 1. Алгоритми, які не змінюють значень та порядка слідування елементів (немодифікуючі алгоритми). Пошук. Приклади


Зміст


Пошук на інших ресурсах:

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

 


Споріднені теми