C++11 std::set ラムダ比較関数

質問内容

私は std::set をカスタム比較関数で作りたいのです。それをクラスとして定義するには operator() でクラスとして定義することもできますが、ラムダが使われる場所でラムダを定義できることを楽しみたかったので、ラムダ関数を、クラスとして定義したクラスのコンストラクタの初期化リストで定義することにしました。 std::set をメンバーとして持つクラスのコンストラクタの初期化リストにラムダ関数を定義することにしました。しかし、ラムダの型がわからない。先に進む前に、例を挙げておきます。

class Foo
{
private:
     std::set<int, /*???*/> numbers;
public:
     Foo () : numbers ([](int x, int y)
                       {
                           return x < y;
                       })
     {
     }
};

検索した結果、2つの解決策を見つけました。 std::function . ただ、セット比較関数の型が std::function<bool (int, int)> にして、私がやったように正確にラムダを渡します。2つ目の解決策は、make_set関数を書くことです。 std::make_pair .

解決方法1:

class Foo
{
private:
     std::set<int, std::function<bool (int, int)> numbers;
public:
     Foo () : numbers ([](int x, int y)
                       {
                           return x < y;
                       })
     {
     }
};

解決方法2:

template <class Key, class Compare>
std::set<Key, Compare> make_set (Compare compare)
{
     return std::set<Key, Compare> (compare);
}

問題は、1つの解決策を他より好む正当な理由があるかということです。私は標準的な機能（make_setは標準的な関数ではありません）を使用するため、最初のものを好みますが、私は疑問に思っています。 std::function を使うとコードが遅くなる(可能性がある)のでしょうか? つまり、コンパイラが比較関数をインライン化する可能性が低くなるのか、それともラムダ関数型でなく std::function (私は、この場合、ラムダ型であることができないことを知っているが、あなたは知っている、私は一般的に尋ねている) ?

(私はGCCを使っていますが、一般的に人気のあるコンパイラが何をするのか知りたいのです)

要約、私はたくさんの素晴らしい答えを得た後。

速度が重要な場合、最良の解決策は、クラスで operator() というファンクタを使うことです。コンパイラが最適化するのが最も簡単で、間接参照も避けられます。

メンテナンスが簡単で、C++11 の機能を使ったより良い汎用的なソリューションのためには std::function . これはまだ高速で（ファンクタよりほんの少し遅いですが、無視できる程度かもしれません）、どんな関数でも使うことができます - 。 std::function ラムダ、呼び出し可能な任意のオブジェクトを使用することができます。

関数ポインタを使用するオプションもありますが、スピードの問題がなければ、私は std::function の方が良いと思います(C++11を使用している場合)。

ラムダ関数を別の場所に定義するオプションもありますが、そうすると比較関数がラムダ式であることから何も得るものがありません。 operator() でクラス化することができ、定義する場所はいずれにせよセット構築にはならないからです。

デリゲーションを使うなど、もっと他のアイデアもあります。すべての解決策についてより徹底した説明が必要な場合は、回答を読んでください :)

どのように解決するのですか？

そうです。 std::function は、ほぼ不可避なインダイレクトを set . コンパイラは理論上、常に set 's std::function は、常に全く同じラムダでそれを呼び出すことを含み、それは難しく、非常に壊れやすいものです。

壊れやすいというのは、コンパイラがその std::function へのアクセスが実際にラムダへの呼び出しであることを証明する前に、コンパイラが std::set を設定することがないことを証明しなければなりません。 std::function にはあなたのラムダ以外のものは設定されません。 つまり、ラムダはあなたの std::set に到達するすべての可能なルートを追跡し、それらのどれもがそれをしないことを証明しなければならないことを意味します。

これは場合によっては可能かもしれませんが、比較的無害な変更であれば、コンパイラが何とか証明できたとしても、それを破る可能性があります。

一方、ステートレスなファンクタである operator() を持つファンクタは挙動を証明するのが簡単で、それを含む最適化は日常茶飯事です。

そうですね、実際には std::function の方が遅いかもしれません。 その一方で std::function ソリューションの方が make_set よりも保守しやすく、プログラマの時間をプログラムのパフォーマンスと交換することは非常に価値があることです。

make_set には、そのような set への呼び出しから型を推測しなければならない、という重大な欠点があります。 make_set . 多くの場合 set は永続的な状態を保存するものであり、スタック上で作成した後にスコープから外れるようなものではありません。

静的またはグローバルなステートレス・ラムダを作成した場合 auto MyComp = [](A const&, A const&)->bool { ... } を使用することができます。 std::set<A, decltype(MyComp)> の構文で set のインスタンスは、持続可能でありながら、コンパイラが最適化しやすいものです。 decltype(MyComp) のインスタンスはすべてステートレスなファンクタであるため）、インラインで最適化することが容易です。 このことを指摘したのは、あなたが set の中に struct . (あるいはコンパイラは

struct Foo {
  auto mySet = make_set<int>([](int l, int r){ return l<r; });
};

というのは意外でしたね（笑)

最後に、もしあなたがパフォーマンスについて心配しているのなら、次のことを考慮してください。 std::unordered_set の方がはるかに高速であり (その代償として、内容を順番に反復することができず、 良いハッシュを書いたり探したりしなければなりません)、 ソートされた std::vector は、2 段階の "すべてを挿入" それから "内容を繰り返し照会" がある場合に適しています。 単純に詰め込んで vector に詰め、次に sort unique erase を使用すると、無料の equal_range アルゴリズムを使用します。