bsearch包装器

Question

不久前，我只是在玩搜索算法，经过几个基准测试之后，我看到了旧的bsearch()与std::binary_search()相比有多快，这给我留下了深刻的印象。我认为任何合适的编译器都可以在可能的情况下用bsearch()代替std::binary_search()，但是即使我使用GCC 4.7，bsearch的执行速度似乎比std::binary_search快5倍。

因此，我认为这将是一个很好的练习，尝试用相同的接口(然后是std::binary_search )为bsearch创建某种包装器。但由于一个未知的原因，我没能做到。这是我的密码：

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停止了，因为它认为它立即找到了正确的元素。

Answer 2

通常，不可能使用bsearch实现std::binary_search，因为bsearch只能搜索一个连续的元素数组，而std::binary_search则可以搜索任何迭代器类型的迭代器范围。它可以是链接列表迭代器、deque迭代器，也可以是用户创建的自定义外来迭代器。显然没有办法用bsearch搜索这些迭代器。