std::search_n() algorithm
- since C++20
- since C++17
- until C++17
// (1)
template< class ForwardIt, class Size, class T >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );
// (2)
template< class ForwardIt, class Size, class T, class BinaryPredicate >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Size count, const T& value );
// (4)
template< class ExecutionPolicy, class ForwardIt,
class Size, class T, class BinaryPredicate >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Size count, const T& value, BinaryPredicate p );
// (1)
template< class ForwardIt, class Size, class T >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );
// (2)
template< class ForwardIt, class Size, class T, class BinaryPredicate >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Size count, const T& value );
// (4)
template< class ExecutionPolicy, class ForwardIt,
class Size, class T, class BinaryPredicate >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Size count, const T& value, BinaryPredicate p );
// (1)
template< class ForwardIt, class Size, class T >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );
// (2)
template< class ForwardIt, class Size, class T, class BinaryPredicate >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );
Searches the range for the first sequence of count
identical elements, each equal to the given value
.
-
(1) Elements are compared using
operator==
. -
(2) Elements are compared using the given binary predicate
p
. -
(3 - 4) Same as (1 - 2), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20) istrue
.
Parameters
first last | The range of elements to examine. |
s_first s_last | The range of elements to search for. |
policy | The execution policy to use. See execution policy for details. |
searcher | The searcher encapsulating the search algorithm and the pattern to look for. |
p | Binary predicate which returns The signature of the function should be equivalent to the following:
|
Type requirements
ForwardIt | LegacyForwardIterator |
Size | Must be implicitly convertible to an integral type. |
Return value
If count
is positive, returns an iterator to the beginning of the first sequence found in the range [first
; last
).
Each iterator it in the sequence should satisfy the following condition:
- (1, 3)
*it == value
- (2, 4)
p(*it, value)
If no such sequence is found, last
is returned.
If count
is zero or negative, first
is returned.
Complexity
Given N
as std::distance(first, last)
:
- (1, 3) At most
N
comparisons withvalue
usingoperator==
. - (2, 4) At most
N
applications of the predicatep
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
search_n (1)
template<class ForwardIt, class Size, class T>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value)
{
if (count <= 0)
return first;
for (; first != last; ++first)
{
if (!(*first == value))
continue;
ForwardIt candidate = first;
for (Size cur_count = 1; true; ++cur_count)
{
if (cur_count >= count)
return candidate; // success
++first;
if (first == last)
return last; // exhausted the list
if (!(*first == value))
break; // too few in a row
}
}
return last;
}
search_n (2)
template<class ForwardIt, class Size, class T, class BinaryPredicate>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value,
BinaryPredicate p)
{
if (count <= 0)
return first;
for (; first != last; ++first)
{
if (!p(*first, value))
continue;
ForwardIt candidate = first;
for (Size cur_count = 1; true; ++cur_count)
{
if (cur_count >= count)
return candidate; // success
++first;
if (first == last)
return last; // exhausted the list
if (!p(*first, value))
break; // too few in a row
}
}
return last;
}
Examples
#include <algorithm>
#include <iostream>
#include <iterator>
template<class Container, class Size, class T>
[[nodiscard]]
constexpr 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()
{
constexpr char sequence[] = "1001010100010101001010101";
static_assert(consecutive_values(sequence, 3, '0'));
std::cout << std::boolalpha
<< "Has 4 consecutive zeros: "
<< consecutive_values(sequence, 4, '0') << '\n'
<< "Has 3 consecutive zeros: "
<< consecutive_values(sequence, 3, '0') << '\n';
}
Has 4 consecutive zeros: false
Has 3 consecutive zeros: true
Hover to see the original license.