STL算法 | 区间最值 max_element、min_element

布满荆棘的人生 2022-09-06 14:24 95阅读 0赞

std::max\_element 定义于头文件 <algorithm> 寻找范围 \[first, last) 中的最大元素。。

**函数原型**

第一种：用 operator< 比较元素
    // 参数：obj.begin(), obj.end()
    template< class ForwardIt >
    ForwardIt max_element(ForwardIt first, ForwardIt last );
    
    // 参数：obj.begin(), obj.end()
    // 返回常量
    template< class ForwardIt >
    constexpr ForwardIt max_element(ForwardIt first, ForwardIt last );
    
    第二种：用给定的二元比较函数 comp 比较元素。
    // 参数：obj.begin(), obj.end(), 二元函数/仿函数/lambda表达式均可（返回值bool）
    template< class ForwardIt, class Compare >
    ForwardIt max_element(ForwardIt first, ForwardIt last, Compare comp );
    
    // 返回常数
    template< class ForwardIt, class Compare >
    constexpr ForwardIt max_element(ForwardIt first, ForwardIt last, Compare comp );

**参数**  
first, last - 定义要检验范围的向前迭代器  
comp - 比较函数对象（即满足比较 (Compare) 要求的对象），**若首个参数小于第二个，则返回 true** 。

> 比较函数的签名应等价于如下：
> 
> > bool cmp(const Type1 &a, const Type2 &b);
> 
> 虽然签名不必有 const & ，函数也不能修改传递给它的对象，而且必须接受（可为 const 的）类型 Type1 与 Type2 的值，无关乎值类别（从而不允许 Type1 & ，亦不允许 Type1 ，除非 Type1 的移动等价于复制 (C++11 起)）。  
> 类型 Type1 与 Type2 必须使得 ForwardIt 类型的对象能在解引用后隐式转换到这两个类型。

**可能的实现方式：**

//版本一
    template<class ForwardIt>
    ForwardIt max_element(ForwardIt first, ForwardIt last)
    {
        
        if (first == last) {
        	// 没有元素，返回last
            return last;
        }
        ForwardIt largest = first;	// 前一个元素
        ++first;					// 第二个元素
        for (; first != last; ++first) {
        
            if (*largest < *first) {
        	// 如果第一个元素，小于第二个元素，则largest更新
                largest = first;
            }
        }
        return largest;
    }
    //版本二
    template<class ForwardIt, class Compare>
    ForwardIt max_element(ForwardIt first, ForwardIt last, 
                          Compare comp)
    {
        
        if (first == last) {
        
            return last;
        }
        ForwardIt largest = first;
        ++first;
        for (; first != last; ++first) {
        
            if (comp(*largest, *first)) {
        	// 这里使用自定义的规则，去取值
                largest = first;
            }
        }
        return largest;
    }

**示例一：获得数组中最大的元素**  
如下：给出普通数组，向量数组，无序集合三种类型，都可以使用 max\_element 解最大值

int arr[] = {
         1,2,3,4,9,8,7,4,1,2 };
        int len = sizeof(arr) / sizeof(arr[0]);
        int* idx = max_element<int*>(arr, arr + len);
        // 模板参数会自动推演，等价于 int* idx = max_element(arr, arr + len);
        cout << "最大值为 arr[" << (idx - arr) << "] = " << *idx << endl;
        /*
        * 输出： 最大值为 arr[4] = 9
        */
    
        vector<int> vec(arr, arr + len);    // 用普通数组初始化vector<int>
        auto max_it = max_element<vector<int>::iterator>(vec.begin(), vec.end());
        // 模板参数会自动推演，等价于 auto max_it = max_element(vec.begin(), vec.end());
        cout << "最大值为 arr[" << distance(vec.begin(), max_it) << "] = " << *max_it << endl;
        /*
        * 输出： 最大值为 arr[4] = 9
        */
    
        unordered_set<int> u_set(vec.begin(), vec.end());   // 用vector<int>初始化unordered_set<int>
        auto max_sit = max_element<unordered_set<int>::iterator>(u_set.begin(), u_set.end());
        // 模板参数会自动推演，等价于 auto max_sit = max_element(u_set.begin(), u_set.end());
        cout << "最大值为 arr[" << distance(u_set.begin(), max_sit) << "] = " << *max_sit << endl;
        /*
        * 输出： 最大值为 arr[0] = 9
        */

