Пространства имён
Варианты
Действия

cpp/algorithm/max element — различия между версиями

Материал из cppreference.com
< cpp‎ | algorithm
м
Строка 3: Строка 3:
 
{{dcl begin}}
 
{{dcl begin}}
 
{{dcl header | algorithm}}
 
{{dcl header | algorithm}}
−
{{dcl | num=1 |
+
{{dcl | num=1
−
template< class ForwardIt >
+
|
−
ForwardIt max_element( ForwardIt first, ForwardIt last );
+
template< class ForwardIt >  
 +
ForwardIt max_element(ForwardIt first, ForwardIt last);
 
}}
 
}}
−
{{dcl | num=2 |
+
{{dcl
 +
 +
 +
 +
 +
| num= 2
 +
 +
 +
 +
|
 
template< class ForwardIt, class Compare >
 
template< class ForwardIt, class Compare >
−
ForwardIt max_element( ForwardIt first, ForwardIt last, Compare comp );
+
ForwardIt max_element(ForwardIt first, ForwardIt last, Compare );
 
}}
 
}}
 +
 +
 +
 +
 +
 +
 +
 +
 
{{dcl end}}
 
{{dcl end}}
  
−
Находит наибольший элемент в диапазоне {{tt|[first, last)}}. Первая версия использует {{c|operator<}} для сравнения значений, вторая — переданную функцию сравнения {{tt|comp}}.
+
Находит наибольший элемент в диапазоне {{tt|[first, last)}}.  
 +
 
 +
{{|operator<}}
 +
{{tt|comp}}
 +
.
  
 
===Параметры===
 
===Параметры===
 
{{par begin}}
 
{{par begin}}
−
{{par | first, last | однонаправленные итераторы, задающие диапазон }}
+
{{par | first, last | итераторы, диапазон
−
{{par cmp | cmp | p1=ForwardIt | {{tt|*a}} ''меньше'' {{tt|*b}}}}
+
}}
 +
{{par cmp | cmp | p1=ForwardIt }}  
 
{{par hreq}}
 
{{par hreq}}
 
{{par req concept | ForwardIt | ForwardIterator}}
 
{{par req concept | ForwardIt | ForwardIterator}}
Строка 24: Строка 47:
  
 
===Возвращаемое значение===
 
===Возвращаемое значение===
−
Итератор, указывающий на наибольший элемент в диапазоне [first, last). Если несколько элементов в диапазоне эквивалентны наибольшему, то возвращается итератор на первый такой элемент. Возвращает last, если диапазон пуст.
+
Итератор, указывающий на наибольший элемент в диапазоне [first, last). Если несколько элементов в диапазоне эквивалентны наибольшему , то возвращается итератор на первый такой элемент. диапазон пуст.  
  
 
===Сложность===
 
===Сложность===
 
В точности {{math|max(N-1,0)}} сравнений, где {{c|N {{=}} std::distance(first, last)}}.
 
В точности {{math|max(N-1,0)}} сравнений, где {{c|N {{=}} std::distance(first, last)}}.
 +
 +
 +
  
 
===Возможная реализация===
 
===Возможная реализация===
Строка 49: Строка 75:
 
  | 2=
 
  | 2=
 
template<class ForwardIt, class Compare>
 
template<class ForwardIt, class Compare>
−
ForwardIt max_element(ForwardIt first, ForwardIt last,
+
ForwardIt max_element(ForwardIt first, ForwardIt last,  
−
                            Compare comp)
+
Compare )
 
