优化argmin：如何让评分函数仅被每个元素调用一次？

咱们先明确场景：手里有一堆Item对象，还有个计算成本很高的score函数，现在要找出评分最低的元素。用标准的std::min_element虽然简单，但它会重复调用score——毕竟编译器没法确定这个函数是不是纯函数（会不会每次调用返回不同结果、有没有副作用）。

除了记忆化，这里有几个直观易读的方案，部分甚至和std::min_element的使用体验几乎一致：

方案1：预计算评分-元素对，再找最小值 #

这是最直白的思路：先遍历所有元素，把每个元素和它的评分存成配对，再对这些配对找评分最小的那个。每个元素只算一次score，逻辑一目了然：

#include <vector>
#include <algorithm>

// 预计算所有元素的评分，存为（评分，元素指针）的配对
std::vector<std::pair<double, const Item*>> scored_items;
scored_items.reserve(items.size()); // 预分配空间避免扩容开销
for (const auto& item : items) {
    scored_items.emplace_back(score(item), &item);
}

// 用std::min_element找到评分最小的配对
const auto min_entry = std::min_element(scored_items.begin(), scored_items.end());
const Item* argmin = min_entry->second;

如果不想额外占用vector的内存，也可以手动遍历跟踪最小值，省掉中间容器：

if (items.empty()) {
    // 处理空集合的边界情况，比如返回nullptr或抛出异常
    return nullptr;
}

double current_min_score = score(items[0]);
const Item* argmin = &items[0];

for (size_t i = 1; i < items.size(); ++i) {
    const auto& item = items[i];
    const double item_score = score(item);
    if (item_score < current_min_score) {
        current_min_score = item_score;
        argmin = &item;
    }
}

这种写法内存效率更高，逻辑清晰，适合数据量较大的场景。

方案2：封装自定义算法，模仿std::min_element风格 #

如果想让调用方式和标准库算法保持一致，咱们可以自己写一个模板函数，内部处理评分的单次计算逻辑：

#include <iterator>

template <typename ForwardIterator, typename ScoreFunction>
ForwardIterator min_element_single_score(ForwardIterator first, ForwardIterator last, ScoreFunction score_func) {
    if (first == last) {
        return last;
    }

    ForwardIterator min_it = first;
    double min_score = score_func(*first);

    ++first;
    for (; first != last; ++first) {
        const double current_score = score_func(*first);
        if (current_score < min_score) {
            min_score = current_score;
            min_it = first;
        }
    }

    return min_it;
}

调用时和std::min_element一模一样，熟悉标准库的人一眼就能懂：

const auto argmin = min_element_single_score(items.begin(), items.end(), score);

这个方案完美贴合标准库的使用习惯，代码可读性拉满，还保证每个元素只被评分一次。

方案3：C++20+用Range库简化代码 #

如果你的项目已经用上了C++20，可以结合Range视图简化预计算步骤，代码更紧凑：

#include <ranges>
#include <algorithm>

// 用transform视图生成（评分，元素指针）的序列
auto scored_view = items | std::views::transform([](const Item& item) {
    return std::make_pair(score(item), &item);
});

// 找到评分最小的条目
const auto min_entry = std::ranges::min_element(scored_view, [](const auto& a, const auto& b) {
    return a.first < b.first;
});

const Item* argmin = min_entry->second;

这里的transform会遍历每个元素一次并计算评分，所以每个元素的score只调用一次，同时代码比手动写vector更简洁。

内容的提问来源于stack exchange，提问作者YSC