4. bsearch

最終更新日時(UTC):
が更新

履歴 編集

function
<cstdlib>

std::bsearch

namespace std {
  void*
    bsearch(const void* key,
            void* base,
            size_t nmemb,
            size_t size,
            c-compare-pred* compar); // (1)
  void*
    bsearch(const void* key,
            void* base,
            size_t nmemb,
            size_t size,
            compare-pred* compar);   // (2)

  const void*
    bsearch(const void* key,
            const void* base,
            size_t nmemb,
            size_t size,
            c-compare-pred* compar); // (3) C++26
  const void*
    bsearch(const void* key,
            const void* base,
            size_t nmemb,
            size_t size,
            compare-pred* compar);   // (4) C++26
}

概要

ソート済みの配列に対して二分探索を行う。

baseが指すnmemb個の要素 (各要素のサイズはsizeバイト) からなる配列を、比較関数comparを用いて二分探索し、keyが指す値と一致する要素を検索する。

説明用の型c-compare-pred・compare-predは、それぞれextern "C"・extern "C++"の言語リンケージを持つ比較関数int(const void*, const void*)へのポインタ型である。これにより、いずれの言語リンケージの比較関数も渡せる。

戻り値

一致する要素が見つかった場合、その要素へのポインタを返す。一致する要素が複数ある場合、いずれが返されるかは未規定である。

一致する要素が見つからなかった場合、ヌルポインタを返す。

  • (1), (2) : baseが指す配列の要素へのポインタをvoid*型で返す
  • (3), (4) : baseが指す配列の要素へのポインタをconst void*型で返す

比較関数

comparは、第1引数にkey、第2引数に配列の要素を受け取り、以下を返す関数である。

  • keyが要素より小さい場合 : 負の値
  • keyが要素と等しい場合 : 0
  • keyが要素より大きい場合 : 正の値

配列は、この比較関数の順序に従って昇順にソートされていなければならない。

備考

  • C++26では、const修飾を保持するオーバーロード (3), (4) が追加された。これにより、constな配列を探索した結果としてconst void*が返るようになり、constな配列の要素を結果経由で書き換えてしまう不適切なコードを防げる
    • 同時に、非constの配列を受け取る(1), (2)は引数baseがvoid*となり、非constなポインタを返す

例

#include <cstdlib>
#include <iostream>

int compare(const void* a, const void* b)
{
  int x = *static_cast<const int*>(a);
  int y = *static_cast<const int*>(b);
  return x - y;
}

int main()
{
  const int data[] = {1, 3, 5, 7, 9};
  int key = 5;

  // constな配列を探索すると、C++26ではconst int*が得られる
  const int* p = static_cast<const int*>(
    std::bsearch(&key, data, std::size(data), sizeof(int), compare));

  if (p != nullptr) {
    std::cout << "found: " << *p << std::endl;
  }
}

出力

found: 5

バージョン

言語

関連項目

  • qsort: 範囲の並べ替えを行う
  • std::lower_bound: ソート済み範囲から二分探索を行う

参照