home | help 
std::search_n(3)	       C++ Standard Libary		std::search_n(3)

NAME
     std::search_n - std::search_n

Synopsis
	Defined in header <algorithm>
	template< class ForwardIt, class
	Size, class T >
						  (constexpr
	ForwardIt search_n( ForwardIt		  since C++20)
	first, ForwardIt last,			  (until C++26)

			    Size count,
	const T& value );
	template< class ForwardIt, class

Size,
		  class T = typename
	std::iterator_traits
						  (since C++26)
	<ForwardIt>::value_type >
	constexpr ForwardIt search_n(
	ForwardIt first, ForwardIt last,

	Size count, const T& value );
	template< class ExecutionPolicy,

		  class ForwardIt, class
	Size, class T > 					(since
	ForwardIt search_n(					C++17)
	ExecutionPolicy&& policy,				(until
			    ForwardIt				C++26)
	first, ForwardIt last,

			    Size count,
	const T& value );
	template< class ExecutionPolicy,

		  class ForwardIt, class

Size,
		  class T = typename
	std::iterator_traits
								(since
	<ForwardIt>::value_type >				C++26)
	ForwardIt search_n(
	ExecutionPolicy&& policy,
			    ForwardIt
	first, ForwardIt last,

			    Size count,
	const T& value );
	template< class ForwardIt, class  (1)
	Size, class T, class BinaryPred >
									(const-
     expr
	ForwardIt  search_n(  ForwardIt 				   since
     C++20)
	first, ForwardIt last,						(until
									C++26)
			    Size count,
	const T& value, BinaryPred p );
	template< class ForwardIt, class

Size,
					      (2)
		  class T = typename
	std::iterator_traits
									(since
	<ForwardIt>::value_type,					C++26)
		  class BinaryPred >
	constexpr ForwardIt search_n(
	ForwardIt first, ForwardIt last,

			    Size count,
	const T& value, BinaryPred p );
	template< class ExecutionPolicy,
	class ForwardIt, class Size,
						  (3)
		  class T, class
	BinaryPred							       >
     (since
	ForwardIt						       search_n(
     C++17)
	ExecutionPolicy&&						 policy,
     (until
			    ForwardIt
     C++26)
	first, ForwardIt last,

			    Size count,
	const T& value, BinaryPred p );
	template< class ExecutionPolicy,
	class ForwardIt, class Size,				(4)

		  class T = typename
	std::iterator_traits

	<ForwardIt>::value_type,
     (since
		  class 		      BinaryPred		       >
     C++26)
	ForwardIt search_n(
	ExecutionPolicy&& policy,
			    ForwardIt
	first, ForwardIt last,

			    Size count,
	const T& value, BinaryPred p );

	Searches the range [first, last) for the first sequence of count identi-
     cal elements,
	each equal to the given value.

	1) Elements are compared using operator==.
	3) Elements are compared using the given binary predicate p.
	2,4) Same as (1,3), but executed according to policy.
	These overloads participate in overload resolution only if

	std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>    is    true.
     (until
										  C++20)
	std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>      is
     true. (since
										  C++20)

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
	policy	    - the execution policy to use. See execution policy for  de-
     tails.
		      binary predicate which returns true if the elements should
     be treated
		      as equal.

		      The  signature of the predicate function should be equiva-
     lent to the
		      following:

		       bool pred(const Type1 &a, const Type2 &b);

	p	    - While the signature does not need to  have  const  &,  the
     function must
		      not  modify  the	objects passed to it and must be able to
     accept all
		      values of type (possibly const) Type1 and Type2 regardless
     of value
		      category (thus, Type1 & is not allowed
		      , nor is Type1 unless for Type1 a move is equivalent to  a
     copy
		      (since C++11)).
		      The  type  Type1	must be such that an object of type For-
     wardIt 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 LegacyForwardIterator.
	-
	BinaryPred must meet the requirements of BinaryPredicate.
	-
	Size must be 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,2) *it == value is true.
	3,4) p(*it, value) != false is true.

	If no such sequence is found, last is returned.

	If count is zero or negative, first is returned.

Complexity
	Given \(\scriptsize N\)N as std::distance(first, last):

	1,2) At most \(\scriptsize N\)N comparisons using operator==.
	3,4) At most \(\scriptsize N\)N applications of the predicate p.

Exceptions
	The overloads with a template parameter named ExecutionPolicy report er-
     rors 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 other ExecutionPolicy, the	behavior  is  implementation-de-
     fined.
	  * If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation
					 search_n (1)
	template<class ForwardIt, class Size,
		 class T = typename std::iterator_traits<ForwardIt>::value_type>
	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 (3)
	template<class ForwardIt, class Size,
		 class T = typename std::iterator_traits<ForwardIt>::value_type,
		 class BinaryPred>
	ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T&
     value,
			   BinaryPred 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;
	}

Notes
		  Feature-test macro	       Value	Std		 Feature
	__cpp_lib_algorithm_default_value_type	202403	(C++26) List-initializa-
     tion for
							      algorithms (1-4)

Example
     // Run this code

      #include <algorithm>
      #include <cassert>
      #include <complex>
      #include <iostream>
      #include <iterator>
      #include <vector>

      template<class Container, class Size, class T>
      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[] = ".0_0.000.0_0.";

	  static_assert(consecutive_values(sequence, 3, '0'));

	  for (int n : {4, 3, 2})
	      std::cout << std::boolalpha
			<< "Has " << n << " consecutive zeros: "
			<< consecutive_values(sequence, n, '0') << '\n';

	  std::vector<std::complex<double>> nums{{4, 2}, {4, 2}, {1, 3}};
	  #ifdef __cpp_lib_algorithm_default_value_type
	      auto it = std::search_n(nums.cbegin(), nums.cend(), 2, {4, 2});
	  #else
	      auto  it	= std::search_n(nums.cbegin(), nums.cend(), 2, std::com-
     plex<double>{4, 2});
	  #endif
	  assert(it == nums.begin());
      }

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

	Defect reports

	The following behavior-changing defect	reports  were  applied	retroac-
     tively to
	previously published C++ standards.

	   DR	 Applied to	      Behavior as published		 Correct
     behavior
			    T  was  required  to be EqualityComparable,  removed
     the
	LWG 283  C++98	     but					require-
     ment
			    the value type of InputIt is not always T
			    the complexity upper limit was NA.count,   the upper
     limit is 0
	LWG  426   C++98      it is negative if count is negative	if count
     is
								      non-posi-
     tive
			    if count > 0, the complexity  upper  limit	 changed
     the upper
	LWG  714  C++98      was NA.count, but in			limit to
     N in this
			    the worst case the number of	      case
			    comparisons/operations is always N
	LWG 2150 C++98	    the condition of asequence occurencea was corrected
			    incorrect

See also
	find_end	 finds the last sequence of elements in a certain range
			 (function template)
	find
	find_if 	 finds the first element satisfying specific criteria
	find_if_not	 (function template)
	(C++11)
	search		 searches for a range of elements
			 (function template)
	ranges::search_n searches for a number consecutive copies of an  element
     in a range
	(C++20) 	 (niebloid)

http://cppreference.com 	   2024.06.10			std::search_n(3)
home | help