Алгоритмы определения минимума и максимума. Пример

---

Содержание

• 1. Алгоритм min. Поиск минимума между двумя значениями
• 2. Алгоритм min_element. Поиск минимального элемента в наборе значений
• 3. Алгоритм max. Поиск максимума между двумя значениями
• 4. Алгоритм max_element. Поиск максимума в последовательности
• 5. Алгоритм lexicographical_compare. Сравнить поэлементно 2 последовательности
• Связанные темы

---

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

1. Алгоритм min. Поиск минимума между двумя значениями

Алгоритм min сравнивает два объекта и возвращает меньший из них. Критерий сравнения элементов может быть задан предикатом.
Алгоритм имеет несколько перегруженных реализаций

template <class Type>
  constexpr const Type& min(
  const Type& left,
  const Type& right);

template <class Type, class Pr>
  constexpr const Type& min(
  const Type& left,
  const Type& right,
  BinaryPredicate pred);

template <class Type>
  constexpr Type min(
  initializer_list<Type> ilist);

template <class Type, class Pr>
  constexpr Type min(
  initializer_list<Type> ilist,
  BinaryPredicate pred);

где

• left, right – сравниваемые объекты;
• pred – предикат, используемый для сравнения двух объектов. Это может быть также лямбда-выражение;
• inlist – объект, содержащий элементы для сравнения.

Пример.

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

// Функция сравнения.
// Если знак < заменить на >, то будет поиск максимума.
bool MoreThan(int a, int b)
{
  return a < b;
}

void main()
{
  // Алгоритм min – поиск минимума между двумя значениями
  // 1. Поиск между значениями типа double
  double minDouble = min(2.8, 3.6);
  cout << "minDouble = " << minDouble << endl;

  // 2. Поиск между целыми числами,
  // используется функция сравнения
  int minInt = min(29, 36, MoreThan);
  cout << "minInt = " << minInt << endl;
}

Результат

minDouble = 2.8
minInt = 29

  ⇑

2. Алгоритм min_element. Поиск минимального элемента в наборе значений

Алгоритм выполняет поиск малейшего элемента в заданном диапазоне. Критерий упорядочения может быть задан бинарным предикатом.

Наиболее употребляемые перегруженные реализации алгоритма

template <class ForwardIterator>
constexpr ForwardIterator min_element(
  ForwardIterator first,
  ForwardIterator last );

template <class ForwardIterator, class Compare>
constexpr ForwardIterator min_element(
  ForwardIterator first,
  ForwardIterator last,
  Compare pred);

где

• first, last – прямые итераторы, указывающие соответственно на первый и последний элемент диапазона;
• pred – бинарный предикат, который задает условие, когда один элемент меньше другого. Если первый элемент меньше другого, то предикат должен возвращать true.

Пример.

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

// Функция сравнения.
// Если знак < заменить >, то будет поиск максимума.
bool MoreThan(int a, int b)
{
  return a < b;
}

void main()
{
  // Алгоритм min_element - поиск минимума в наборе значений
  // 1. Поиск в векторе чисел типа double
  vector<double> V = { 2.8, 1.6, 2.9, 3.3, 4.5, -1.8, -2.2 };
  vector<double>::iterator itV = min_element(V.begin(), V.end());
  cout << "min_element(V) = " << *itV << endl;

  // 2. Поиск между целыми числами,
  // используется функция сравнения
  list<int> L = { 2, 3, 8, -4, 1, 3, -2 };
  list<int>::iterator itL = min_element(L.begin(), L.end(), MoreThan);
  cout << "min_element(L) = " << *itL << endl;

  // 3. Поиск между целыми числами,
  // используется лямбда-выражение
  itL = min_element(L.begin(), L.end(), [](int a, int b) { return a < b; });
  cout << "min_element(L) = " << *itL << endl;
}

Результат

min_element(V) = -2.2
min_element(L) = -4
min_element(L) = -4

  ⇑

3. Алгоритм max. Поиск максимума между двумя значениями

Алгоритм max сравнивает два объекта и возвращает больший из них. В алгоритме разрешается задавать критерий упорядочения с помощью бинарного предиката.

Перегруженные реализации алгоритма следующие

template <class Type>
constexpr Type& max(
  const Type& left,
  const Type& right);

template <class Type, class Pr>
  constexpr Type& max(
  const Type& left,
  const Type& right,
  BinaryPredicate pred);

template <class Type>
constexpr Type& max (
  initializer_list<Type> ilist);

template <class Type, class Pr>
constexpr Type& max(
  initializer_list<Type> ilist,
  BinaryPredicate pred);

где

