std::bsearch
ヘッダ <cstdlib> で定義 | ||
void* bsearch(constvoid* key, constvoid* ptr, std::size_t count, std::size_t size, /*compare-pred*/* comp ); | (1) | |
extern"C++"using/*compare-pred*/=int(constvoid*, constvoid*);// exposition-only extern"C"using/*c-compare-pred*/=int(constvoid*, constvoid*);// exposition-only | (2) | |
ptr の指す配列から key の指す要素と等しい要素を探します。 配列はそれぞれ size バイトの要素を count 個持ち、 key の指すオブジェクトに関して分割されていなければなりません。 つまり、キーオブジェクトより小さなすべての要素はキーオブジェクトと等しいすべての要素より前に現れなければならず、それらはキーオブジェクトより大きなすべての要素より前に現れなければなりません。 完全にソートされた配列はこれらの要件を満たします。 要素は comp の指す関数を使用して比較されます。
配列がキーに関して comp が使用するのと同じ基準に従ってあらかじめ昇順に分割されていない場合、動作は未定義です。
検索する要素と等しいと comp が示す要素が配列に複数含まれている場合、関数が結果としていずれの要素を返すかは未規定です。
目次 |
[編集]引数
| key | - | 検索する要素を指すポインタ |
| ptr | - | 調べる配列を指すポインタ |
| count | - | 配列の要素数 |
| size | - | 配列の各要素のバイト単位のサイズ |
| comp | - | 第1引数が第2引数より小さい場合は負の整数値、第1引数が第2引数より大きい場合は正の整数値、第1引数が第2引数と等しい場合はゼロを返す比較関数。 key が第1引数として、配列の要素が第2引数として渡されます。比較関数のシグネチャは以下と同等であるべきです。 int cmp(constvoid*a, constvoid*b); 関数は渡されたオブジェクトを変更してはならず、同じオブジェクトに対してはその配列内の位置にかかわらず一貫した結果を返さなければなりません。 |
[編集]戻り値
見つかった要素を指すポインタ、または要素が見つからなかった場合はヌルポインタ。
[編集]ノート
その名前にもかかわらず、 C も POSIX 標準もこの関数がバイナリサーチを用いて実装されることも、いかなる計算量の保証も、要求していません。
引数 comp の型が異なるため (言語リンケージは型の一部です)、 C++ 標準ライブラリが提供する2つのオーバーロードは異なります。
[編集]例
#include <cstdlib>#include <iostream> int compare(constvoid*ap, constvoid*bp){constint*a =(int*) ap;constint*b =(int*) bp;if(*a <*b)return-1;elseif(*a >*b)return1;elsereturn0;} int main(int argc, char**argv){constint ARR_SIZE =8;int arr[ARR_SIZE]={1, 2, 3, 4, 5, 6, 7, 8}; int key1 =4;int*p1 =(int*) std::bsearch(&key1, arr, ARR_SIZE, sizeof(arr[0]), compare);if(p1)std::cout<<"value "<< key1 <<" found at position "<<(p1 - arr)<<'\n';elsestd::cout<<"value "<< key1 <<" not found\n"; int key2 =9;int*p2 =(int*) std::bsearch(&key2, arr, ARR_SIZE, sizeof(arr[0]), compare);if(p2)std::cout<<"value "<< key2 <<" found at position "<<(p2 - arr)<<'\n';elsestd::cout<<"value "<< key2 <<" not found\n";}
出力:
value 4 found at position 3 value 9 not found
[編集]関連項目
| 指定範囲の不特定な型の要素をソートします (関数) | |
| 特定のキーに一致する要素の範囲を返します (関数テンプレート) | |
bsearch の C言語リファレンス | |
