C++でC風ライブラリを作る（二分探索編）

著者：高木信尚

公開日：2019/02/19

最終更新日：2019/02/19

カテゴリー：技術情報

高木です。おはようございます。

今回は標準Cライブラリのbsearch風の関数を作ってみることにします。
bsearchは便利な関数なんですが、C++ではPOD型以外には実質的に使えませんので用途が非常に制限されます。
また、引数も多い上にわかりにくいので、もうちょっと使い勝手を改善したいものです。

bsearchと完全に互換性を持たせることにあまり意味はありません。
引数の渡し方もそうですが、比較関数の仕様はstd::lower_boundやstd::sort関数なんかと同じで、2つの値を比較して小さければtrueを返す形式にそろえておく方がよさそうです。
ちなみにオリジナルのbsearch関数ｍに渡す比較関数は、2つの値を比較し、左の値が小さければ負、等しければゼロ、左の値は大きければ正の値を返す必要があります。
また、単純に<演算子で比較できる場合は、std::lower_bound関数と同様、比較関数を省略できるようにしたほうがよいでしょう。

比較関数以外の引数については、探索する値（キー）と探索対象の列コンテナを渡すだけで十分かと思います。
凝った使い方をしたいのであれば、std::lower_bound関数を使うほうが融通が利くでしょうから。

返却値をどうするかも考えものです。
STLの探索関数は、該当する要素が見つからなければ末尾の次を指す反復子を返す仕様になっています。
これはこれで合理的なのですが、簡便さを欠きます。
本来であれば、std::optionalを使いたいところなのに、残念ながらstd::optionalはC++17からしか使えません。

そこで今回は、あくまでも簡便さ優先で、探索で見つけた要素へのポインタを返すことにしました。
もちろん見つからない場合は空ポインタを返します。
オリジナルのbsearch関数であれば、返したポインタを頼りに見つけた要素が配列内のどこにあるかを知ることができるのですが、今回は必ずしもそれができなくなります。
もっとも、大多数のケースでは、探索対象の列コンテナは配列かstd::arrayかstd::vectorだと思いますので、それなら見つけた要素がどこかを知ることはできるんですけどね。

前置きが長くなってしまいましたが、ここから実際の実装を見ていきます。
凝った実装はしない方針なので、若干汎用性に欠けるところはありますが、まあいいでしょう。

namespace cloverfield
{
  template <typename C, typename T, typename F>
  inline T* bsearch(T const& key, C& c, F comp)
  {
    auto first = std::begin(c);
    auto last = std::end(c);
    first = std::lower_bound(first, last, key, comp);
    if (first == last || comp(key, *first))
      return nullptr;
    return &*first;
  }

  template <typename C, typename T>
  inline T* bsearch(T const& key, C& c)
  {
    return bsearch(key, c, std::less<T>());
  }
}

namespace cloverfield

{

template <typename C, typename T, typename F>

inline T* bsearch(T const& key, C& c, F comp)

{

auto first = std::begin(c);

auto last = std::end(c);

first = std::lower_bound(first, last, key, comp);

if (first == last || comp(key, *first))

return nullptr;

return &*first;

}

template <typename C, typename T>

inline T* bsearch(T const& key, C& c)

{

return bsearch(key, c, std::less<T>());

}

今回、bsearch関数を作ったということは、次に作るのはqsort関数でしょうね。