**示例二：使用自定义二元谓词**

int arr[] = {
         1,2,3,4,9,8,7,4,1,2 };
        int len = sizeof(arr) / sizeof(arr[0]);
    
        // 案例一：默认是operator< 比较。即 less<>()
        // 如果我们，使用 operator> 比较，就成了寻找最小值的下标了。
        int* idx1 = max_element(arr, arr + len,std::greater<int>()); // 或std::greater<>()
        // 等价于 int* idx1 = max_element(arr, arr + len, [](const int a, const int b) {return a > b; });
        cout << "最小值为 arr[" << (idx1 - arr) << "] = " << *idx1 << endl;
        /*
        * 输出： 最小值为 arr[0] = 1 
        */
    
        // 案例二：使用greater<>()找最小值
        vector<int> vec(arr, arr + len);  
        auto no_max_it = max_element(vec.begin(), vec.end(),std::greater<int>());
        cout << "最小值为 arr[" << distance(vec.begin(), no_max_it) << "] = " << *no_max_it << endl;
        /*
        * 输出： 最小值为 arr[0] = 1
        */
    
        // 案例三：使用less<>()找最大值
        auto max_it = max_element(vec.begin(), vec.end(), std::less<int>());
        cout << "最大值为 arr[" << distance(vec.begin(), max_it) << "] = " << *max_it << endl;
        /*
        * 输出： 最大值为 arr[4] = 9
        */
    
        // 案例四：返回绝对值最大的小数
        vector<double> dvec{
         1.0,4.0,-3.6,9.1,-7.2,8.3,-10.9,9,9 };
        auto dmax_it = max_element(dvec.begin(), dvec.end(), [](double d1, double d2) {
        return fabs(d1) < fabs(d2); });
        cout << "绝对值最大值为 arr[" << distance(dvec.begin(), dmax_it) << "] = " << *dmax_it << endl;
        /*
        * 输出： 绝对值最大值为 arr[6] = -10.9
        */
    
        // 案例五：返回map中key最大的、value最大的
        unordered_map<int, int> mp;
        for (const auto& a : vec) // 1,2,3,4,9,8,7,4,1,2 
        {
        
            mp[a]++;
        }
    
        auto max_key = max_element(mp.begin(), mp.end());   // 默认按照key找最大值
        auto max_val = max_element(mp.begin(), mp.end(), [](const auto& m1, const auto& m2) {
        return m1.second < m2.second; });
       
        cout << "vec={";
        for_each(vec.begin(), vec.end(), [](const auto& v) {
        cout << v << ","; });
        cout <<  "}\n其中最大值为: {" << max_key->first << "}\t重复元素最多的为: {" << max_val->first << "} ×" << max_val->second << endl;
        /*
        * 输出：
        *   vec = { 1,2,3,4,9,8,7,4,1,2, }
        *   其中最大值为: {9}       重复元素最多的为: {1} ×2
        */

--------------------

min\_element 的用法与max\_element相似。

**参数**  
first, last - 定义要检验范围的向前迭代器  
comp - 比较函数对象（即满足比较 (Compare) 要求的对象），若a 小于 b ，则返回 true 。

**可能的实现**

// 版本一
    template<class ForwardIt>
    ForwardIt min_element(ForwardIt first, ForwardIt last)
    {
        
        if (first == last) return last;
     
        ForwardIt smallest = first;	// 前一个元素
        ++first;					// 第二个元素
        for (; first != last; ++first) {
        
            if (*first < *smallest) {
        	// 如果第二个元素小，则更新smallest的位置
                smallest = first;
            }
        }
        return smallest;
    }
    // 版本二
    template<class ForwardIt, class Compare>
    ForwardIt min_element(ForwardIt first, ForwardIt last, Compare comp)
    {
        
        if (first == last) return last;
     
        ForwardIt smallest = first;
        ++first;
        for (; first != last; ++first) {
        
            if (comp(*first, *smallest)) {
         // 使用自定义谓词比较
                smallest = first;
            }
        }
        return smallest;
    }

示例一：来自cppreference的示例

#include <algorithm>
    #include <iostream>
    #include <vector>
     
    int main()
    {
        
        std::vector<int> v{
        3, 1, 4, 1, 5, 9};
     
        std::vector<int>::iterator result = std::min_element(std::begin(v), std::end(v));
        std::cout << "min element at: " << std::distance(std::begin(v), result);
    }

输出：

min element at: 1