std::sort by unary mapping

Question

The C++ standard library offers to pass a Comparator to std::sort. However, I have many cases in my code where I want to sort a list of T objects by a function f. A comparator like this would be a valid option:

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

This is not optimal though. f is slow to evaluate but will return the same value for every call with the same T object. So what I would rather do is compute f once for every object in the range and then use those results to sort them.

My goal is to write this function (which I have not been able to do):

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

Such that after this call, f(*iter) <= f(*std::next(iter)) for all iter in the sequence left to right.

Furthermore, the function should satisfy these requirements:

• Does not allocate any additional objects of type T.
• Evaluates f exactly std::distance(left, right) many times.
• Maintains the overall complexity of O(n log n).
• Should be implemented in terms of std::sort. Of course I could solve this problem by implementing my own merge sort but that is something I would like to avoid.

(C++11 is preferred; C++14 is also ok)

Answer 1

So what you want is a C++ implementation of a Schwartzian transform. I don't have a simple solution in a few lines of code, but I did implement a Schwartzian transform utility in a C++14 library of mine. Unfortunately it relies on proxy iterators, which aren't handled by std::sort (at least not until the Ranges TS), but you can use any other sorter from the library instead. Here is how you could write the sort function mentioned in your question:

#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);
}

When called this way, the sorter will cross [left, right) and create std::distance(left, right) pairs associating an iterator it to f(*it). Then it will use the passed sorter (default_sorter in the example above, which is a pattern-defeating quicksort at the time of writing) to sort the collection of pairs. Proxy iterators are used under the hood so that elements of the original collection are swapped whenever pairs are swapped.

I wouldn't say it's quite simple, but it should solve your problem. If you don't want to rely on an external library, you can still take inspiration from the soure code. It is under a permissive license, so you can do pretty much whatever you want to with it if you need to use elements from it.

Anyway, it looks like it mostly satifies your requirements:

• It doesn't allocate additional instances of T (unless f returns a new instance of T since it stores the return value of f).
• It applies f exactly std::distance(left, right) prior to the actual sorting.
• It maintains the overall complexity of O(n log n) if used with an O(n log n) sorter.
• This latest bullet is the only one not being satisfied: it doesn't use std::sort because std::sort isn't smart enough as of today, but it can use equivalent algorithms without you having to write your own.