__gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc > Class Template Reference

#include <ext/pb_ds/detail/binary_heap_/binary_heap_.hpp>

Inheritance diagram for __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >:

Public Types
typedef Value_Type	value_type
typedef Cmp_Fn	cmp_fn
typedef _Alloc	allocator_type
typedef _Alloc::size_type	size_type
typedef _Alloc::difference_type	difference_type
typedef PB_DS_ENTRY_CMP_DEC	entry_cmp
typedef PB_DS_RESIZE_POLICY_DEC	resize_policy
typedef cond_dealtor < value_type, _Alloc >	cond_dealtor_t
typedef value_allocator::pointer	pointer
typedef value_allocator::const_pointer	const_pointer
typedef value_allocator::reference	reference
typedef value_allocator::const_reference	const_reference
typedef __conditional_type < simple_value, value_type, pointer >::__type	entry
typedef _Alloc::template rebind< entry >::other	entry_allocator
typedef entry_allocator::pointer	entry_pointer
typedef binary_heap_point_const_iterator_ < value_type, entry, simple_value, _Alloc >	point_const_iterator
typedef point_const_iterator	point_iterator
typedef binary_heap_const_iterator_ < value_type, entry, simple_value, _Alloc >	const_iterator
typedef const_iterator	iterator

Public Member Functions
	binary_heap ()
	binary_heap (const cmp_fn &)
	binary_heap (const binary_heap &)
void	swap (binary_heap &)
	~binary_heap ()
bool	empty () const
size_type	size () const
size_type	max_size () const
Cmp_Fn &	get_cmp_fn ()
const Cmp_Fn &	get_cmp_fn () const
point_iterator	push (const_reference)
void	modify (point_iterator, const_reference)
const_reference	top () const
void	pop ()
void	erase (point_iterator)
template<typename Pred >
size_type	erase_if (Pred)
void	erase_at (entry_pointer, size_type, false_type)
void	erase_at (entry_pointer, size_type, true_type)
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
void	clear ()
template<typename Pred >
void	split (Pred, binary_heap &)
void	join (binary_heap &)

Protected Member Functions
template<typename It >
void	copy_from_range (It, It)

Private Types
enum	{ simple_value = is_simple<value_type>::value }
typedef integral_constant< int, simple_value >	no_throw_copies_t
typedef _Alloc::template rebind< value_type >	__rebind_v
typedef __rebind_v::other	value_allocator

Private Member Functions
void	value_swap (binary_heap &)
void	insert_value (const_reference, false_type)
void	insert_value (value_type, true_type)
void	resize_for_insert_if_needed ()
void	swap_value_imp (entry_pointer, value_type, true_type)
void	swap_value_imp (entry_pointer, const_reference, false_type)
void	fix (entry_pointer)
const_reference	top_imp (true_type) const
const_reference	top_imp (false_type) const
void	resize_for_erase_if_needed ()
template<typename Pred >
size_type	partition (Pred)
void	make_heap ()
void	push_heap ()
void	pop_heap ()
bool	is_heap ()

Static Private Member Functions
static size_type	left_child (size_type)
static size_type	right_child (size_type)
static size_type	parent (size_type)

Private Attributes
size_type	m_size
size_type	m_actual_size
entry_pointer	m_a_entries

Static Private Attributes
static entry_allocator	s_entry_allocator
static value_allocator	s_value_allocator
static no_throw_copies_t	s_no_throw_copies_ind

Detailed Description

template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
class __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >

Binary heaps composed of resize and compare policies.

Based on CLRS.

Member Typedef Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::template rebind<value_type> __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::__rebind_v

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::allocator_type

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef Cmp_Fn __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::cmp_fn

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef cond_dealtor<value_type, _Alloc> __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::cond_dealtor_t

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef binary_heap_const_iterator_<value_type, entry, simple_value, _Alloc> __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::const_iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef value_allocator::const_pointer __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::const_pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef value_allocator::const_reference __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::const_reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::difference_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::difference_type

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __conditional_type<simple_value, value_type, pointer>::__type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::entry

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::template rebind<entry>::other __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::entry_allocator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef PB_DS_ENTRY_CMP_DEC __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::entry_cmp

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef entry_allocator::pointer __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::entry_pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef const_iterator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef integral_constant<int, simple_value> __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::no_throw_copies_t

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef binary_heap_point_const_iterator_<value_type, entry, simple_value, _Alloc> __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::point_const_iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef point_const_iterator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::point_iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef value_allocator::pointer __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef value_allocator::reference __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef PB_DS_RESIZE_POLICY_DEC __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::resize_policy

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::size_type

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_v::other __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::value_allocator

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef Value_Type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::value_type