{
 
{
 
     if (first == last) {
 
     if (first == last) {
Строка 58: Строка 84:
 
     ++first;
 
     ++first;
 
     for (; first != last; ++first) {
 
     for (; first != last; ++first) {
−
         if (comp(*largest, *first)) {
+
         if ((*largest, *first)) {
 
             largest = first;
 
             largest = first;
 
         }
 
         }
Строка 82: Строка 108:
 
int main()
 
int main()
 
{
 
{
−
     std::vector<int> v{ 3, 1, -14, 1, 5, 9 };
+
     std::vector<int> v{ 3, 1, -14, 1, 5, 9 };  
 
     std::vector<int>::iterator result;
 
     std::vector<int>::iterator result;
  
 
     result = std::max_element(v.begin(), v.end());
 
     result = std::max_element(v.begin(), v.end());
−
     std::cout << "max element at: " << std::distance(v.begin(), result) << '\n';
+
     std::cout << ": " << std::distance(v.begin(), result) << '\n';
  
 
     result = std::max_element(v.begin(), v.end(), abs_compare);
 
     result = std::max_element(v.begin(), v.end(), abs_compare);
−
     std::cout << "max element (absolute) at: " << std::distance(v.begin(), result);
+
     std::cout << "() : " << std::distance(v.begin(), result);
 
}
 
}
 
  | output=
 
  | output=
−
max element at: 5
+
: 5
−
max element (absolute) at: 2
+
() : 2
 
}}
 
}}
  
Строка 101: Строка 127:
 
{{dsc inc | cpp/algorithm/dsc minmax_element}}
 
{{dsc inc | cpp/algorithm/dsc minmax_element}}
 
{{dsc inc | cpp/algorithm/dsc max}}
 
{{dsc inc | cpp/algorithm/dsc max}}
 +
 
{{dsc end}}
 
{{dsc end}}
  
−
[[de:cpp/algorithm/max element]]
 
 
[[en:cpp/algorithm/max element]]
 
[[en:cpp/algorithm/max element]]
 +
 
[[es:cpp/algorithm/max element]]
 
[[es:cpp/algorithm/max element]]
 
[[fr:cpp/algorithm/max element]]
 
[[fr:cpp/algorithm/max element]]

Версия 06:47, 29 января 2018

 
C++
Поддержка компилятором
Автономные и размещённые реализации
Язык
Стандартная библиотека
Заголовки стандартной библиотеки
Требования к именованию
Макросы тестирования функциональности (C++20)
Поддержка языка
Библиотека концептов (C++20)
Библиотека метапрограммирования (C++11)
Библиотека диагностики
Библиотека общих утилит
Библиотека строк
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека численных данных
Библиотека ввода/вывода
Библиотека локализаций
Регулярные выражения (C++11)
Атомарные операции (C++11)
Библиотека поддержки конкуренции (C++11)
Библиотека файловой системы (C++17)
Технические спецификации
Указатель символов
Внешние библиотеки
 
Библиотека алгоритмов
Ограниченные алгоритмы и алгоритмы над диапазонами (C++20)
Ограниченные алгоритмы, например ranges::copy, ranges::sort, ...
Политики исполнения (C++17)
(C++17)  
Немодифицирующие операции над последовательностями
(C++11)(C++11)(C++11)
(C++17)
Модифицирующие операции над последовательностями
Операции разбиения
Операции сортировки
(C++11)
(C++11)
Операции двоичного поиска
Операции с наборами (в отсортированных диапазонах)
Операции с кучей
(C++11)
(C++11)
Операций минимума/максимума
max_element
(C++11)
(C++11)
(C++17)

Операции перестановки
Числовые операции
Операции с неинициализированной памятью
(C++17)
(C++17)
(C++17)
(C++20)
Библиотека C
 
Определено в заголовочном файле <algorithm>
(1)
template< class ForwardIt >
ForwardIt max_element(ForwardIt first, ForwardIt last);
 (до C++17)
template< class ForwardIt >
constexpr ForwardIt max_element(ForwardIt first, ForwardIt last);
 (начиная с C++17)
template< class ExecutionPolicy, class ForwardIt >
ForwardIt max_element(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last);
 (2) (начиная с C++17)
(3)
template< class ForwardIt, class Compare >
ForwardIt max_element(ForwardIt first, ForwardIt last, Compare cmp);
 (до C++17)
template< class ForwardIt, class Compare >
constexpr ForwardIt max_element(ForwardIt first, ForwardIt last, Compare cmp);
 (начиная с C++17)
template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt max_element(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare cmp);
 (4) (начиная с C++17)

Находит наибольший элемент в диапазоне [first, last).

1) Элементы сравниваются с помощью operator<.
3) Элементы сравниваются с помощью переданной бинарной функции компаратора comp.
2,4) Аналогично (1,3), но выполнение происходит согласно policy. Эти перегрузки не участвуют в разрешении перегрузок кроме случая, когда std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> равен true.

