Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::adjacent_find

      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>
      template<class ForwardIt>
      ForwardIt adjacent_find( ForwardIt first, ForwardIt last);
      		 (1)(constexpr since C++20)
      template<class ExecutionPolicy,class ForwardIt>

      ForwardIt adjacent_find( ExecutionPolicy&& policy,

                               ForwardIt first, ForwardIt last);
      		 (2)(since C++17)
      template<class ForwardIt,class BinaryPred>

      ForwardIt adjacent_find( ForwardIt first, ForwardIt last,

                               BinaryPred p);
      		 (3)(constexpr since C++20)
      template<class ExecutionPolicy,class ForwardIt,class BinaryPred>

      ForwardIt adjacent_find( ExecutionPolicy&& policy,
                               ForwardIt first, ForwardIt last,

                               BinaryPred p);
      		 (4)(since C++17)

      Searches the range[first, last) for two consecutive equal elements.

      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
      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 typesType1 andType2 must be such that an object of typeForwardIt can be dereferenced and then implicitly converted to both of them.​

      Type requirements
      -
      ForwardIt must meet the requirements ofLegacyForwardIterator.
      -
      BinaryPred must meet the requirements ofBinaryPredicate.

      [edit]Return value

      An iterator to the first of the first pair of identical elements, that is, the first iteratorit such that*it==*(it+1) for(1,2) orp(*it,*(it+1))!=false for(3,4).

      If no such elements are found,last is returned.

      [edit]Complexity

      Givenresult as the return value ofadjacent_find,\(\scriptsize M\)M asstd::distance(first, result) and\(\scriptsize N\)N asstd::distance(first, last):

      1) Exactly\(\scriptsize \min(M+1,N-1)\)min(M+1,N-1) comparisons usingoperator==.
      2)\(\scriptsize O(N)\)O(N) comparisons usingoperator==.
      3) Exactly\(\scriptsize \min(M+1,N-1)\)min(M+1,N-1) applications of the predicatep.
      4)\(\scriptsize O(N)\)O(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

      adjacent_find (1)
      template<class ForwardIt>ForwardIt adjacent_find(ForwardIt first, ForwardIt last){if(first== last)return last;     ForwardIt next= first;++next; for(; next!= last;++next,++first)if(*first==*next)return first; return last;}
      adjacent_find (3)
      template<class ForwardIt,class BinaryPred>ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPred p){if(first== last)return last;     ForwardIt next= first;++next; for(; next!= last;++next,++first)if(p(*first,*next))return first; return last;}

      [edit]Example

      Run this code
      #include <algorithm>#include <functional>#include <iostream>#include <vector> int main(){std::vector<int> v1{0,1,2,3,40,40,41,41,5}; auto i1= std::adjacent_find(v1.begin(), v1.end()); if(i1== v1.end())std::cout<<"No matching adjacent elements\n";elsestd::cout<<"The first adjacent pair of equal elements is at "<<std::distance(v1.begin(), i1)<<", *i1 = "<<*i1<<'\n'; auto i2= std::adjacent_find(v1.begin(), v1.end(),std::greater<int>());if(i2== v1.end())std::cout<<"The entire vector is sorted in ascending order\n";elsestd::cout<<"The last element in the non-decreasing subsequence is at "<<std::distance(v1.begin(), i2)<<", *i2 = "<<*i2<<'\n';}

      Output:

      The first adjacent pair of equal elements is at 4, *i1 = 40The last element in the non-decreasing subsequence is at 7, *i2 = 41

      [edit]Defect reports

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

      DRApplied toBehavior as publishedCorrect behavior
      LWG 240C++98the predicate was appliedstd::find
      (first, last, value)- first times
      for(1,3), wherevalue was never defined      		appliedstd::min(
      (result- first)+1,
      (last- first)-1) times

      [edit]See also

      removes consecutive duplicate elements in a range
      (function template)[edit]
      finds the first two adjacent items that are equal (or satisfy a given predicate)
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/adjacent_find&oldid=180336"
      [8]ページ先頭
      ©2009-2025 Movatter.jp