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

	  RandomIt is_heap_until( ExecutionPolicy&& policy,	   (2)	(since
       C++17)

				  RandomIt first, RandomIt last	);
	  template<  class RandomIt, class Compare >			(since
       C++11)
	  RandomIt is_heap_until( RandomIt first, RandomIt last,   (3) (const-
       expr since C++20)
	  Compare comp );
	  template< class ExecutionPolicy, class RandomIt, class
	  Compare >

	  RandomIt is_heap_until( ExecutionPolicy&& policy,	   (4)	(since
       C++17)

				  RandomIt first, RandomIt last,
	  Compare comp );

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

	  1) The heap property to be checked is	with respect to
	  operator<
	  (until C++20)
	  std::less{}
	  (since C++20).
	  3) The heap property to be checked is	with respect to	comp.
	  2,4) Same as (1,3), but executed according to	policy.
	  These	overloads participate in overload resolution only if

	  std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>  is	 true.
       (until
										    C++20)
	  std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>  is
       true. (since
										    C++20)

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.
	  -
	  Compare must meet the	requirements of	Compare.

Return value
	  The last iterator it for which range [first, it) is a	heap.

Complexity
	  Given	\(\scriptsize N\)N as std::distance(first, last):

	  1,2) \(\scriptsize O(N)\)O(N)	comparisons using
	  operator<
	  (until C++20)
	  std::less{}
	  (since C++20).
	  3,4) \(\scriptsize O(N)\)O(N)	applications of	the  comparison	 func-
       tion comp.

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.

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	(const 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		  2024.06.10		 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.1.quarterly>

home | help