Содержание

Параметры

first, last — forward-итераторы, определяющие диапазон для обработки
policy — используемая политика выполнения. Подробнее смотрите политика выполнения.
cmp — объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй.

Определение сравнения должно быть эквивалентно:

bool cmp(const Type1 &a, const Type2 &b);

Использование noexcept (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по const&, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже const) Type1 и Type2 независимо от категории значений (таким образом, Type1& не допускается, равно как и Type1, если только для Type1 перемещение не эквивалентно копированию (начиная с C++11)). Типы Type1 и Type2 должны быть таковы, что объект типа ForwardIt может быть разыменован и затем неявно преобразован в оба из них.

Требования к типам
-
ForwardIt должен соответствовать требованиям ForwardIterator.

Возвращаемое значение

Итератор, указывающий на наибольший элемент в диапазоне [first, last). Если несколько элементов в диапазоне эквивалентны наибольшему элементу, то возвращается итератор на первый такой элемент. Если диапазон пуст, то возвращается last.

Сложность

В точности max(N-1,0) сравнений, где N = std::distance(first, last).

Исключения

Перегрузки с параметром шаблона по имени ExecutionPolicy сообщают об ошибках следующим образом:

  • Если выполнение функции, вызванной как часть алгоритма, вызывает исключение и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любой другой ExecutionPolicy поведение определяется реализацией.
  • Если алгоритму не удаётся выделить память, генерируется std::bad_alloc.

Возможная реализация

Первый вариант 
template<class ForwardIt>
ForwardIt max_element(ForwardIt first, ForwardIt last)
{
    if (first == last) {
        return last;
    }
    ForwardIt largest = first;
    ++first;
    for (; first != last; ++first) {
        if (*largest < *first) {
            largest = first;
        }
    }
    return largest;
}
Второй вариант 
template<class ForwardIt, class Compare>
ForwardIt max_element(ForwardIt first, ForwardIt last, 
                      Compare cmp)
{
    if (first == last) {
        return last;
    }
    ForwardIt largest = first;
    ++first;
    for (; first != last; ++first) {
        if (cmp(*largest, *first)) {
            largest = first;
        }
    }
    return largest;
}

Пример

Запустить этот код
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
 
static bool abs_compare(int a, int b)
{
    return (std::abs(a) < std::abs(b));
}
 
int main()
{
    std::vector<int> v{ 3, 1, -14, 1, 5, 9 }; 
    std::vector<int>::iterator result;
 
    result = std::max_element(v.begin(), v.end());
    std::cout << "индекс максимального элемента: " << std::distance(v.begin(), result) << '\n';
 
    result = std::max_element(v.begin(), v.end(), abs_compare);
    std::cout << "индекс максимального (по модулю) элемента: " << std::distance(v.begin(), result);
}

Вывод: 

индекс максимального элемента: 5
индекс максимального (по модулю) элемента: 2

См. также

 возвращает наименьший элемент в диапазоне
(шаблон функции) [править]
(C++11)
 возвращает наименьший и наибольший элементы в диапазоне
(шаблон функции) [править]
возвращает большее из заданных значений
(шаблон функции) [править]
Источник — «https://ru.cppreference.com/mwiki/index.php?title=cpp/algorithm/max_element&oldid=42661»