2

与えられた：

typedef .../*some type*/ SomeValue;

SomeValue someFunction(int arg){
     return /*some calculation involving arg that produces SomeValue*/
}

int firstCandidate = 0, lastCandidate = 101;
SomeValue desiredValue = SomeValue();

二分探索 ( ) を使用して ( に渡されたときに) をint生成する引数を見つけたいです。 、に与えるパラメータです。検索候補の場合、を呼び出して結果を と比較する必要があります。は真です。desiredValuesomeFunctionstd::lower_boundfirstCandidatelastCandidatesomeFunctionstd::lower_boundsomeFunction(currentArgument)desiredValueSomeValue someFunction(x) < someFunction(x + 1)

つまり、これと同じ結果が得られるはずです:

int findArgLowerbound(int first, int last, SomeValue refVal){
     for (int i = first; i < last; i++){
          if (someFunction(i) >= refVal)
               return i;
     }
     return last;
}

標準関数 + 二分探索アルゴリズムのみを使用します。

ブーストの有無にかかわらず、(独自のバイナリ検索関数を作成せずに) 簡単に行うにはどうすればよいですか? intはイテレータではなくboost::make_transform_iterator、この場合の作成方法がわかりません。

制限:

  1. c++03 標準。
  2. ブーストは問題ありませんが、ブーストなしのソリューション が本当に好きです。

- 編集 -

組み込み関数または既に利用可能な関数 (std::lower_bound など) を使用して、自分のやりたいことを実行する方法を知りたいです。特殊な二分探索関数を書くことはできますが、それが「正しい」方法だとは思いません。

4

2 に答える 2

0

それを理解しました (マクロ + テンプレートブードゥーをお楽しみください)。

#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/irange.hpp>
#include <boost/typeof/std/utility.hpp>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <sstream>

std::string convertArgs(int arg1, int arg2){
    std::stringstream out;
    out << std::setfill('0') << std::setw(8) << arg1*arg2;
    return out.str();
}

void boostTest(){
    int first = 0, last = 42;
    int arg = 2;
    std::string desiredValue = "00000007";
    BOOST_AUTO(range, boost::irange(first, last));
    BOOST_AUTO(start, boost::make_transform_iterator(range.begin(), std::bind1st(std::ptr_fun(convertArgs), arg)));
    BOOST_AUTO(end, boost::make_transform_iterator(range.end(), std::bind1st(std::ptr_fun(convertArgs), arg)));
    BOOST_AUTO(found, std::lower_bound(start, end, desiredValue));
    if (found != end){
        std::cout << "str:" << *found << "\nval: " << *(found.base());
    }
}

int main(int argc, char** argv){
    boostTest();
    return 0;
}

ほとんどの場合、すべての可能な値で配列を生成するか、自分でラッパー反復子を作成するか、そのようなものを作成しない限り、ブーストなしでは簡単に実行できません。

于 2013-08-02T16:31:39.370 に答える
0

これは私がそれにアプローチする方法です：

vector<SomeValue>ソートされた があるふりをします。このベクトルは、 を使用してアクセスできますsomeFunction(index)。

さて、これを見てください。これは二分探索の擬似コードです。上記の思考プロセスを続けて、 に置き換えA[imid]てsomeFunction(imid)を作成keyしSomeValueます。SomeValue有効なoperator <(またはその代わりに使用するコンパレーター関数) があることを確認してください。

もちろん、これはsomeFunction(x) < someFunction(x + 1)すべての場合にのみ機能しますx。あなたはこれが真実であると述べたので、それは良いはずです.

どちらも漸近的なランタイムが同じであり、反復バージョンでは見つからなかったキーの報告が容易になり、メモリ使用量が少なくなる傾向があるため、反復アプローチを使用することをお勧めします。

編集私は、stdものを使ってそれを行う簡単な方法を知りません。上で述べたようにint、イテレータとしては機能せず、おそらく使用したいすべての関数がイテレータを使用します。ただし、技術的には、これらの関数の反復子はテンプレート化された型であるため、独自のIntIterクラスなどを作成します。を使用するには、、、およびstd::lower_boundが必要です。おそらく を返します。ここで、は に関連付けられた int 値です。ただし、これが実際に機能するかどうかはわかりません。おそらく、より多くの時間とコーディングが必要になるでしょう。このアプローチを採用する場合は、 and ( で呼び出されます) を参照してください。operator *()operator ++()operator +(int)operator *()someFunction(n)nIntIterstd::lower_boundstd::advancelower_bound

于 2013-08-02T15:51:24.410 に答える