std::bsearch
| Определено в заголовочном файле <cstdlib>
|
||
| void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /*предикат-сранения*/* comp ); |
(1) | |
| extern "C++" using /*предикат-сранения*/ = int(const void*, const void*); extern "C" using /*c-предикат-сранения*/ = int(const void*, const void*); |
(2) | (только для пояснения*) |
Находит элемент, равный элементу, на который указывает key в массиве, на который указывает ptr. Массив содержит count элементов по size байтов каждый и должен быть разделён относительно объекта, на который указывает key, то есть все элементы, которые при сравнении меньше чем должны стоять перед всеми элементами, которые при сравнении равны, а те должны стоять перед всеми элементами, которые при сравнении больше, чем объект key. Полностью отсортированный массив соотетствует этим требованиям. Элементы сравниваются с помощью функции, на которую указывает comp.
Поведение не определено, если масс��в ещё не разделён в порядке возрастания по ключу в соответствии с тем же критерием, который использует comp.
Если массив содержит несколько элементов, которые comp указала равными искомому элементу, то не указано, какой элемент функция вернёт в качестве результата.
Содержание |
[править] Параметры
| key | — | указатель на элемент для поиска |
| ptr | — | указатель на массив для проверки |
| count | — | количество элементов в массиве |
| size | — | размер каждого элемента массива в байтах |
| comp | — | функция сравнения, которая возвращает отрицательное целое значение, если первый аргумент меньше второго, положительное целое значение, если первый аргумент больше второго, и ноль, если аргументы эквивалентны. key передаётся в качестве первого аргумента, элемент массива в качестве второго. Сигнатура функции сравнения должна быть эквивалентна следующему: int cmp(const void *a, const void *b); Функция не должна изменять переданные ей объекты и должна возвращать согласованные результаты при вызове для одних и тех же объектов, независимо от их положения в массиве. |
[править] Возвращаемое значение
Указатель на найденный элемент или нулевой указатель, если элемент не найден.
[править] Примечание
Несмотря на название, ни стандарты C, ни POSIX не требуют, чтобы эта функция была реализована с использованием бинарного поиска, и не дают никаких гарантий сложности.
Две перегрузки, предоставляемые стандартной библиотекой C++, различны, поскольку типы параметра comp различны (no section name является частью типа)
[править] Пример
#include <array> #include <cstdlib> #include <iostream> template <typename T> int compare(const void *a, const void *b) { const auto &arg1 = *(static_cast<const T*>(a)); const auto &arg2 = *(static_cast<const T*>(b)); const auto cmp = arg1 <=> arg2; return cmp < 0 ? -1 : cmp > 0 ? +1 : 0; } int main() { std::array arr { 1, 2, 3, 4, 5, 6, 7, 8 }; for (const int key : { 4, 8, 9 }) { const int* p = static_cast<int*>( std::bsearch(&key, arr.data(), arr.size(), sizeof(decltype(arr)::value_type), compare<int>)); std::cout << "значение " << key; (p) ? std::cout << " найдено в позиции " << (p - arr.data()) << '\n' : std::cout << " не найдено\n"; } }
Вывод:
значение 4 найдено в позиции 3 значение 8 найдено в позиции 7 значение 9 не найдено
[править] Смотрите также
| сортирует диапазон элементов с неопределённым типом (функция) | |
| возвращает диапазон элементов, соответствующих определённому ключу (шаблон функции) | |
| Документация C по bsearch
| |
