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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::pop_heap - std::pop_heap

Synopsis
	  Defined in header <algorithm>
	  template< class RandomIt >				   (1) (const-
       expr since C++20)
	  void pop_heap( RandomIt first, RandomIt last );
	  template< class RandomIt, class Compare >
	  void pop_heap( RandomIt first, RandomIt last,	Compare	   (2) (const-
       expr since C++20)
	  comp );

	  Swaps	 the value in the position first and the value in the position
       last - 1	and
	  makes	the subrange [first, last - 1) into a heap. This has  the  ef-
       fect of removing
	  the first element from the heap [first, last).

	  1) [first, last) is a	heap with respect to
	  operator<
	  (until C++20)
	  std::less{}
	  (since C++20).
	  2) [first, last) is a	heap with respect to comp.

	  If [first, last) not a non-empty heap, the behavior is undefined.

	  If any of the	following conditions is	satisfied, the behavior	is un-
       defined:

	    * [first, last) is empty.
	    * [first, last) is not a heap.

	    * The type of *first is not	Swappable.	     (until C++11)
	    * RandomIt is not ValueSwappable.
	    * The type of *first is not	MoveConstructible.   (since C++11)
	    * The type of *first is not	MoveAssignable.

Parameters
	  first, last -	 the non-empty heap to modify
			 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.

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

	  1) At	most \(\scriptsize 2\log(N)\)2log(N) comparisons using
	  operator<
	  (until C++20)
	  std::less{}
	  (since C++20).
	  2)  At most \(\scriptsize 2\log(N)\)2log(N) applications of the com-
       parison function
	  comp.

Example
       // Run this code

	#include <algorithm>
	#include <iostream>
	#include <string_view>
	#include <type_traits>
	#include <vector>

	void println(std::string_view rem, const auto& v)
	{
	    std::cout << rem;
	    if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
		std::cout << v;
	    else
		for (int e : v)
		    std::cout << e << '	';
	    std::cout << '\n';
	}

	int main()
	{
	    std::vector<int> v{3, 1, 4,	1, 5, 9};

	    std::make_heap(v.begin(), v.end());
	    println("after make_heap: ", v);

	    std::pop_heap(v.begin(), v.end()); // moves	the largest to the end
	    println("after pop_heap:  ", v);

	    int	largest	= v.back();
	    println("largest element: ", largest);

	    v.pop_back(); // actually removes the largest element
	    println("after pop_back:  ", v);
	}

Output:
	after make_heap: 9 5 4 1 1 3
	after pop_heap:	 5 3 4 1 1 9
	largest	element: 9
	after pop_back:	 5 3 4 1 1

	  Defect reports

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

	     DR	   Applied to	      Behavior as published		  Cor-
       rect behavior
	  LWG  1205  C++98	the behavior was unclear if	       the be-
       havior is undefined
			      [first, last) is empty		      in  this
       case

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

http://cppreference.com		  2024.06.10		      std::pop_heap(3)

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

home | help