Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::is_permutation

      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
      is_permutation
      (C++11)


      C library
      Numeric operations
      Operations on uninitialized memory
       
      Defined in header<algorithm>
      template<class ForwardIt1,class ForwardIt2>

      bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,

                           ForwardIt2 first2);
      		 (1)(since C++11)
      (constexpr since C++20)
      template<class ForwardIt1,class ForwardIt2,

               class BinaryPredicate>
      bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,

                           ForwardIt2 first2, BinaryPredicate p);
      		 (2)(since C++11)
      (constexpr since C++20)
      template<class ForwardIt1,class ForwardIt2>

      bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,

                           ForwardIt2 first2, ForwardIt2 last2);
      		 (3)(since C++14)
      (constexpr since C++20)
      template<class ForwardIt1,class ForwardIt2,

               class BinaryPredicate>
      bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                           ForwardIt2 first2, ForwardIt2 last2,

                           BinaryPredicate p);
      		 (4)(since C++14)
      (constexpr since C++20)

      Checks whether[first1, last1) is apermutation of a range starting fromfirst2:

      • For overloads(1,2), the second range hasstd::distance(first1, last1) elements.
      • For overloads(3,4), the second range is[first2, last2).
      1,3) Elements are compared usingoperator==.
      2,4) Elements are compared using the given binary predicatep.

      IfForwardIt1 andForwardIt2 have differentvalue types, the program is ill-formed.

      If the comparison function is not anequivalence relation, the behavior is undefined.

      Contents

      [edit]Parameters

      first1, last1 - the pair of iterators defining the firstrange of elements to compare
      first2, last2 - the pair of iterators defining the secondrange of elements to compare
      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 objects of typesInputIt1 andInputIt2 can be dereferenced and then implicitly converted toType1 andType2 respectively.​

      Type requirements
      -
      ForwardIt1, ForwardIt2 must meet the requirements ofLegacyForwardIterator.

      [edit]Return value

      true if the range[first1, last1) is a permutation of the range[first2, last2),false otherwise.

      [edit]Complexity

      Given\(\scriptsize N\)N asstd::distance(first1, last1):

      1) Exactly\(\scriptsize N\)N comparisons usingoperator== if the two ranges are equal, otherwise\(\scriptsize O(N^2)\)O(N2
      )       comparisons in the worst case.
      2) Exactly\(\scriptsize N\)N applications of the predicatep if the two ranges are equal, otherwise\(\scriptsize O(N^2)\)O(N2
      )       applications in the worst case.
      3,4) IfForwardIt1 andForwardIt2 are bothLegacyRandomAccessIterator, andlast1- first1!= last2- first2 istrue, no comparison will be made.
      Otherwise:
      3) Exactly\(\scriptsize N\)N comparisons usingoperator== if the two ranges are equal, otherwise\(\scriptsize O(N^2)\)O(N2
      )       comparisons in the worst case.
      4) Exactly\(\scriptsize N\)N applications of the predicatep if the two ranges are equal, otherwise\(\scriptsize O(N^2)\)O(N2
      )       applications in the worst case.

      [edit]Possible implementation

      template<class ForwardIt1,class ForwardIt2>bool is_permutation(ForwardIt1 first, ForwardIt1 last,                    ForwardIt2 d_first){// skip common prefixstd::tie(first, d_first)=std::mismatch(first, last, d_first); // iterate over the rest, counting how many times each element// from [first, last) appears in [d_first, d_last)if(first!= last){        ForwardIt2 d_last=std::next(d_first,std::distance(first, last));for(ForwardIt1 i= first; i!= last;++i){if(i!=std::find(first, i,*i))continue;// this *i has been checked auto m=std::count(d_first, d_last,*i);if(m==0||std::count(i, last,*i)!= m)returnfalse;}}returntrue;}

      [edit]Note

      Thestd::is_permutation can be used intesting, namely to check the correctness of rearranging algorithms (e.g. sorting, shuffling, partitioning). Ifx is an original range andy is apermuted range thenstd::is_permutation(x, y)==true means thaty consist of"the same" elements, maybe staying at other positions.

      [edit]Example

      Run this code
      #include <algorithm>#include <iostream> template<typename Os,typename V>Os& operator<<(Os& os,const V& v){    os<<"{ ";for(constauto& e: v)        os<< e<<' ';return os<<'}';} int main(){staticconstexprauto v1={1,2,3,4,5};staticconstexprauto v2={3,5,4,1,2};staticconstexprauto v3={3,5,4,1,1}; std::cout<< v2<<" is a permutation of "<< v1<<": "<<std::boolalpha<< std::is_permutation(v1.begin(), v1.end(), v2.begin())<<'\n'<< v3<<" is a permutation of "<< v1<<": "<< std::is_permutation(v1.begin(), v1.end(), v3.begin())<<'\n';}

      Output:

      { 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false

      [edit]See also

      generates the next greater lexicographic permutation of a range of elements
      (function template)[edit]
      generates the next smaller lexicographic permutation of a range of elements
      (function template)[edit]
      specifies that arelation imposes an equivalence relation
      (concept)[edit]
      determines if a sequence is a permutation of another sequence
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/is_permutation&oldid=180537"
      [8]ページ先頭
      ©2009-2025 Movatter.jp