C / C++ / 系统课时

用 minmax_element 找极值

用 minmax_element 找极值

需要同时找到容器中的最小值和最大值时,分别调用 min_element 与 max_element 会重复遍历数据。std::minmax_element 能在一次算法调用中返回两个极值位置,还可以通过自定义比较器处理结构体等业务对象。

学习目标

  • 会使用 std::minmax_element 同时取得最小值和最大值的迭代器
  • 能为自定义对象提供正确的比较条件
  • 能处理空区间和重复极值,避免解引用无效迭代器

返回的是两个迭代器

std::minmax_element 定义在 <algorithm> 中,返回包含两个迭代器的 std::pair:第一个指向最小元素,第二个指向最大元素。因为拿到的是位置而不是值,所以既能读取极值,也能进一步计算元素下标或操作对应对象。

对于普通数值类型,只要元素支持默认的小于比较,就可以直接传入 begin() 和 end()。自定义对象如果没有符合业务含义的默认顺序,则应显式提供比较器。

为自定义对象指定比较条件

下面按商品价格同时寻找最低价与最高价商品,并使用 std::distance 得到它们在容器中的位置。

cpp
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

struct Product {
    std::string name;
    double price;
};

int main() {
    std::vector<Product> products{
        {"Keyboard", 49.90},
        {"Cable", 12.50},
        {"Adapter", 49.90}
    };

    const auto [min_it, max_it] = std::minmax_element(
        products.begin(), products.end(),
        [](const Product& a, const Product& b) {
            // 业务上的“大小”只比较价格,不比较商品名称。
            return a.price < b.price;
        }
    );

    const auto min_index = std::distance(products.begin(), min_it);
    const auto max_index = std::distance(products.begin(), max_it);

    std::cout << std::fixed << std::setprecision(2);
    std::cout << "min=" << min_it->name << ':' << min_it->price
              << ", index=" << min_index << '\n';
    std::cout << "max=" << max_it->name << ':' << max_it->price
              << ", index=" << max_index << '\n';
}

预期输出

text
min=Cable:12.50, index=1
max=Adapter:49.90, index=2

示例中的结构化绑定需要 C++17。使用较早标准时,也可以把结果保存为 std::pair,再通过 first 和 second 取得两个迭代器。

比较器必须表达严格的小于关系

比较器的含义应该是“a 是否严格排在 b 前面”。上例因此使用 a.price < b.price,而不是 a.price <= b.price。把“小于等于”作为比较条件会使相等元素之间也互相满足比较,破坏算法所要求的严格弱序关系。

如果业务希望按多个字段排序,可以在比较器中明确优先级。例如先比较价格,再比较名称。但极值的定义也会随比较规则改变,所以比较器必须真正代表当前业务所说的“最小”和“最大”。

重复极值的位置规则

当最小值出现多次时,minmax_element 返回第一个最小元素;当最大值出现多次时,则返回最后一个最大元素。示例中 Keyboard 与 Adapter 都是 49.90,因此最大值迭代器最终指向后出现的 Adapter。

这个细节在只关心极值数值时通常没有影响,但如果还要记录元素位置、修改对象或根据对象身份执行后续操作,就必须知道究竟返回了哪一个重复元素。

空区间不能解引用

对空区间调用 minmax_element 本身是合法的,此时返回的两个迭代器都会等于传入的 last。真正危险的是随后执行 *min_it、*max_it 或 min_it->member,因为结束迭代器不能解引用。

因此当容器可能为空时,应先使用 products.empty() 判断是否存在元素,再执行极值查找。对于通用迭代器代码,则可以在调用后检查返回的迭代器是否等于 last。

什么时候使用 minmax_element

如果最小值与最大值都需要,minmax_element 比分别调用 min_element 和 max_element 更直接,并且标准算法可以通过组合比较减少比较次数;整体时间复杂度仍为 O(n)O(n)。如果只需要一个方向的极值,单独使用 min_element 或 max_element 会更清楚。

使用时最需要记住两点:结果是迭代器,因此空区间不能解引用;自定义比较器必须表示严格的“小于”关系。掌握这两个边界后,就可以安全地把同一套算法应用到数值、结构体和其他自定义对象上。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 minmax_element 找极值

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通