c++ - bsearch包装器

前一段时间我只是在玩搜索算法，在经过一些基准测试之后，我看到旧的bsearch()与std::binary_search()相比要快多少，给我留下了深刻的印象。我认为任何可能的编译器都可以在可能的情况下用bsearch()替换std::binary_search()，但是即使我使用的是GCC 4.7，bsearch的执行速度似乎也要比std::binary_search快5倍。

因此，我认为尝试用与std::binary_search相同的接口(interface)为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;
}

最佳答案

bsearch采用函数指针，而cmp不是函数指针。 (编辑:我对此不太正确。由于cmp不会捕获任何变量-它的方括号为空-可以将其作为函数指针进行传递。此行为在C的5.1.2 / 6节中指定。 ++ 11标准。)
bsearch也不会返回比较函数预期返回的正确值。如果键小于数组元素，则应返回-1；如果键相等，则返回0；如果键大于数组元素，则返回1。如果不相等，则cmp函数返回0，如果相等则返回1。结果，如果您要比较的第一个元素与键不相等，那么您的cmp会使bsearch认为它们相等，并且bsearch停止，因为它认为它立即找到了正确的元素。

关于c++ - bsearch包装器，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10906497/