メモの日々

■ [c++] 二分探索にはstd::partition_point()が使える

C++で二分探索を行いたいときはstd::lower_bound()を使っていたが、C++11で導入されたstd::partition_point()を使えばより柔軟に二分探索が行えることを知った。

lower_boundはpartition_pointの特殊なケースに過ぎない。

lower_boundは使えずpartition_pointなら使える例として、次を行うコードを示す。

• 文字列長を基準にソートされた文字列配列から、特定の文字列長の文字列を二分探索で見つける

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

template<typename Langs>
std::string f(const Langs& langs, int length)
{
  const auto it = std::partition_point(
      std::cbegin(langs),
      std::cend(langs),
      [length](const auto& s) { return s.size() < length; });
  return it == std::end(langs) ? "" : *it;
}

int main()
{
  std::vector<std::string> langs = {
    "c", "c++", "go", "rust", "c#", "java", "swift", "python", "ruby", "javascript"
  };
  std::sort(
      std::begin(langs),
      std::end(langs),
      [](const auto& lhs, const auto& rhs) { return lhs.size() < rhs.size(); });
  std::cout << f(langs, 3) << std::endl;
  std::cout << f(langs, 7) << std::endl;
}

c++
javascript