Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

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

NAME
       std::is_heap_until - std::is_heap_until

Synopsis
	  Defined in header <algorithm>
	  template<   class  RandomIt  >				(since
       C++11)
	  RandomIt  is_heap_until(  RandomIt  first,  RandomIt		(until
       C++20)
	  last );
	  template< class RandomIt >
	  constexpr   RandomIt	is_heap_until(	RandomIt		(since
       C++20)
	  first, RandomIt last );
	  template< class ExecutionPolicy, class RandomIt
	  >							 (2)	(since
       C++17)
	  RandomIt is_heap_until( ExecutionPolicy&&
	  policy, RandomIt first, RandomIt last	);
	  template<    class	RandomIt,    class    Compare	>	   (1)
       (since C++11)
	  RandomIt	is_heap_until(	    RandomIt	  first,      RandomIt
       (until C++20)
	  last,	Compare	comp );
	  template< class RandomIt, class Compare >
	  constexpr	     RandomIt	       is_heap_until(	      RandomIt
       (since C++20)
	  first, RandomIt last,	Compare	comp );		       (3)
	  template< class ExecutionPolicy, class RandomIt,
	  class	Compare	>
	  RandomIt   is_heap_until(    ExecutionPolicy&&		   (4)
       (since C++17)
	  policy, RandomIt first, RandomIt last, Compare
	  comp );

	  Examines  the	range [first, last) and	finds the largest range	begin-
       ning at first
	  which	is a max heap.

	  1) Elements are compared using operator<.
	  3) Elements are compared using the given binary comparison  function
       comp.
	  2,4)	Same  as  (1,3), but executed according	to policy. These over-
       loads do	not
	  participate in overload resolution unless
	  std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
	  (until C++20)
	  std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
	  (since C++20)	is true.

Parameters
	  first, last -	 the range of elements to examine
	  policy      -	 the execution policy to use. See execution policy for
       details.
			 comparison function object (i.e. an object that  sat-
       isfies the
			 requirements  of  Compare)  which returns true	if the
       first argument
			 is less than the second.

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

			 bool cmp(const	Type1 &a, const	Type2 &b);
	  comp	      -
			 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 re-
       gardless	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 types Type1 and Type2 must	be such	that an	object
       of type
			 RandomIt can be dereferenced and then implicitly con-
       verted to both of
			 them.

Type requirements
	  -
	  RandomIt must	meet the requirements of LegacyRandomAccessIterator.

Return value
	  The  upper  bound of the largest range beginning at first which is a
       max heap. That
	  is, the last iterator	it for which range [first, it) is a max	heap.

Complexity
	  Linear in the	distance between first and last.

Exceptions
	  The overloads	with a template	parameter named	ExecutionPolicy	report
       errors 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::termi-
       nate is called.
	      For  any	other ExecutionPolicy, the behavior is implementation-
       defined.
	    * If the algorithm fails to	 allocate  memory,  std::bad_alloc  is
       thrown.

Notes
	  A max	heap is	a range	of elements [f,l) that has the following prop-
       erties:

		     *	With  N	 = l-f,	for all	0 < i <	N, f[(i-1)/2] does not
       compare less than
		       f[i].
		     * A new element can be  added  using  std::push_heap,  in
       \(\scriptsize
		       \mathcal{O}(\log	N)\)(log N) time.
		     *	The  first element can be removed using	std::pop_heap,
       in \(\scriptsize
		       \mathcal{O}(\log	N)\)(log N) time.

Example
       // Run this code

	#include <iostream>
	#include <algorithm>
	#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	(auto 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 6
	only heap: 9 5 4 1 1 3 2

See also
	  is_heap		checks if the given range is a max heap
	  (C++11)		(function template)
	  make_heap		creates	a max heap out of a range of elements
				(function template)
	  push_heap		adds an	element	to a max heap
				(function template)
	  pop_heap		removes	the largest element from a max heap
				(function template)
				turns  a  max  heap  into  a range of elements
       sorted in ascending
	  sort_heap		order
				(function template)
	  ranges::is_heap_until	finds the largest subrange that	is a max heap
	  (C++20)		(niebloid)

http://cppreference.com		  2022.07.31		 std::is_heap_until(3)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::is_heap_until&sektion=3&manpath=FreeBSD+Ports+15.0>

home | help