c++ - 使用 STL 算法缓存复杂的比较函数？

Question

我有一个很长的计算函数 f(T) -> int 和一个 T 的 vector v。任务是在应用 f 后找到最小元素。

一般来说，我会用

std::min_element(begin(v), end(v), [&f](auto a, auto b){ return f(a) < f(b); }

编译器是否尝试存储计算值(如果这有意义)，还是我必须手动存储？第二种情况:是否有使用STL算法手工完成的好的解决方案？

编辑:请注意，实现无法确保此优化，因为它仅获取比较函数而不是比较函数的结构(在本例中为一元函数)。

这也是一个更普遍的问题，因为在使用 STL 算法时经常会出现这个问题。如果我测量一个例子，我只能为一个特定的例子买保险。我感兴趣的是编译器是否尝试在一般情况下修复此问题(启用合理的优化)。如果不是，您可以在不重写算法的情况下解决这个问题吗？

编辑 2:我认为除了替换方法外，所有问题都得到了很好的回答。这应该满足它与(未实现的)函数具有相同的运行时间

std::min_element(begin(v), end(v), f);

存储最后访问的元素的值。此外，我想要一个适用于可以进行此优化的所有算法的解决方案。

使用 c++20，我们可以使用投影，但据我所知，建议的实现 https://en.cppreference.com/w/cpp/algorithm/ranges/min_element没有针对缓存进行优化(我想知道为什么，它不会让任何东西变慢，对吧？)。

Answer 1

Do compilers try to store the computed values (if that makes sense) or do I have to do that by hand?

一般这叫做memoization并且一般编译器不能为你做这件事。在特定情况下，内联可能允许优化器做一些聪明的事情。

如果您希望经常这样做，您可以编写一个自动内存功能包装器 - 它只需要保留一些(可能是有限的)存储量来跟踪先前遇到的输入的输出。然后你可以写类似的东西

auto mf = memoize(f);
std::min_element(begin(v), end(v), [&mf](auto a, auto b){ return mf(a) < mf(b); }

(请注意，假设当 mf 超出范围时其缓存值会丢失，您仍在明确决定该特定备忘录的持续时间)。

语言不会为你做这件事，因为有很多实现权衡(多少存储是合理的？如果返回值的复制构造函数在将它复制到你的备忘录存储时抛出异常会发生什么？) 没有任何明显好的默认值。