• left, right – соответственно первый и второй из сравниваемых объектов;
• pred – бинарный предикат, задающий способ сравнения объектов;
• ilist – список с объектами, которые нужно сравнить.

Пример.

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

// Функция сравнения.
// Если знак < заменить >, то будет поиск минимума.
bool LessThan(int a, int b)
{
  return a < b;
}

void main()
{
  // Алгоритм max – поиск максимума между двумя значениями
  // 1. Поиск между значениями типа double
  double maxDouble = max(2.8, 3.6);
  cout << "maxDouble = " << maxDouble << endl;

  // 2. Поиск между целыми числами, используется функция сравнения
  int maxInt = max(29, 36, LessThan);
  cout << "maxInt = " << maxInt << endl;
}

Результат

maxDouble = 3.6
maxInt = 36

  ⇑

4. Алгоритм max_element. Поиск максимума в последовательности

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

Алгоритм имеет несколько перегруженных реализаций, наиболее распространённые из которых следующие

template <class ForwardIterator>
constexpr ForwardIterator max_element(
  ForwardIterator first,
  ForwardIterator last );

template <class ForwardIterator, class Compare>
constexpr ForwardIterator max_element(
  ForwardIterator first,
  ForwardIterator last,
  Compare pred );

здесь

• first, last – прямые итераторы, которые указывают соответственно на первый и последний элемент рассматриваемого диапазона;
• pred – бинарный предикат, который задает условие, когда один элемент меньше другого. Если первый элемент меньше второго, то предикат должен возвращать true.

Пример.

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

// Функция сравнения.
// Если знак < заменить >, то будет поиск минимума.
bool MoreThan(int a, int b)
{
  return a < b;
}

void main()
{
  // Алгоритм max_element - поиск максимума в наборе значений.
  // 1. Поиск в векторе чисел типа double
  vector<double> V = { 2.8, 1.6, 2.9, 3.3, 4.5, -1.8, -2.2 };
  vector<double>::iterator itV = max_element(V.begin(), V.end());
  cout << "max_element(V) = " << *itV << endl;

  // 2. Поиск между целыми числами,
  // используется функция сравнения
  list<int> L = { 2, 3, 8, -4, 1, 3, -2 };
  list<int>::iterator itL = max_element(L.begin(), L.end(), MoreThan);
  cout << "max_element(L) = " << *itL << endl;

  // 3. Поиск между целыми числами,
  // используется лямбда-выражение
  itL = max_element(L.begin(), L.end(), [](int a, int b) { return a < b; });
  cout << "min_element(L) = " << *itL << endl;
}

Результат

max_element(V) = 4.5
max_element(L) = 8
min_element(L) = 8

  ⇑

5. Алгоритм lexicographical_compare. Сравнить поэлементно 2 последовательности

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

Распространенные реализации алгоритма следующие

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

template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  Compare pred );

где

• first1, last1 – итераторы, задающие диапазон элементов первой последовательности;
• first2, last2 – итераторы, задающие пределы второй последовательности.

Поэлементное сравнение последовательностей происходит по следующим правилам:

• находятся первые 2 неравных соответствующих элемента и результат их сравнения является результатом сравнения двух последовательностей;
• если элементы последовательностей равны, то сравниваются длины последовательностей. Больше считается та последовательность, количество элементов в которой больше;
• если последовательности идентичны и имеют одинаковое количество элементов, то результатом сравнения является false.

Пример.

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

int main()
{
  // Алгоритм lexicographical_compare - сравнивает 2 последовательности поэлементно,
  // если последовательности идентичны - результат false.

  // 1. Объявить два вектора
  vector<double> V1 = { 1.1, 2.2, 2.7, 2.8, 3.2, 5.5 };
  vector<double> V2 = { 1.1, 2.2, 2.7, 2.8, 3.2, 5.5 };

  // 2. Вызвать алгоритм, получить результат
  bool res = lexicographical_compare(V1.begin(), V1.end(), V2.begin(), V2.end());

  // 3. Обработать результат
  if (res)
    cout << "true => V1 != V2" << endl;
  else
    cout << "false => V1 == V2" << endl;
}

Результат

false => V1 == V2

  ⇑

---

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

• Алгоритмы перестановок. Алгоритмы 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
• Модифицирующие алгоритмы. Часть 1. Алгоритмы изменяющие значения элементов последовательности. Алгоритмы for_each, transform, fill, fill_n, generate, generate_n
• Модифицирующие алгоритмы. Часть 2. Алгоритмы обмена значениями элементов последовательности. Алгоритмы swap, swap_ranges, iter_swap

  ⇑

---