Member Enumeration Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

anonymous enum

private

Enumerator
simple_value

    {
      simple_value = is_simple<value_type>::value
    };

Constructor & Destructor Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::binary_heap

(

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::binary_heap

(

const cmp_fn &

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::binary_heap

(

const binary_heap< Value_Type, Cmp_Fn, _Alloc > &

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::~binary_heap

(

)

Member Function Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

iterator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::begin ( )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

const_iterator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::begin ( ) const

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::clear

(

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

template<typename It >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::copy_from_range ( It  , It    )

protected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

bool __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::empty ( ) const

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

iterator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::end ( )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

const_iterator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::end ( ) const

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::erase ( point_iterator  )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::erase_at ( entry_pointer  , size_type  , false_type    )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::erase_at ( entry_pointer  , size_type  , true_type    )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

template<typename Pred >

size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::erase_if

(

Pred

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::fix ( entry_pointer  )

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

Cmp_Fn& __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::get_cmp_fn

(

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

const Cmp_Fn& __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::get_cmp_fn

(

)

const

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::insert_value ( const_reference  , false_type    )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::insert_value ( value_type  , true_type    )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

bool __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::is_heap ( )

inlineprivate

      {
    const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
    entry_pointer end = m_a_entries + m_size;
    bool p = std::__is_heap(m_a_entries, end, m_cmp);
    return p;
      }

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::join

(

binary_heap< Value_Type, Cmp_Fn, _Alloc > &

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

static size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::left_child ( size_type  )

inlinestaticprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::make_heap ( )

inlineprivate

      {
    const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
    entry_pointer end = m_a_entries + m_size;
    std::make_heap(m_a_entries, end, m_cmp);
    _GLIBCXX_DEBUG_ASSERT(is_heap());
      }

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::max_size ( ) const

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::modify	(	point_iterator	,
		const_reference
	)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

static size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::parent ( size_type  )

inlinestaticprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

template<typename Pred >

size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::partition ( Pred  )

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::pop ( )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::pop_heap ( )

inlineprivate

      {
    const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
    entry_pointer end = m_a_entries + m_size;
    std::pop_heap(m_a_entries, end, m_cmp);
      }

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

point_iterator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::push ( const_reference  )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::push_heap ( )

inlineprivate

      {
    if (!is_heap())
      make_heap();
    else
      {
        const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
        entry_pointer end = m_a_entries + m_size;
        std::push_heap(m_a_entries, end, m_cmp);
      }
      }

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::resize_for_erase_if_needed ( )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::resize_for_insert_if_needed ( )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

static size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::right_child ( size_type  )

inlinestaticprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::size ( ) const

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

template<typename Pred >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::split	(	Pred	,
		binary_heap< Value_Type, Cmp_Fn, _Alloc > &
	)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::swap

(

binary_heap< Value_Type, Cmp_Fn, _Alloc > &

)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::swap_value_imp ( entry_pointer  , value_type  , true_type    )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::swap_value_imp ( entry_pointer  , const_reference  , false_type    )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

const_reference __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::top ( ) const

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

const_reference __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::top_imp ( true_type  ) const

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

const_reference __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::top_imp ( false_type  ) const

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::value_swap ( binary_heap< Value_Type, Cmp_Fn, _Alloc > &  )

private

Member Data Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

entry_pointer __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::m_a_entries

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::m_actual_size

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

size_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::m_size

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

entry_allocator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::s_entry_allocator

staticprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

no_throw_copies_t __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::s_no_throw_copies_ind

staticprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

value_allocator __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::s_value_allocator

staticprivate

---

The documentation for this class was generated from the following file:

• GCC4/inc/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp