Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::is_heap_until

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

      RandomIt is_heap_until( ExecutionPolicy&& policy,

                              RandomIt first, RandomIt last);
      		 (2)(since C++17)
      template<class RandomIt,class Compare>
      RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp);
      		 (3)(since C++11)
      (constexpr since C++20)
      template<class ExecutionPolicy,class RandomIt,class Compare>

      RandomIt is_heap_until( ExecutionPolicy&& policy,

                              RandomIt first, RandomIt last, Compare comp);
      		 (4)(since C++17)

      Examines the range[first, last) and finds the largest range beginning atfirst which is aheap.

      1) The heap property to be checked is with respect tooperator<(until C++20)std::less{}(since C++20).
      3) The heap property to be checked is with respect tocomp.
      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
      comp - comparison function object (i.e. an object that satisfies the requirements ofCompare) which returnstrue if the first argument isless than the second.

      The signature of the comparison function should be equivalent to the following:

      bool cmp(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 typeRandomIt can be dereferenced and then implicitly converted to both of them.

      Type requirements
      -
      RandomIt must meet the requirements ofLegacyRandomAccessIterator.
      -
      Compare must meet the requirements ofCompare.

      [edit]Return value

      The last iteratorit for which range[first, it) is a heap.

      [edit]Complexity

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

      1,2)\(\scriptsize O(N)\)O(N) comparisons usingoperator<(until C++20)std::less{}(since C++20).
      3,4)\(\scriptsize O(N)\)O(N) applications of the comparison functioncomp.

      [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]Example

      Run this code
      #include <algorithm>#include <iostream>#include <vector> int main(){std::vector<int> v{3,1,4,1,5,9}; std::make_heap(v.begin(), v.end()); // probably mess up the heap    v.push_back(2);    v.push_back(6); auto heap_end= std::is_heap_until(v.begin(), v.end()); std::cout<<"all of v:  ";for(constauto& i: v)std::cout<< i<<' ';std::cout<<'\n'; std::cout<<"only heap: ";for(auto i= v.begin(); i!= heap_end;++i)std::cout<<*i<<' ';std::cout<<'\n';}

      Output:

      all of v:  9 5 4 1 1 3 2 6only heap: 9 5 4 1 1 3 2

      [edit]See also

      (C++11)
      		 checks if the given range is a max heap
      (function template)[edit]
      creates a max heap out of a range of elements
      (function template)[edit]
      adds an element to a max heap
      (function template)[edit]
      removes the largest element from a max heap
      (function template)[edit]
      turns a max heap into a range of elements sorted in ascending order
      (function template)[edit]
      finds the largest subrange that is a max heap
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/is_heap_until&oldid=180608"
      [8]ページ先頭
      ©2009-2025 Movatter.jp