Немодифицирующие алгоритмы. Примеры

---

Содержание

• 1. Алгоритм count. Определить количество вхождений заданного элемента в последовательности
• 2. Алгоритм count_if. Определить количество вхождений элемента в последовательности на основе заданного условия
• 3. Алгоритм equal. Определить, совпадают ли элементы двух диапазонов
• 4. Алгоритм equal_range. Возврат диапазона, который допускает вставку элементов без нарушения порядка
• 5. Алгоритм mismatch. Поэлементное сравнение двух диапазонов
• Связанные темы

---

Поиск на других ресурсах:

1. Алгоритм count. Определить количество вхождений заданного элемента в последовательности

Алгоритм count возвращает количество элементов в последовательности, значение которых соответствует заданному значению. Общая форма объявления алгоритма следующая

template <class InputIterator, class Type>
typename iterator_traits<InputIterator>::difference_type count(
  InputIterator first,
  InputIterator last,
  const Type& value);

где

• first, last – итераторы, задающие пределы последовательности;
• value – значение элементов для подсчета.

Пример.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main()
{
  // Алгоритм count - количество значений в массиве
  // 1. Создать динамический массив случайных чисел от 0 до 9
  vector<int> v;
  for (int i = 0; i < 10; i++)
    v.push_back(rand() % 10);

  // 2. Вывести массив на экран
  cout << "V => ";
  for (int i = 0; i < v.size(); i++)
    cout << v[i] << " ";
  cout << endl;

  // 3. Применить алгоритм count()
  // 3.1. Определить количество чисел 5
  int num7 = count(v.begin(), v.end(), 7);
  cout << "Number 7 - " << num7 << endl;

  // 3.2. Определить количество чисел 2
  int num2 = count(v.begin(), v.end(), 2);
  cout << "Number 2 - " << num2 << endl;
}

Результат

V => 1 7 4 0 9 4 8 8 2 4
Number 7 - 1
Number 2 - 1

  ⇑

2. Алгоритм count_if. Определить количество вхождений элемента в последовательности на основе заданного условия

Алгоритм count_if возвращает количество элементов в диапазоне, соответствующих заданному условию (заданному критерию). Условие (критерий) может быть задано с помощью унарного предиката или лямбда-выражения.

Объявление распространенной реализации алгоритма имеет вид:

template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type count_if(
  InputIterator first,
  InputIterator last,
  UnaryPredicate pred);

здесь

• first, last – итераторы ввода, задающие границы диапазона;
• pred – унарный предикат, задающий условие вычисления.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

// Предикат, определяющий условие вычисления для алгоритма count_if
bool Multiple_3(int a)
{
  // Если a - число кратное 3
  return a % 3 == 0;
}

int main()
{
  // Алгоритм count_if – определить количество вхождений элемента в последовательности,
  // соответствующее заданному условию.

  // 1. Использование алгоритма на основе лямбда-выражения
  // 1.1. Объявить список строк
  list<string> LS = { "abc", "def", "dabc", "bcdemks", "fjidj", "def", "jklmn" };

  // 1.2. Объявить переменную-результат
  list<string>::iterator::difference_type res; // тип res - long long

  // 1.3. Определить количество строк в списке, длина которых меньше 5
  res = count_if(
    LS.begin(),
    LS.end(),
    [](string s) // лямбда-выражение
    {
      return s.length() < 5;
    }
  );

  // 1.4. Вывести результат
  cout << "res = " << res << endl;

  // 2. Использование алгоритма на основе предиката Multiple_3
  // 2.1. Объявить массив чисел
  vector<int> V = { 2, 8, 4, 1, 7, -3, 0, 9, 11 };

  // 2.2. Объявить переменную-результат
  vector<int>::iterator::difference_type res2;

  // 2.3. Вызвать алгоритм с указанием предиката
  res2 = count_if(
    V.begin(),
    V.end(),
    Multiple_3
  );

  // 2.4. Вывести результат
  cout << "res2 = " << res2 << endl;
}

