std::minmax_element

来自cppreference.com
< cpp‎ | algorithm

 
 
算法库
执行策略 (C++17)
不修改的序列操作
(C++11)
(C++11)
(C++11)
(C++17)
修改的序列操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
二分查找操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
minmax_element
(C++11)
(C++17)

重排
数值操作
C 库
 
定义于头文件 <algorithm>
template< class ForwardIt >

std::pair<ForwardIt,ForwardIt>

    minmax_element( ForwardIt first, ForwardIt last );
(1)
template< class ForwardIt, class Compare >

std::pair<ForwardIt,ForwardIt>

    minmax_element( ForwardIt first, ForwardIt last, Compare comp );
(2)
发现最大和最小的范围内[first, last)元素。使用operator<的值进行比较的第一个版本,第二个版本使用给定的比较函数comp.
原文:
Finds the greatest and the smallest element in the range [first, last). The first version uses operator< to compare the values, the second version uses the given comparison function comp.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

目录

[编辑] 参数

first, last -
前向迭代器定义的范围检查
原文:
forward iterators defining the range to examine
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
cmp - 比较函数对象(即满足比较Compare)要求的对象),若 if *a is less than *b,则返回 ​true

比较函数的签名应等价于如下者:

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

签名不需要拥有 const & ,但函数对象必须不修改传递给它的对象。
类型 Type1Type2 必须使得 ForwardIt 类型的对象能在解引用后隐式转换到这两个类型。 ​

类型要求
-
ForwardIt 必须满足 ForwardIterator 的要求。

[编辑] 返回值

组成的一对迭代器的第一个元素的最小元素和一个迭代的最大元素作为第二。返回std::make_pair(first, first)的范围内是空的。如果几个元素是等价的最小的元素,则返回到第一个这样的元件的迭代器。如果有多个元素的最大元素是等价的,到最后这样的元素,则返回的迭代器.
原文:
a pair consisting of an iterator to the smallest element as the first element and an iterator to the greatest element as the second. Returns std::make_pair(first, first) if the range is empty. If several elements are equivalent to the smallest element, the iterator to the first such element is returned. If several elements are equivalent to the largest element, the iterator to the last such element is returned.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

[编辑] 复杂度

max(floor(3/2(N−1)), 0)应用程序的谓词,N = std::distance(first, last).
原文:
At most max(floor(3/2(N−1)), 0) applications of the predicate, where N = std::distance(first, last).
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

[编辑] 可能的实现

版本一
template<class ForwardIt>
std::pair<ForwardIt, ForwardIt> 
    minmax_element(ForwardIt first, ForwardIt last)
{
    typedef typename std::iterator_traits<ForwardIt>::value_type value_t;
    return std::minmax_element(first, last, std::less<value_t>());
}
版本二
template<class ForwardIt, class Compare>
std::pair<ForwardIt, ForwardIt> 
    minmax_element(ForwardIt first, ForwardIt last, Compare comp)
{
    std::pair<ForwardIt, ForwardIt> result(first, first);
 
    if (first == last) return result;
    if (++first == last) return result;
 
    if (comp(*first, *result.first)) {
        result.second = result.first;
        result.first = first;
    } else {
        result.second = first;
    }
    while (++first != last) {
        ForwardIt i = first;
        if (++first == last) {
            if (comp(*i, *result.first)) result.first = i;
            else if (!(comp(*i, *result.second))) result.second = i;
            break;
        } else {
            if (comp(*first, *i)) {
                if (comp(*first, *result.first)) result.first = first;
                if (!(comp(*i, *result.second))) result.second = i;
            } else {
                if (comp(*i, *result.first)) result.first = i;
                if (!(comp(*first, *result.second))) result.second = first;
            }
        }
    }
    return result;
}

[编辑] 示例

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v = { 3, 9, 1, 4, 2, 5, 9 };
 
    auto result = std::minmax_element(v.begin(), v.end());
    std::cout << "min element at: " << (result.first - v.begin()) << '\n';
    std::cout << "max element at: " << (result.second - v.begin()) << '\n';
}

输出:

min element at: 2
max element at: 6

[编辑] 另请参阅

返回区间内的最小元素
(函数模板) [编辑]
返回区间内的最大元素
(函数模板) [编辑]