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