C++のstd::binary_searchで構造体を検索＆イテレーターを取得

ソート済み構造体の配列を検索して、見つかった位置のイテレーターを取得するというネタです。
タイトルにはstd::binary_searchとありますけど、binary_searchでは見つかった位置は 分からないので、std::lower_boundを使用します。 定番ですけど、いざやろうとするとパッと出てこないので、備忘録も兼ねて。。

検索する関数

#include <algorithm>

template <class ForwardIterator, class T, class Compare>
ForwardIterator bfind(ForwardIterator first, ForwardIterator last, const T &val,
                      Compare comp) {
  ForwardIterator it = std::lower_bound(first, last, val, comp);

  if (it != last && !comp(val, *it)) {
    return it;
  } else {
    return last;
  }
}

構造体などのデータ配列を検索するので、比較関数compも指定してやります。

サンプル

#include <algorithm>
#include <tuple>
#include <vector>

int main() {
  using Data = std::tuple<int, std::string>;
  std::vector<Data> data{
      {4, "a"}, {2, "b"}, {1, "d"},
  };
  auto comp_first = [](const Data &lhs, const Data &rhs) {
    return std::get<0>(lhs) < std::get<0>(rhs);
  };
  auto comp_second = [](const Data &lhs, const Data &rhs) {
    return std::get<1>(lhs) < std::get<1>(rhs);
  };

  auto it = bfind(data.begin(), data.end(), Data{0, "b"}, comp_second);
  if (it != data.end()) {
    std::cout << "Data={" << std::get<0>(*it) << ", "
              << std::get<1>(*it).c_str() << "}" << std::endl;
  }
  it = bfind(data.begin(), data.end(), Data{0, "c"}, comp_second);
  if (it == data.end()) {
    std::cout << "Not found" << std::endl;
  }

  std::sort(data.begin(), data.end());
  it = bfind(data.begin(), data.end(), Data{4, ""}, comp_first);
  if (it != data.end()) {
    std::cout << "Data={" << std::get<0>(*it) << ", "
              << std::get<1>(*it).c_str() << "}" << std::endl;
  }
  it = bfind(data.begin(), data.end(), Data{3, ""}, comp_first);
  if (it == data.end()) {
    std::cout << "Not found" << std::endl;
  }

  return 0;
}

実行結果

Data={2, b}
Not found
Data={4, a}
Not found

簡単ですね。