ゆとりーなの日記

日記的な事を書いて行くと思はれる

yappy祭り記念

 連日開催のyappy氏のイベントに関連して、yappylibにも遂に新たな関数が追加されました!

#include <iterator>
#include <random>
 
template <typename Iterator, typename T, typename Random = std::mt19937>
bool yappy_search(Iterator first, Iterator end, const T &val, Random &&engine = Random()) {
  std::uniform_int_distribution<int> distribution(0, std::distance(first, end) - 1);
  for (;;) {
    if (*std::next(first, distribution(engine)) == val) {
      return true;
    }
  }
  return false;
}

 見ての通り、ある範囲にある値があるかを検索する関数です。運がいいとなんとO(1)で見つかりますし、最悪でも範囲に検索する値が存在すれば停止が保障されます。しかし検索中なのか、範囲に検索している値がないのかの判別は範囲が大きくなればなるほど困難になります。また、乱数エンジンを外部から与えることで運を調節できます。デフォルトはstd::mt19937です。
以下使用例です。

#include <iostream>
#include <vector>
 
int main() {
  std::vector<int> v = {0, 1, 2, 3, 4, 5};
  bool b = yappy_search(v.begin(), v.end(), 5);
  std::cout << std::boolalpha << b << std::endl;
  return 0;
}

出力

true