1

std::find_ifオーバーロードされた関数の 1 つで述語を取ります。バインダーを使用すると、ユーザー定義型の EqualityComparators を作成し、それらを動的比較または静的比較のいずれかに使用できます。

const T&対照的に、標準ライブラリのバイナリ検索関数は、比較に使用する必要がある値にコンパレータと aを使用します。これは私には矛盾しているように感じられ、定数引数をバインドするのではなく、毎回両方の引数でコンパレータを呼び出す必要があるため、おそらくより非効率的です。std::binary_searchこれを使用する方法で実装することは可能std::bindですが、すべてのコンパレータが から継承する必要がありますstd::binary_function。私が見たほとんどのコードはそれをしません。

バインダーを使用させるのではなく、値としてstd::binary_function取るアルゴリズムでそれを使用するときに、コンパレーターに継承させることによる利点はありますか? const T&これらの関数で述語のオーバーロードを提供しない理由はありますか?

4

3 に答える 3

8

の単一引数の述語バージョンはstd::binary_search、O(log n) 時間で完了できません。

古いゲームの「私が考えている文字を当てる」を考えてみてください。「それは A ですか?」と尋ねることができます。「Bですか？」…などなど、手紙にたどり着くまで。これは、線形または O(n) アルゴリズムです。しかし、「M の前ですか?」と尋ねる方が賢明でしょう。「Gの前ですか？」「私より先ですか？」問題の手紙にたどり着くまで、など。これは対数、つまり O(log n) アルゴリズムです。

これが行うことstd::binary_searchであり、これを行うには、次の 3 つの条件を区別できる必要があります。

  • 候補 C は検索項目 X です
  • 候補 C は X より大きい
  • 候補 C は X より小さい

引数が 1 つの述語 P(x) は、「x はプロパティ P を持っている」または「x はプロパティ P を持っていない」としか言いません。このブール関数から 3 つの結果を取得することはできません。

比較演算子 (たとえば、<) を使用すると、C < X と X < C を計算することで 3 つの結果を得ることができます。次に、3 つの可能性があります。

  • !(C < X) && !(X < C)C は X に等しい
  • C < X && !(X < C)C は X より小さい
  • !(C < X) && X < CC は X より大きい

X と C の両方が異なる時点で の両方のパラメーターにバインドされることに注意してください。その<ため、X を の 1 つの引数にバインドしてそれを使用することはできません<。

編集：binary_searchは<=ではなく<を使用していることを思い出させてくれたjpalecekに感謝します。編集編集：明確化のためにRob Kennedyに感謝します。

于 2010-03-03T14:12:06.210 に答える
1

それらは完全に異なるアルゴリズムです。述語が真である最初の項目を直線的find_ifに探し、範囲がソートされていることを利用して、指定された値がその中にあるかどうかを対数時間でテストします。binary_search

述語 forbinary_searchは、範囲が順序付けられる関数を指定します (おそらく、ソートに使用したのと同じ述語を使用する必要があります)。

ソートを利用して、まったく関係のない述語を満たす値を検索することはできません (find_ifとにかく使用する必要があります)。ただし、ソートされた範囲を使用するとlower_bound、 、upper_boundおよびで存在をテストするだけでなく、それ以上のことができることに注意してくださいequal_range。

何が目的なのかという質問はstd::binary_function興味深いものです。

result_type、first_argument_typeおよびの typedef を提供するだけsecond_argument_typeです。これらは、テンプレート引数としてファンクターを与えられたユーザーが、これらの型を見つけて使用できるようにします。

template <class T, class BinaryFunction>
void foo(const T& a, const T& b, BinaryFunction f)
{
     //declare a variable to store the result of the function call
     typename BinaryFunction::result_type result = f(a, b);
     //...
 }

ただし、標準ライブラリで使用される唯一の場所はbind1st、bind2nd、not1、などの他のファンクタ ラッパーを作成することだと思いますnot2。(それらが他の目的に使用された場合、関数をファンクターとして使用すると、移植性がなくなるため、人々はいつでもあなたに怒鳴るでしょう。)

たとえば、次のbinary_negateように実装できます (GCC):

template<typename _Predicate>
class binary_negate
: public binary_function<typename _Predicate::first_argument_type,
             typename _Predicate::second_argument_type, bool>
{
protected:
  _Predicate _M_pred;

public:
  explicit
  binary_negate(const _Predicate& __x) : _M_pred(__x) { }

  bool
  operator()(const typename _Predicate::first_argument_type& __x,
     const typename _Predicate::second_argument_type& __y) const
  { return !_M_pred(__x, __y); }
};

もちろん、operator()単にテンプレートである可能性もあります。その場合、これらの typedef は不要になります (欠点はありますか?)。ユーザーが明示的に型定義する必要なしに、引数の型が何であるかを見つけるためのメタプログラミング手法もおそらくあります。私は、C++0x が与える力で多少邪魔になると思います-たとえば、可変引数テンプレートを使用して任意のアリティの関数の否定子を実装したい場合...

std::tr1::bind(IMO では、C++98 のファンクターは、やなどに比べて柔軟性に欠け、原始的すぎますstd::tr1::mem_fnが、おそらく当時、それらを機能させるために必要なメタプログラミング手法に対するコンパイラーのサポートはそれほど良くなく、おそらくその手法はまだ発見されていました。 )

于 2010-03-03T16:11:26.420 に答える
0

これは、C++のFunctorの概念の誤解です。

継承とは何の関係もありません。オブジェクトを関数にする（任意のアルゴリズムに渡すことができる）プロパティは、関数ポインターであるか、関数呼び出し演算子がオーバーロードされているオブジェクトであるかに関係なく、それぞれ式object(x)またはの有効性です。object(x, y)絶対に何からも継承しません。同じことが。にも当てはまりますstd::bind。

コンパレータとしてのバイナリファンクタの使用は、コンパレータ（たとえばstd::less）がバイナリファンクタであり、それらを直接使用できるのは良いことです。

私見では、提案する述語バージョンを提供または使用してもメリットはありません（結局のところ、1つの参照を渡すだけです）。バインダーを使用しても（パフォーマンス）向上はありません。これは、アルゴリズムと同じことを行うためです（bindは、アルゴリズムの代わりに追加の引数を渡します）。

于 2010-03-03T14:31:07.347 に答える