std::bsearch
| ヘッダ <cstdlib> で定義 |
||
| void* bsearch( const void* key, const void* ptr, std::size_t count, std::size_t size, /* c-compare-pred */* comp ); |
(1) | |
| extern "C" using /* c-compare-pred */ = int(const void*, const void*); extern "C++" using /* compare-pred */ = int(const void*, const void*); |
(2) | (説明用*) |
key が指す要素と同じ要素を、ptr が指す配列から検索します。この配列は count 個の要素を持ち、各要素は size バイトです。配列は key が指すオブジェクトに対してパーティション化されている必要があります。つまり、key より小さい要素はすべて key と等しい要素の前に、それらは key より大きい要素の前に配置されていなければなりません。完全にソートされた配列はこれらの要件を満たします。要素の比較には、comp が指す関数が使用されます。
配列が、comp が使用するものと同じ基準で、key に対して昇順にパーティション化されていない場合、動作は未定義です。
comp が検索対象の要素と等しいと示す要素が配列内に複数存在する場合、関数が結果としてどの要素を返すかは未指定です。
目次 |
[編集] Parameters
| key | - | 検索する要素へのポインタ |
| ptr | - | 検査する配列へのポインタ |
| count | - | 配列内の要素数 |
| size | - | 配列内の各要素のバイト単位のサイズ |
| comp | - | 比較関数。最初の引数が2番目の引数より小さい場合は負の整数値、大きい場合は正の整数値、同等の場合はゼロを返します。key が最初の引数として、配列の要素が2番目の引数として渡されます。 比較関数のシグネチャは、以下と同等でなければならない。 int cmp(const void *a, const void *b); この関数は、渡されたオブジェクトを変更してはならず、同じオブジェクトに対して呼び出された場合、配列内の位置に関係なく一貫した結果を返さなければなりません。 |
[編集] Return value
見つかった要素へのポインタ。要素が見つからなかった場合はヌルポインタ。
[編集] Notes
名前に反して、C標準やPOSIX標準では、この関数がバイナリ検索を使用して実装されることや、複雑さの保証があることは要求されていません。
C++標準ライブラリによって提供される2つのオーバーロードは、パラメータ comp の型が異なる（その型の言語リンケージが型の一部である）ため、区別されます。
[編集] Example
#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
[編集] See also
| 型が指定されていない要素の範囲をソートする (関数) | |
| 特定のキーに一致する要素の範囲を返す (関数テンプレート) | |
| Cドキュメント for bsearch
| |
