std::bsearch
cppreference.netより
| ヘッダで定義 <cstdlib>
|
||
void* bsearch( const void* key, const void* ptr, std::size_t count,
std::size_t size, /* c-compare-pred */* comp );
|
(1) | |
void* bsearch( const void* key, const void* ptr, std::size_t count,
std::size_t size, /* compare-pred */* comp );
|
(2) | |
void* bsearch( void* key, const void* ptr, std::size_t count,
std::size_t size, /* c-compare-pred */* comp );
|
(3) | (C++26以降) |
void* bsearch( void* key, const void* ptr, std::size_t count,
std::size_t size, /* compare-pred */* comp );
|
(4) | (C++26以降) |
extern "C" using /* c-compare-pred */ = int(const void*, const void*);
|
(説明のみ*) | |
extern "C++" using /* compare-pred */ = int(const void*, const void*);
|
(説明のみ*) | |
key が指す要素と等しい要素を、ptr が指す配列内から見つけます。配列は count 個の size バイトの要素を持ち、key が指すオブジェクトに対して分割されていなければなりません。すなわち、比較して小さい全ての要素は比較して等しい全ての要素の前に現れ、それらは比較して大きい全ての要素の前に現れなければなりません。完全にソートされた配列はこれらの要件を満たします。要素は comp が指す関数を使って比較されます。
配列が key に関して、comp が使うのと同じ基準に従って昇順に既に分割されていない場合、動作は未定義です。
配列に comp が検索された要素と等しいと示す複数の要素が含まれている場合、関数が結果としてどの要素を返すかは未規定です。
引数
| key | - | 検索する要素へのポインタ |
| ptr | - | 調査する配列へのポインタ |
| count | - | 配列内の要素の数 |
| size | - | 配列内の各要素のサイズ（バイト） |
| comp | - | 比較関数。第1引数が第2引数より小さい場合は負の整数値、第1引数が第2引数より大きい場合は正の整数値を返し、引数が等価の場合はゼロを返します。key が第1引数として渡され、配列の要素が第2引数として渡されます。比較関数のシグネチャは以下と同等であるべきです:
関数は渡されたオブジェクトを変更してはならず、同じオブジェクトに対して呼び出されたときは、配列内の位置に関わらず一貫した結果を返さなければなりません。 |
戻り値
見つかった要素へのポインタ、または要素が見つからなかった場合はヌルポインタ。
ノート
名前にもかかわらず、C も POSIX 標準もこの関数が二分探索を使って実装されることや、何らかの複雑性の保証を要求していません。
C++ 標準ライブラリが提供する2つのオーバーロードは、引数 comp の型が異なるため (言語リンケージ がその型の一部である)、別個のものです。
例
このコードを実行
#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 << "value " << key;
if (p)
std::cout << " found at position " << (p - arr.data()) << '\n';
else
std::cout << " not found\n";
}
}
出力:
value 4 found at position 3
value 8 found at position 7
value 9 not found
関連項目
| 不特定の型の要素の範囲をソートする (関数) | |
| 二分探索を使って指定された値に一致する要素の範囲を見つける (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
Cドキュメント for bsearch
| |