Результат

res = 4
res2 = 3

  ⇑

3. Алгоритм equal. Определить, совпадают ли элементы двух диапазонов

Алгоритм equal выполняет поэлементное сравнение двух диапазонов на предмет равенства или равноценности. Это равенство (равноценность) может быть задано предикатом. Распространенные реализации алгоритма имеют следующие объявления

template <class InputIterator1, class InputIterator2>
bool equal(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  bool equal(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  BinaryPredicate pred);

здесь

• first1, last1 – итераторы ввода, задающие пределы выходного диапазона;
• first2 – итератор ввода, указывающий на первый элемент второго диапазона, который сравнивается с исходным;
• pred – бинарный предикат или лямбда-выражение, задающее условие сравнения.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

// Предикат, определяющий условие вычисления для алгоритма equal
bool Is_Equal(string s1, string s2)
{
  // Сравниваются только длины элементов
  return s1.length() == s2.length();
}

int main()
{
  // Алгоритм equal - определить совпадают ли элементы двух диапазонов

  // 1. Использование алгоритма без предиката
  // 1.1. Объявить список строк
  list<string> LS1 = { "00", "11", "22", "33", "44" };

  // 1.2. Создать новый список длиной LS1 – длина списка LS2
  // должна быть не меньше длины списка LS1
  list<string> LS2(LS1.size());

  // 1.3. Скопировать значения из LS1 в LS2
  copy(LS1.begin(), LS1.end(), LS2.begin()); // списки равны

  // 1.4. Объявить переменную-результат
  bool f_equal;

  // 1.5. Вызвать алгоритм equal без предиката или лямбда-выражения.
  // В этом случае за основу берется длина последовательности LS1.
  f_equal = equal(LS1.begin(), LS1.end(), LS2.begin());

  // 1.6. Обработать результат
  if (f_equal)
    cout << "LS1 == LS2" << endl;
  else
    cout << "LS1 != LS2" << endl;

  // 2. Использование алгоритма с предикатом
  // 2.1. В списке LS1 изменить первый элемент из "00" на "AA"
  list<string>::iterator it = LS1.begin();
  *it = "AA";

  // 2.2. Вызвать алгоритм на основе предиката Is_Equal
  f_equal = equal(LS1.begin(), LS1.end(), LS2.begin(), Is_Equal);

  // 2.3. Обработать результат
  if (f_equal)
    cout << "LS1 == LS2" << endl;
  else
    cout << "LS1 != LS2" << endl;

  // 3. Использование алгоритма с лямбда-выражением
  // 3.1. Огласить два массива чисел одинаковой длины
  vector<double> V1 = { 1.7, 2.8, 3.9 };
  vector<double> V2 = { -1.7, 2.8, -3.9 };

  // 3.2. Вызвать алгоритм, лямбда-выражение задает условие сравнения
  f_equal = equal(
    V1.begin(),
    V1.end(),
    V2.begin(),
    [](double a, double b) {
      // сравниваются модули чисел
      return fabs(a) == fabs(b);
    }
  );

  // 3.3. Обработать результат
  if (f_equal)
    cout << "LS1 == LS2" << endl;
  else
    cout << "LS1 != LS2" << endl;
}

Результат

LS1 == LS2
LS1 == LS2
LS1 == LS2

  ⇑

4. Алгоритм equal_range. Возврат диапазона, который допускает вставку элементов без нарушения порядка

В упорядоченном диапазоне находит диапазон, в котором все элементы эквивалентны заданному значению. Согласно документации объявления алгоритма следующее:

template <class ForwardIterator, class Type>
pair<ForwardIterator, ForwardIterator> equal_range(
  ForwardIterator first,
  ForwardIterator last,
  const Type& value);

template <class ForwardIterator, class Type, class Compare>
pair<ForwardIterator, ForwardIterator> equal_range(
  ForwardIterator first,
  ForwardIterator last,
  const Type& value,
  Compare pred);

здесь

• first, last – исходный диапазон;
• value – искомое значение;
• pred – функция-предикат, которая задает условие, когда один элемент меньше другого.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
  // Алгоритм equal_range – возвращает диапазон, допускающий вставку элементов
  // без нарушения порядка. Элементы предварительно должны быть упорядочены

  // 1. Объявить вектор чисел
  vector<int> V = { 1, 2, 8, 4, 5, 6, 7 };

  // 2. Отсортировать вектор
  sort(V.begin(), V.end());

  // 3. Вывести на екран
  cout << "V => ";
  for (int i : V)
    cout << i << " ";
  cout << endl;

  // 4. Объявить переменную-результат
  //    первое значение пары - начало диапазона;
  //    второе значение пары - конец диапазона.
  pair<typename vector<int>::iterator, typename vector<int>::iterator> it;

  // 5. Вызов алгоритма equal_range
  it = equal_range(V.begin(), V.end(), 4);

  // 6. Вывести значение пары
  cout << "it->first = " << *it.first << endl;
  cout << "it->second = " << *it.second << endl;

  // 7. Вывести массив
  cout << endl << "V+ => ";

  for (vector<int>::iterator i = V.begin(); i != V.end(); ++i)
  {
    cout << *i << " ";
  }
  cout << endl;
}

