首页 文章

使用/不使用boost进行二进制搜索函数参数

提问于
浏览 次
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 参数，它使用二进制搜索（ std::lower_bound ）生成 desiredValue （当传递给 someFunction 时） . firstCandidate ， lastCandidate 是要给 someFunction 的参数 . 对于搜索候选人 std::lower_bound 应调用 someFunction(currentArgument) 并将结果与 desiredValue 进行比较 . for SomeValue 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 .

restrictions ：

  • c 03标准 .

  • 提升是可以的，但我真的更喜欢没有它的解决方案 .

  • 编辑 -

我想知道如何使用内置或已经可用的函数（std :: lower_bound和类似函数）做我想要的 . 我可以编写专门的二进制搜索功能，但我不是't think that'这样做的方式 .

c++ boost c++03

2 回答

  • 0

    这是我接近它的方式：

    假装你有一个已排序的 vector<SomeValue> . 可以使用 someFunction(index) 访问此向量 .

    现在，look at this . 这是二进制搜索的伪代码 . 继续上面的思考过程，将 A[imid] 替换为 someFunction(imid) 并将 key 替换为 SomeValue . 确保 SomeValue 具有有效的 operator < （或者您使用的比较器功能代替它） .

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

    我建议使用迭代方法，因为它们都具有相同的渐近运行时，并且迭代版本使得报告未找到的密钥变得更容易，并且倾向于使用更少的内存 .

    EDIT 我不知道使用 std 这样做的简单方法 . 如上所述， int 不能用作迭代器，并且您可能想要使用的所有函数都使用迭代器 . 从技术上讲，这些函数中的迭代器是模板类型，因此您可以编写自己的 IntIter 类或类似的东西 . 使用 std::lower_bound 需要 operator *() ， operator ++() 和 operator +(int) . operator *() 可能会返回 someFunction(n) ，其中 n 是与 IntIter 关联的int值 . 但是， I don't know if this would actually work ，它可能需要更多的时间和编码 . 如果你想采用这种方法，你应该看std::lower_bound和std::advance（在 lower_bound 中调用） .

    回复于
  • 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;
}

    最有可能的是，除非你生成具有所有可能值的数组，否则不能在没有增强的情况下完成 easily ，自己制作包装器迭代器或类似的东西 .

    回复于

相关问题