Часть 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

  ⇑

---

Связанные темы

• Немодифицирующие алгоритмы. Алгоритмы count, count_if, equal, equal_range, mismatch
• Алгоритмы работы с данными которые представлены по принципу «кучи» (heap). Алгоритмы make_heap, push_heap, pop_heap, sort_heap
• Алгоритмы определения минимума и максимума. Алгоритмы min, min_element, max, max_element, lexicographical_compare
• Алгоритмы перестановок. Алгоритмы next_permutation, prev_permutation

  ⇑

---