std::search_n

Defined in header <algorithm>

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

(1)

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

(2)

Searches the range [first, last) for the first sequence of count identical elements, each equal to the given value value. The first version uses operator== to compare the elements, the second version uses the given binary predicate p.

Parameters

first, last	-	the range of elements to examine
count	-	the length of the sequence to search for
value	-	the value of the elements to search for
p	-	binary predicate which returns `true` if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following: `bool pred(const Type1 &a, const Type2 &b);` The signature does not need to have `const &`, but the function must not modify the objects passed to it. The type `Type1` must be such that an object of type `ForwardIt` can be dereferenced and then implicitly converted to `Type1`. The type `Type2` must be such that an object of type `T` can be implicitly converted to `Type2`.
Type requirements
- `ForwardIt` must meet the requirements of `ForwardIterator`.

Return value

Iterator to the beginning of the found sequence in the range [first, last). If no such sequence is found, last is returned.

Complexity

At most last - first applications of the predicate.

Possible implementation

First version

template<class ForwardIt, class Size, class T>
ForwardIt search_n(ForwardIt first, ForwardIt last,
                    Size count, const T& value)
{
    for(; first != last; ++first) {
        if (!(*first == value)) {
            continue;
        }
  
        ForwardIt candidate = first;
        Size cur_count = 0;
  
        while (true) {
            ++cur_count;
            if (cur_count == count) {
                // success
                return candidate;
            }
            ++first;
            if (first == last) {
                // exhausted the list
                return last;
            }
            if (!(*first == value)) {
                // too few in a row
                break;
            }
        }
    }
    return last;
}

Second version

template<class ForwardIt, class Size, class T, class BinaryPredicate>
ForwardIt search_n(ForwardIt first, ForwardIt last,
                    Size count, const T& value, BinaryPredicate p)
{
    for(; first != last; ++first) {
        if (!p(*first, value)) {
            continue;
        }
  
        ForwardIt candidate = first;
        Size cur_count = 0;
  
        while (true) {
            ++cur_count;
            if (cur_count == count) {
                // success
                return candidate;
            }
            ++first;
            if (first == last) {
                // exhausted the list
                return last;
            }
            if (!p(*first, value)) {
                // too few in a row
                break;
            }
        }
    }
    return last;
}

Example

#include <iostream>
#include <algorithm>
#include <iterator>
  
template <class Container, class Size, class T>
bool consecutive_values(const Container& c, Size count, const T& v)
{
  return std::search_n(std::begin(c),std::end(c),count,v) != std::end(c);
}
  
int main()
{
   const char sequence[] = "1001010100010101001010101";
  
   std::cout << std::boolalpha;
   std::cout << "Has 4 consecutive zeros: "
             << consecutive_values(sequence,4,'0') << '\n';
   std::cout << "Has 3 consecutive zeros: "
             << consecutive_values(sequence,3,'0') << '\n';
}

Output:

Has 4 consecutive zeros: false
Has 3 consecutive zeros: true

find_end	finds the last sequence of elements in a certain range (function template)
findfind_iffind_if_not (C++11)	finds the first element satisfying specific criteria (function template)
search	searches for a range of elements (function template)
std::experimental::parallel::search_n (parallelism TS)	parallelized version of `std::search_n` (function template)

Links:

http://en.cppreference.com/w/cpp/algorithm/search_n

doc_CPP

2025-01-10 15:47:30

Comments