std :: sort by unary mapping

Question

C++標準ライブラリでは、コンパレータをstd::sortに渡します。しかし、私はTオブジェクトのリストを関数fでソートしたいという私のコードに多くの場合があります。このようなコンパレータは有効なオプションです：

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

これは最適ではありません。 fは評価が遅くなりますが、同じTオブジェクトを持つすべてのコールで同じ値が返されます。ですから、範囲内のすべてのオブジェクトに対してfを1回計算し、それらの結果をソートすることです。

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

ように、このコールの後、シーケンスleft内のすべてのiterためf(*iter) <= f(*std::next(iter))rightへ：

私の目標は、（私がすることができていない）、この関数を記述することです。

さらに、関数がこれらの要件を満たす必要があります。

• はタイプTのいずれかの追加オブジェクトを割り当てません。
• f正確にはstd::distance(left, right)と評価されます。
• O（n log n）の全体的な複雑さを維持します。
• std :: sortに関して実装する必要があります。もちろん、私は自分のマージソートを実装することでこの問題を解決することができますが、それは避けたいものです。

（C++ 11が好ましく、C++ 14もOKです）

Answer 1

あなたが望むのは、Schwartzian transformのC++実装です。私はコードのいくつかの行で簡単な解決策はありませんが、私はSchwartzian transform utilityをC++ 14の私のライブラリに実装しました。残念ながら、それはstd::sort（少なくともRanges TSまでではない）によって処理されないプロキシイテレータに頼っていますが、代わりにライブラリの他のソータを使うことができます。このように呼ばれると、

#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)を渡り、f(*it)にイテレータitを関連付けるstd::distance(left, right)ペアを作成します。ここでは、あなたの質問に言及したsort関数を書くことができるかです。次に、渡されたソーター（上記の例ではdefault_sorter、書面ではpattern-defeating quicksort）を使用して、ペアのコレクションをソートします。フードの下でProxy iteratorsが使用されるため、ペアが交換されると元のコレクションの要素が交換されます。

私はそれが非常に簡単だとは言いませんが、あなたの問題を解決するはずです。外部のライブラリに依存したくない場合でも、the soure codeからインスピレーションを得ることができます。許可されたライセンスの下にあるので、要素を使用する必要がある場合は、それを使用したいと思っていることをすべて実行することができます。

とにかく、それは主にsatifies要件のようになります。

• （それはfの戻り値を格納するのでfがTの新しいインスタンスを返さない限り）それはTの追加のインスタンスを割り当てません。
• 実際にソートする前に、f正確にはstd::distance(left, right)が適用されます。
• O（n log n）ソーターで使用すると、O（n log n）の全体的な複雑さが維持されます。
• std::sortは今日の時点では十分にスマートではないため、std::sortは使用されませんが、独自のコードを書くことなく同等のアルゴリズムを使用することができます。

Answer 2

あなただけTのすべてのインスタンスのために、あなたの関数の値をキャッシュするコンパレータを書くstd::sortに固執します。

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

この方法でevaluate(const Foo&);（あなたのケースでf(T)）のみN = the number of unique instances of Foo、N回実行されます：あなたがここに完全な例を見つけることができます

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

。

編集：マップにTインスタンスのコピーはあなたに問題がある場合、あなたはユニークな識別子を使用することができ、コメントで後述するように - 代わりのキーとして - など、あなたのオブジェクトのアドレスなどをオブジェクトそのもの。