bsearch wrapper

Question

Я просто играл с поисковыми алгоритмами некоторое время назад, и после нескольких тестов я был впечатлен тем, насколько быстрее старый bsearch() сравнивался с std :: binary_search(). Я думал, что любой достойный компилятор сможет по возможности заменить std :: binary_search() на bsearch(), но, хотя я использую GCC 4.7, bsearch, похоже, выполняет что-то вроде 5 раз быстрее, чем std :: binary_search.

Так что я думал, что это будет отличное упражнение, пытающееся создать какую-то оболочку для 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; 
} 

Answer 1

bsearch принимает указатель на функцию, и cmp не является указателем на функцию. (EDIT: Я был не прав в этом. Поскольку cmp не записывает никаких переменных - это скобки пусты - это может быть передано как указатель на функцию. Это поведение указано в п. 5.1.1/6 раздела C++ 11 standard.)

bsearch также не возвращает правильные значения, которые должна ожидать функция сравнения. Он должен возвращать -1, если ключ меньше элемента массива, 0, если они равны, и 1, если ключ больше, чем элемент массива. Функция cmp возвращает 0, если они являются неравными и 1, если они равны. В результате, если первый элемент, который вы сравниваете, является неравным с ключом, то ваш cmp делает bsearch, думая, что они равны, и bsearch останавливается, потому что думает, что он сразу нашел правильный элемент.

Answer 2

В общем, это не представляется возможным использовать bsearch для реализации std::binary_search потому что bsearch может искать только непрерывный массив элементов, в то время как std::binary_search работы на диапазоне итераторов, для любого типа итератора. Это может быть итератор связанного списка, итератор deque или какой-то пользовательский, экзотический итератор, созданный пользователем. Очевидно, нет никакого способа поиска этих итераторов с помощью bsearch