Немодифікуючі алгоритми. Приклади

---

Зміст

• 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

  ⇑

---

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

• Немодифікуючі алгоритми. Пошук. Алгоритми find, find_if, find_first_of, find_end, adjanced_find, search, search_n
• Алгоритми для роботи з даними, що представлені за принципом “купи” (heap). Алгоритми make_heap, push_heap, pop_heap, sort_heap
• Алгоритми визначення мінімуму і максимуму. Алгоритми min, min_element, max, max_element, lexicographical_compare
• Алгоритми перестановок. Алгоритми next_permutation, prev_permutation

  ⇑

---