Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::search_n

      From cppreference.com
      <cpp‎ |algorithm
       
       
      Algorithm library
      Constrained algorithms and algorithms on ranges(C++20)
      Constrained algorithms, e.g.ranges::copy,ranges::sort, ...
      Execution policies(C++17)
      Sorting and related operations
      Partitioning operations
      Sorting operations
      Binary search operations
      (on partitioned ranges)
      Set operations (on sorted ranges)
      Merge operations (on sorted ranges)
      Heap operations
      Minimum/maximum operations
      (C++11)
      (C++17)
      Lexicographical comparison operations
      Permutation operations
      C library
      Numeric operations
      Operations on uninitialized memory
       
      Defined in header<algorithm>
      (1)
      template<class ForwardIt,class Size,class T>

      ForwardIt search_n( ForwardIt first, ForwardIt last,

                          Size count,const T& value);
      		(constexpr since C++20)
      (until C++26)
      template<class ForwardIt,class Size,

               class T=typenamestd::iterator_traits
                             <ForwardIt>::value_type>
      constexpr ForwardIt search_n( ForwardIt first, ForwardIt last,

                                    Size count,const T& value);
      		(since C++26)
      (2)
      template<class ExecutionPolicy,

               class ForwardIt,class Size,class T>
      ForwardIt search_n( ExecutionPolicy&& policy,
                          ForwardIt first, ForwardIt last,

                          Size count,const T& value);
      		(since C++17)
      (until C++26)
      template<class ExecutionPolicy,

               class ForwardIt,class Size,
               class T=typenamestd::iterator_traits
                             <ForwardIt>::value_type>
      ForwardIt search_n( ExecutionPolicy&& policy,
                          ForwardIt first, ForwardIt last,

                          Size count,const T& value);
      		(since C++26)
      (3)
      template<class ForwardIt,class Size,class T,class BinaryPred>

      ForwardIt search_n( ForwardIt first, ForwardIt last,

                          Size count,const T& value, BinaryPred p);
      		(constexpr since C++20)
      (until C++26)
      template<class ForwardIt,class Size,

               class T=typenamestd::iterator_traits
                             <ForwardIt>::value_type,
               class BinaryPred>
      constexpr ForwardIt search_n( ForwardIt first, ForwardIt last,

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

               class T,class BinaryPred>
      ForwardIt search_n( ExecutionPolicy&& policy,
                          ForwardIt first, ForwardIt last,

                          Size count,const T& value, BinaryPred p);
      		(since C++17)
      (until C++26)
      template<class ExecutionPolicy,class ForwardIt,class Size,

               class T=typenamestd::iterator_traits
                             <ForwardIt>::value_type,
               class BinaryPred>
      ForwardIt search_n( ExecutionPolicy&& policy,
                          ForwardIt first, ForwardIt last,

                          Size count,const T& value, BinaryPred p);
      		(since C++26)

      Searches the range[first, last) for the first sequence ofcount identical elements, each equal to the givenvalue.

      1) Elements are compared usingoperator==.
      3) Elements are compared using the given binary predicatep.
      2,4) Same as(1,3), but executed according topolicy.
      These overloads participate in overload resolution only if all following conditions are satisfied:

      std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> istrue.

      		(until C++20)

      std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> istrue.

      		(since C++20)

      Contents

      [edit]Parameters

      first, last - the pair of iterators defining therange of elements to examine
      count - the length of the sequence to search for
      value - the value of the elements to search for
      policy - theexecution policy to use
      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);

      While the signature does not need to haveconst&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const)Type1 andType2 regardless ofvalue category (thus,Type1& is not allowed, nor isType1 unless forType1 a move is equivalent to a copy(since C++11)).
      The typeType1 must be such that an object of typeForwardIt can be dereferenced and then implicitly converted toType1. The typeType2 must be such that an object of typeT can be implicitly converted toType2.​

      Type requirements
      -
      ForwardIt must meet the requirements ofLegacyForwardIterator.
      -
      BinaryPred must meet the requirements ofBinaryPredicate.
      -
      Size must beconvertible to anintegral type.

      [edit]Return value

      Ifcount is positive, returns an iterator to the beginning of the first sequence found in the range[first, last). Each iteratorit in the sequence should satisfy the following condition:

      1,2)*it== value istrue.
      3,4)p(*it, value)!=false istrue.

      If no such sequence is found,last is returned.

      Ifcount is zero or negative,first is returned.

      [edit]Complexity

      Given\(\scriptsize N\)N asstd::distance(first, last):

      1,2) At most\(\scriptsize N\)N comparisons usingoperator==.
      3,4) At most\(\scriptsize N\)N applications of the predicatep.

      [edit]Exceptions

      The overloads with a template parameter namedExecutionPolicy report errors as follows:

      • If execution of a function invoked as part of the algorithm throws an exception andExecutionPolicy is one of thestandard 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.

      [edit]Possible implementation

      search_n (1)
      template<class ForwardIt,class Size,class T=typenamestd::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=typenamestd::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;}

      [edit]Notes

      Feature-test macroValueStdFeature
      __cpp_lib_algorithm_default_value_type202403(C++26)List-initialization for algorithms(1-4)

      [edit]Example

      Run this code
      #include <algorithm>#include <cassert>#include <complex>#include <iostream>#include <iterator>#include <vector> template<class Container,class Size,class T>constexprbool 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(){constexprchar 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_typeauto it= std::search_n(nums.cbegin(), nums.cend(),2,{4,2});#elseauto it= std::search_n(nums.cbegin(), nums.cend(),2,std::complex<double>{4,2});#endifassert(it== nums.begin());}

      Output:

      Has 4 consecutive zeros: falseHas 3 consecutive zeros: trueHas 2 consecutive zeros: true

      [edit]Defect reports

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

      DRApplied toBehavior as publishedCorrect behavior
      LWG 283C++98T was required to beEqualityComparable, but
      the value type ofInputIt is not alwaysT      		removed the requirement
      LWG 426C++98the complexity upper limit wasN·count,
      it is negative ifcount is negative      		the upper limit is​0​
      ifcount is non-positive
      LWG 714C++98ifcount>0, the complexity upper limit wasN·count, but in
      the worst case the number of comparisons/operations is alwaysN      		changed the upper
      limit toN in this case
      LWG 2150C++98the condition of “sequence occurence” was incorrectcorrected

      [edit]See also

      finds the last sequence of elements in a certain range
      (function template)[edit]
      finds the first element satisfying specific criteria
      (function template)[edit]
      searches for the first occurrence of a range of elements
      (function template)[edit]
      searches for the first occurrence of a number consecutive copies of an element in a range
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/search_n&oldid=180619"
      [8]ページ先頭
      ©2009-2025 Movatter.jp