79

std::setカスタム比較関数でを作成したい。でクラスとして定義することもできますがoperator()、ラムダを使用する場所で定義できる機能を楽しみたかったので、をstd::setメンバーとして持つクラスのコンストラクターの初期化リストでラムダ関数を定義することにしました。しかし、ラムダのタイプを取得できません。先に進む前に、次に例を示します。

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

検索したところ、2つの解決策が見つかりました。1つは、を使用したものstd::functionです。setの比較関数型をbestd::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);
}

問題は、一方のソリューションをもう一方のソリューションよりも優先する正当な理由があるかどうかです。私は最初のものを好みます。なぜならそれは標準機能を利用しているからです（make_setは標準関数ではありません）が、私は疑問に思います：使用std::functionするとコードが（潜在的に）遅くなりますか？つまり、コンパイラが比較関数をインライン化する可能性を低くしますか、それともラムダ関数タイプであるのとまったく同じように動作するのに十分スマートである必要がありますstd::function（この場合、ラムダタイプですが、ご存知のとおり、私は一般的に質問しています）？

（私はGCCを使用していますが、一般的なコンパイラーが一般的に何をするのか知りたいです）

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

operator()速度が重要な場合、最善の解決策は、別名ファンクターを備えたクラスを使用することです。コンパイラが最適化して間接を回避するのが最も簡単です。

C ++ 11機能を使用して、メンテナンスを容易にし、より優れた汎用ソリューションを実現するには、を使用しますstd::function。それでも高速で（ファンクターよりも少し遅いですが、無視できるかもしれません）、任意の関数std::function（ラムダ、呼び出し可能オブジェクト）を使用できます。

関数ポインタを使用するオプションもありますが、速度の問題がない場合は、より良いと思いますstd::function（C ++ 11を使用する場合）。

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

委任を使用するなど、さらに多くのアイデアがあります。すべての解決策のより完全な説明が必要な場合は、回答を読んでください:)

4

6 に答える 6

36

コンパイラーがstd::function呼び出しをインライン化できる可能性は低いですが、ラムダをサポートするコンパイラーは、ファンクターが。によって隠されていないラムダである場合を含め、ファンクターのバージョンをほぼ確実にインライン化しstd::functionます。

decltypeラムダのコンパレータタイプを取得するために使用できます。

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
   auto comp = [](int x, int y){ return x < y; };
   auto set  = std::set<int,decltype(comp)>( comp );

   set.insert(1);
   set.insert(10);
   set.insert(1); // Dupe!
   set.insert(2);

   std::copy( set.begin(), set.end(), std::ostream_iterator<int>(std::cout, "\n") );
}

どの印刷物：

1
2
10

でライブ実行されるのを確認してくださいColiru。

于 2013-02-15T13:49:44.193 に答える
28

はい、はstd::functionあなたにほぼ避けられない間接参照を導入しますset。コンパイラは、理論的には常に、のすべての使用には、set常にstd::functionまったく同じラムダであり、ハードで非常に壊れやすいラムダで呼び出す必要があることを理解できます。

壊れやすいのは、コンパイラがそれに対するすべての呼び出しstd::functionが実際にラムダへの呼び出しであることを証明する前に、あなたへのアクセスがラムダ以外std::setのものに設定されていないことを証明する必要があるためですstd::function。つまり、すべてのコンパイルユニットであなたに到達するために、すべての可能なルートを追跡しstd::set、それらのいずれもそれを行わないことを証明する必要があります。

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

一方、ステートレスのファンクターはoperator()動作を証明するのが簡単であり、それを含む最適化は日常的なことです。

そうです、実際にはstd::functionもっと遅くなるのではないかと思います。一方、std::functionソリューションはソリューションよりも保守が容易make_setであり、プログラマーの時間をプログラムのパフォーマンスと交換することは非常に代替可能です。

make_setsetの呼び出しからそのようなタイプを推測する必要があるという重大な欠点があります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アルゴリズムを使用します。

于 2013-02-15T14:10:50.160 に答える
7

ステートレスラムダ（つまり、キャプチャのないラムダ）は関数ポインターに減衰する可能性があるため、タイプは次のようになります。

std::set<int, bool (*)(int, int)> numbers;

そうでなければ私はmake_set解決策に行きます。非標準であるために1行の作成関数を使用しない場合は、多くのコードを記述できません。

于 2013-02-15T14:04:04.203 に答える
1

プロファイラーで遊んだ私の経験から、パフォーマンスと美しさの間の最良の妥協点は、次のようなカスタムデリゲート実装を使用することです。

https://codereview.stackexchange.com/questions/14730/impossibly-fast-delegate-in-c11

通常はstd::function少し重すぎるので。しかし、私はあなたの特定の状況については知らないので、コメントすることはできません。

于 2013-02-15T13:55:19.330 に答える
1

setをクラス メンバーとして使用し、コンストラクター時にそのコンパレーターを初期化することに決めた場合、少なくとも 1 レベルの間接化は避けられません。コンパイラが知る限り、別のコンストラクタを追加できることを考慮してください。

 Foo () : numbers ([](int x, int y)
                   {
                       return x < y;
                   })
 {
 }

 Foo (char) : numbers ([](int x, int y)
                   {
                       return x > y;
                   })
 {
 }

type のオブジェクトを取得するFooと、その型は、setどのコンストラクターがそのコンパレーターを初期化したかに関する情報を保持しないため、正しいラムダを呼び出すには、実行時に選択された lambda への間接指定が必要operator()です。

bool (*)(int, int)キャプチャレスラムダを使用しているため、キャプチャレスラムダには適切な変換関数があるため、関数ポインター型をコンパレーター型として使用できます。もちろん、これには関数ポインタによる間接化が含まれます。

于 2013-02-15T14:15:59.570 に答える
0

違いは、コンパイラの最適化に大きく依存します。ラムダを最適化するstd::function場合は同等ですが、そうでない場合は、前者に後者にはない間接化を導入します。

于 2013-02-15T13:43:08.733 に答える