1

不久前我只是在玩搜索算法，经过几次基准测试后，我对旧的 bsearch() 与 std::binary_search() 相比要快得多感到印象深刻。我认为任何体面的编译器都可以在可能的情况下用 bsearch() 替换 std::binary_search()，但即使我使用的是 GCC 4.7，bsearch 的执行速度似乎比 std::binary_search 快 5 倍。

所以我认为尝试为 bsearch 创建某种包装器与 std::binary_search 相同的接口将是一个很好的练习。但不知什么原因，我没能做到。这是我的代码：

template<typename InputIterator, class T>
bool binary_search(InputIterator first, InputIterator last, const T& value)
{
    auto cmp = [](const void* a, const void* b)
    {
        return (int) ((*(T*)a) == (*(T*)b));
    };

    std::cout << value << std::endl;
    T* res = (T*) bsearch(&value, first, last-first, sizeof(*first), cmp);
    return res != nullptr;
}

代码编译良好，执行时不会崩溃。但是，似乎 bsearch 在一次内部迭代后立即停止（*res 始终等于作为参数传递的选项卡中间的值）。我无法找到它为什么不起作用。所以，如果可能的话，一点帮助就可以了。

谢谢。

对于那些要求用于检查速度的代码的人：

const std::string keyword_str[] = {
    // Some strings
};

int cmp(const void* s1, const void* s2)
{
    return (int) ((*(std::string*)s1) == (*(std::string*)s2));
}

int main()
{
    time_t start, end;
    double dif;
    time (&start);

    // Code
    for (const string& str: keyword_str)
    {
        for (size_t i = 0 ; i < 1000000 ; ++i)
        {
            // std::binary_search (uncomment to check)
            //bool a = std::binary_search(keyword_str, keyword_str+28, str);

            // bsearch
            char** st = (char**) bsearch(&str, keyword_str, 28, sizeof(keyword_str[0]), cmp);
        }
    }

    time (&end);
    dif = difftime (end, start);
    printf("Time spent: %fs.\n", dif);

    return 0;
}
4

2 回答 2

3

bsearch接受函数指针，而cmp不是函数指针。（编辑：我错了。因为cmp没有捕获任何变量——它的括号是空的——它可以作为函数指针传递。这种行为在 C++11 的§5.1.2/6 中指定标准。）

bsearch也不会返回比较函数预期返回的正确值。如果键小于数组元素，它应该返回 -1，如果它们相等，则返回 0，如果键大于数组元素，则返回 1。如果它们不相等，则您的cmp函数返回 0，如果它们相等，则返回 1。结果，如果您要比较的第一个元素与键不相等，那么您的cmp制造商会bsearch认为它们相等并bsearch停止，因为它认为它立即找到了正确的元素。

于 2012-06-05T23:59:51.700 回答
2

一般来说，它不可能用于bsearch实现std::binary_search，因为bsearch它只能搜索一个连续的元素数组，而std::binary_search适用于一系列迭代器，适用于任何迭代器类型。它可以是一个链表迭代器、一个双端队列迭代器，或者用户创建的一些自定义的、奇异的迭代器。显然没有办法搜索这些迭代器bsearch

于 2012-06-06T03:53:19.340 回答