Std :: sort by unary mapping

Question

The C ++ Standard Library suggests passing Comparator to std::sort. However, I have many cases in my code where I want to sort a list of objects Tusing a function f. Such a comparative example would be valid:

bool compare(const T& a, const T& b) {
  return f(a) < f(b);
}

This is not optimal. fevaluates slowly but returns the same value for each call with the same object T. So what I would prefer to do is calculate fonce for each object in the range, and then use these results to sort them.

My goal is to write this function (which I could not do):

template <typename IterT, typename Transformation>
void sort(IterT left, IterT right, Transformation f) { /* ? */ }

So after this call f(*iter) <= f(*std::next(iter))for everyone iterin the sequence leftbefore right.

In addition, the function must satisfy the following requirements:

• Does not allocate any additional type objects T.
• Repeatedly evaluates fsmoothly std::distance(left, right).
• Maintains the overall complexity of O (n log n).
• Must be implemented in terms of std :: sort. Of course, I could solve this problem by implementing my own type of merge, but I would like to avoid this.

(preferably C ++ 11, C ++ 14 is also good)

Answer 1

, ++ .. , Schwartzian ++ 14 . , -, std::sort ( , , TS), . sort, :

#include <cpp-sort/adapters/schwartz_adapter.h>
#include <cpp-sort/sorters/default_sorter.h>

template <typename IterT, typename Transformation>
void sort(IterT left, IterT right, Transformation f)
{
    using sorter = cppsort::schwartz_adapter<cppsort::default_sorter>;
    sorter{}(left, right, f);
}

[left, right) std::distance(left, right), it f(*it). (default_sorter , ), . , , .

, . , . , , , .

, , :

• T ( f T, f).
• f std::distance(left, right) .
• O (n log n), O (n log n).
• , : std::sort, std::sort , , .

Answer 2

std::sort, , T.

:

struct Foo {
    int value;
};

// Replace with your CPU time intensive f() function
int evaluate(const Foo& foo) {
    std::cout << "Evaluating complex function on an instance of Foo..." << std::endl;
    return foo.value;
}

bool compare(const Foo& left, const Foo& right) {
    static std::unordered_map<Foo, int> cache;
    auto leftIt = cache.find(left);
    auto rightIt = cache.find(right);
    if (leftIt == cache.end())
        leftIt = cache.emplace(left, evaluate(left)).first;
    if (rightIt == cache.end())
        rightIt = cache.emplace(right, evaluate(right)).first;
    return (*leftIt).second < (*rightIt).second;
}

: https://gist.github.com/PandarinDev/ee75b095c4cc256a88496f1985bf57ba

evaluate(const Foo&); (f(T) ) N , N = the number of unique instances of Foo.

: , T , - , - , .