A replacement method is not that easy to do in general without adding some runtime overhead that you would not have for single hand-crafted solutions for min_element, max_element etc. The problem is that for memoizing you always have to know what value you should memoize. "The last accessed" does not really make sense in this context since you will always access two elements for a compare.
So if your memoization only works on the projection (agnostic with regards to how it is used in a comparison) it would need two slots for cached return values, two slots for saving the arguments that create these return values and an indication for which should be overridden next.
And even that may not be enough. I am not sure in which way there sequence points in calls to <, but I think that there aren't any in a call to a comp(_,_) function. So comparing a, b, c can use comp(f(a), f(b)) and comp(f(c), f(a)) and may execute that in order f(a), f(b), f(c), f(a). Here, memoizing with two slots would not be enough.
Having established that we cannot really be agnostic with regards to the comparison function, how about we try it with access to it? Well, then we have another problem. Take this simple implementation of a memoizer. std::min_element always packs the current minimum in the right hand side of the comparison and it stays there if the result is false (standard quote).
#include <type_traits>
#include <optional>
#include <utility>
#include <algorithm>
#include <iostream>
template<class ArgType, class Func, class Comp>
struct Memoizer {
Memoizer(Func func, Comp comp) : m_func(std::move(func)), m_comp(std::move(comp)) {}
[[nodiscard]] constexpr bool operator()(const ArgType &lhs, const ArgType &rhs) {
if (!m_cache) {
m_cache = std::invoke(m_func, rhs);
}
auto temp = std::invoke(m_func, lhs);
if (m_comp(temp, *m_cache)) {
m_cache = std::move(temp);
return true;
}
return false;
}
using result_t = std::invoke_result_t<Func, ArgType>;
Func m_func;
Comp m_comp;
private:
std::optional<result_t> m_cache;
};
template<class ArgType, class Func, class Comp>
auto make_memoizer(Func&& f, Comp&& c) -> Memoizer<ArgType, Func, Comp> {
return {std::forward<Func>(f), std::forward<Comp>(c)};
}
int main() {
int arr[] = {2,3,1,5,4};
auto memo = make_memoizer<int>(std::negate{}, std::less{});
auto min = std::min_element(std::begin(arr), std::end(arr), memo);
auto max = std::max_element(std::begin(arr), std::end(arr), memo);
std::cout << "Min: " << -*min << " (Should be: " << -*std::max_element(std::begin(arr), std::end(arr)) << ")\n";
std::cout << "Max: " << -*max << " (Should be: " << -*std::min_element(std::begin(arr), std::end(arr)) << ")\n";
}
As you can see, max_element does it the other way round and hence we obtain a false result. Now you can template the whole thing again on which side to memoize in which case, but that is just a nicely written invitation for bugs because you will use the wrong variant for the wrong algorithm. Further that just won't work for minmax_element. And at that point writing seperate implementations for min_element and max_element is just easier and safer.
There is still the option to write an iterator adaptor that calls the function on the first *iter and memoizes it for further *iter calls. But I does not seem that the standard gives any guarantees to how the iterators are called so I am not exactly sure if we can guarantee that the function calls are as small as they can be.
This is a very bare bones implementation of such an memoizing iter. You should probably use boost or a similar library to write iterator adaptors cause otherwise they are a pain in the neck with everything they have to foward.
#include <type_traits>
#include <optional>
#include <utility>
#include <algorithm>
#include <iostream>
#include <iterator>
template<class Func, class Iter>
struct MemoIter {
using result_t = std::invoke_result_t<Func, decltype(*std::declval<Iter>())>;
using iterator_category = typename std::iterator_traits<Iter>::iterator_category;
auto operator*() {
if(!m_cache) {
m_cache = m_func(*m_iter);
}
return *m_cache;
}
auto operator++() {
invalidate_cache();
++m_iter;
return *this;
}
auto operator++(int) {
auto ret = MemoIter(m_iter, invalidate_cache(), m_func);
++m_iter;
return ret;
}
MemoIter(Iter iter, Func func) : m_iter(iter), m_func(func) {}
explicit MemoIter(Iter iter) : MemoIter(iter, {}) {}
friend bool operator==(const MemoIter& lhs, const MemoIter& rhs) {
return lhs.m_iter == rhs.m_iter;
}
friend bool operator!=(const MemoIter& lhs, const MemoIter& rhs) {
return lhs.m_iter != rhs.m_iter;
}
private:
auto invalidate_cache() {
auto ret = std::move(m_cache);
m_cache.reset();
return ret;
}
MemoIter(Iter iter, std::optional<result_t>&& cache, Func func) : m_iter(iter), m_cache(std::move(cache)), m_func(func) {}
Iter m_iter;
std::optional<result_t> m_cache;
Func m_func;
};
int main() {
int arr[] = {2,3,1,5,4};
auto begin = MemoIter(std::begin(arr), std::negate<>{});
auto end = MemoIter(std::end(arr), std::negate<>{});
auto min = std::min_element(begin, end);
auto max = std::max_element(begin, end);
std::cout << "Min: " << *min << " (Should be: " << -*std::max_element(std::begin(arr), std::end(arr)) << ")\n";
std::cout << "Max: " << *max << " (Should be: " << -*std::min_element(std::begin(arr), std::end(arr)) << ")\n";
}
ADDENDUM: Concerning C++20. The standard explicitly specifies that the number of projection operations is exactly twice the number of comparisons, so the not only the example implementation but also the standard does not give the possibility of caching for this. (Of course, if the compiler could prove that there is no side effect to the projection, it could cache due to the as-if-rule, but that is a big if). As to the why: As you see, memoization is not that easy. You have still further problems if the iterator returns some kind of proxy that may be invalidated in between comparisons. So, just calling the projection more often is more general, easier and also more predictable (you know the number of calls to your projection to be 2*range.size() - 1; if you memoize, it can depend on the order of the elements in your range and whatnot).
