yohhoyの日記

技術的メモをしていきたい日記

std::search_nアルゴリズムとゼロ長サブシーケンス一致

C++

N要素からなるサブシーケンス検索を行うC++標準アルゴリズムstd::search_nでは、“0個の任意要素からなるサブシーケンス” は常に先頭位置にマッチする。

#include <algorithm>

int arr[5] = {0, 10, 10, 20, 30};

// 2個の要素10からなるサブシーケンス
auto itr1 = std::search_n(arr, arr + 5, 2, 10);
assert(itr1 == arr + 1);  // index=1

// 2個の要素20からなるサブシーケンス
auto itr2 = std::search_n(arr, arr + 5, 2, 20);
assert(itr2 == arr + 5);  // NOT FOUND

// 0個の要素42からなるサブシーケンス
auto itr3 = std::search_n(arr, arr + 5, 0, 42);
assert(itr3 == arr + 0);  // index=0

C++03 25.1.9/p4-6より引用。

template<class ForwardIterator, class Size, class T>
  ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last, Size count,
           const T& value);

template<class ForwardIterator, class Size, class T,
         class BinaryPredicate>
  ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last, Size count,
          const T& value, BinaryPredicate pred);

4 Requires: Type T is EqualityComparable (20.1.1), type Size is convertible to integral type (4.7, 12.3).
5 Effects: Finds a subsequence of equal values in a sequence.
6 Returns: The first iterator i in the range [first, last - count) such that for any non-negative integer n less than count the following corresponding conditions hold: *(i + n) == value, pred(*(i + n),value) != false. Returns last if no such iterator is found.

関連URL