在与/函数的参数二进制搜索没有提升

Question

鉴于：

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参数使用二进制搜索（std::lower_bound）产生desiredValue（传递给someFunction时）。 firstCandidate,lastCandidate是给予someFunction的参数。 对于搜索候选人std::lower_bound应该叫someFunction(currentArgument)和比较desiredValue结果。对于SomeValuesomeFunction(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; 
} 

只使用标准函数+二分查找算法。

我该怎么做EASILY（无需编写我自己的二进制搜索功能）有无升压？ int不是迭代器，我还没有想出在这种情况下如何制作boost::make_transform_iterator。

限制：

1. C++ 03标准。
2. 提升是好的，但我真的喜欢解决离不开它。

- 编辑 -

我想知道我怎么可以使用内置或已可用功能（标准:: LOWER_BOUND和类似）做我想做的。我可能写专门的二进制搜索功能，但我不认为这将是“正确”的方式来做到这一点。

Answer 1

想通了（享受微距+模板巫术）。

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

最有可能的，不能轻易做没有提升，除非你生成所有可能值阵列，使包装迭代器自己或类似的东西。

Answer 2

这是我会怎么处理它：

假装您有一个排序的vector<SomeValue>。这个向量可以使用someFunction(index)访问。

现在，look at this。这是二进制搜索的伪代码。与上面的思维过程继续，someFunction(imid)取代A[imid]并key一个SomeValue。确保SomeValue有一个有效的operator <（或者您用来代替它的比较器功能）。

这当然只有当someFunction(x) < someFunction(x + 1)适用于所有已x。你已经说过这是真的，所以它应该是好的。

我会建议使用迭代的方法，因为两者具有相同的渐近运行时间，以及迭代版本可以更容易地报告说未找到一把钥匙，并倾向于使用更少的内存。

编辑我不知道一个简单的方法使用std的东西去做。正如你上面提到的，int不能用作迭代器，并且你可能想要使用的所有函数都使用迭代器。 技术上不过，在这些功能的迭代器模板类型，让你写你自己的IntIter类或类似的东西。使用std::lower_bound将需要operator *()，operator ++()和operator +(int)。 operator *()可能会返回someFunction(n)，其中n与IntIter相关的int值。然而，我不知道这实际上是否会工作，它可能需要更多的时间和编码。你应该看看std::lower_bound和std::advance（称为lower_bound）如果你想采取这种方法。