c++ - bsearch包装器

Question

我刚才只是在玩弄搜索算法，在进行了一些基准测试之后，我很惊讶地发现旧的 bsearch() 与 std::binary_search() 相比要快得多。我认为任何体面的编译器都能够在可能的情况下用 bsearch() 替换 std::binary_search() ，但即使我使用的是 GCC 4.7，bsearch 的执行速度似乎比 std::binary_search 快 5 倍。

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

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

Answer 1

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

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