Результат

V => 1 2 4 5 6 7 8
it->first = 4
it->second = 5

V+ => 1 2 4 5 6 7 8

  ⇑

5. Алгоритм mismatch. Поэлементное сравнение двух диапазонов

Алгоритм mismatch выполняет поэлементное сравнение двух диапазонов на равенство или равноценность на основе заданного бинарного предиката. Алгоритм возвращает первую позицию, где найдены отличия.

Общая форма объявления алгоритма следующая

template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>>
mismatch(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2 );

template <class InputIterator1, class InputIterator2,
  class BinaryPredicate> pair<InputIterator1, InputIterator2>>
mismatch(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  BinaryPredicate pred);

здесь

• first1, last1 – входные итераторы, задающие первый диапазон тестирования;
• first2, last2 – входные итераторы, задающие второй диапазон тестирования;
• pred – объект функции-предиката, сравнивающий текущие элементы в каждом диапазоне и определяющий их эквивалентность.

Пример.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

// Предикат, используемый в алгоритме mismatch
bool Is_Equal(double a, double b)
{
  // Элемент второй последовательности на 1 больше чем элемент первой последовательности
  return a + 1 == b;
}

void main()
{
  // Алгоритм mismatch - сравнить два диапазона

  // 1. Использование алгоритма без предиката
  // 1.1. Объявить два массива
  vector<double> v1 = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
  vector<double> v2 = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };

  // 1.2. Вызов алгоритма mismatch
  auto mismatchPair = mismatch(v1.begin(), v1.end(), v2.begin(), v2.end());

  // 1.3. Обработка результата
  bool is_mismatch = mismatchPair.first != v1.end();
  if (is_mismatch)
    cout << "v1 != v2" << endl;
  else
    cout << "v1 == v2" << endl;

  // 2. Использование алгоритма с предикатом
  // 2.1. Объявить два списка
  list<int> l1 = { 1, 8, 4, 3, 2 };
  list<int> l2 = { 2, 9, 5, 4, 3 };

  // 2.2. Вызвать алгоритм
  auto mismatchPair2 = mismatch(l1.begin(), l1.end(), l2.begin(), l2.end(), Is_Equal);

  // 2.3. Обработка результата
  is_mismatch = mismatchPair2.first != l1.end();
  if (is_mismatch)
    cout << "l1 != l2" << endl;
  else
    cout << "l1 == l2" << endl;
}

Результат

v1 == v2
l1 == l2

  ⇑

---

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

• Алгоритмы работы с данными которые представлены по принципу «кучи» (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

  ⇑

---