libstdc++
Public Types | Public Member Functions | Static Public Attributes | Protected Member Functions | List of all members
__gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc > Class Template Reference
Extensions » Policy-Based Data Structures » Containers » Heap-Based » Base and Policy Classes

#include <binary_heap_.hpp>

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

Public Types

typedef _Alloc allocator_type
 
typedef Cmp_Fn cmp_fn
 
typedef cond_dealtor< value_type, _Alloc > cond_dealtor_t
 
typedef binary_heap_const_iterator_< value_type, entry, simple_value, _Alloc > const_iterator
 
typedef __rebind_v::const_pointer const_pointer
 
typedef __rebind_v::const_reference const_reference
 
typedef _Alloc::difference_type difference_type
 
typedef __conditional_type< simple_value, value_type, pointer >::__type entry
 
typedef rebind_traits< _Alloc, entry >::allocator_type entry_allocator
 
typedef entry_cmp< Value_Type, Cmp_Fn, _Alloc, is_simple< Value_Type >::value >::type entry_cmp
 
typedef rebind_traits< _Alloc, entry >::pointer entry_pointer
 
typedef const_iterator iterator
 
typedef binary_heap_point_const_iterator_< value_type, entry, simple_value, _Alloc > point_const_iterator
 
typedef point_const_iterator point_iterator
 
typedef __rebind_v::pointer pointer
 
typedef __rebind_v::reference reference
 
typedef __gnu_pbds::detail::resize_policy< typename _Alloc::size_type > resize_policy
 
typedef _Alloc::size_type size_type
 
typedef Value_Type value_type
 

Public Member Functions

 binary_heap (const binary_heap &)
 
 binary_heap (const cmp_fn &)
 
iterator begin ()
 
const_iterator begin () const
 
void clear ()
 
bool empty () const
 
iterator end ()
 
const_iterator end () const
 
void erase (point_iterator)
 
void erase_at (entry_pointer, size_type, false_type)
 
void erase_at (entry_pointer, size_type, true_type)
 
template<typename Pred >
size_type erase_if (Pred)
 
Cmp_Fn & get_cmp_fn ()
 
const Cmp_Fn & get_cmp_fn () const
 
size_type get_new_size_for_arbitrary (size_type) const
 
size_type get_new_size_for_grow () const
 
size_type get_new_size_for_shrink () const
 
bool grow_needed (size_type) const
 
void join (binary_heap &)
 
size_type max_size () const
 
void modify (point_iterator, const_reference)
 
void notify_arbitrary (size_type)
 
void notify_grow_resize ()
 
void notify_shrink_resize ()
 
void pop ()
 
point_iterator push (const_reference)
 
bool resize_needed_for_grow (size_type) const
 
bool resize_needed_for_shrink (size_type) const
 
bool shrink_needed (size_type) const
 
size_type size () const
 
template<typename Pred >
void split (Pred, binary_heap &)
 
void swap (binary_heap &)
 
void swap (resize_policy< _Alloc::size_type > &)
 
const_reference top () const
 

Static Public Attributes

static const _Alloc::size_type min_size
 

Protected Member Functions

template<typename It >
void copy_from_range (It, It)
 

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.

Definition at line 84 of file binary_heap_.hpp.

Member Typedef Documentation

◆ allocator_type

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

Definition at line 90 of file binary_heap_.hpp.

◆ cmp_fn

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

Definition at line 89 of file binary_heap_.hpp.

◆ cond_dealtor_t

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

Definition at line 95 of file binary_heap_.hpp.

◆ const_iterator

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

Definition at line 131 of file binary_heap_.hpp.

◆ const_pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >
typedef __rebind_v::const_pointer __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::const_pointer

Definition at line 110 of file binary_heap_.hpp.

◆ const_reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >
typedef __rebind_v::const_reference __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::const_reference

Definition at line 112 of file binary_heap_.hpp.

◆ difference_type

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

Definition at line 92 of file binary_heap_.hpp.

◆ entry

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

Definition at line 116 of file binary_heap_.hpp.

◆ entry_allocator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >
typedef rebind_traits<_Alloc,entry>::allocator_type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::entry_allocator

Definition at line 119 of file binary_heap_.hpp.

◆ entry_cmp

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >
typedef entry_cmp<Value_Type,Cmp_Fn,_Alloc,is_simple<Value_Type>::value>::type __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::entry_cmp

Definition at line 93 of file binary_heap_.hpp.

◆ entry_pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >
typedef rebind_traits<_Alloc,entry>::pointer __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::entry_pointer

Definition at line 121 of file binary_heap_.hpp.

◆ iterator

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

Definition at line 133 of file binary_heap_.hpp.

◆ point_const_iterator

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

Definition at line 125 of file binary_heap_.hpp.

◆ point_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

Definition at line 127 of file binary_heap_.hpp.

◆ pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >
typedef __rebind_v::pointer __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::pointer

Definition at line 109 of file binary_heap_.hpp.

◆ reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >
typedef __rebind_v::reference __gnu_pbds::detail::binary_heap< Value_Type, Cmp_Fn, _Alloc >::reference

Definition at line 111 of file binary_heap_.hpp.

◆ resize_policy

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

Definition at line 94 of file binary_heap_.hpp.

◆ size_type

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

Definition at line 91 of file binary_heap_.hpp.

◆ value_type

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

Definition at line 88 of file binary_heap_.hpp.

Member Function Documentation

◆ get_new_size_for_arbitrary()

resize_policy< _Alloc::size_type >::size_type __gnu_pbds::detail::resize_policy< _Alloc::size_type >::get_new_size_for_arbitrary ( size_type  size) const
inlineinherited

Definition at line 101 of file resize_policy.hpp.

◆ get_new_size_for_grow()

resize_policy< _Alloc::size_type >::size_type __gnu_pbds::detail::resize_policy< _Alloc::size_type >::get_new_size_for_grow
inlineinherited

Definition at line 95 of file resize_policy.hpp.

◆ get_new_size_for_shrink()

resize_policy< _Alloc::size_type >::size_type __gnu_pbds::detail::resize_policy< _Alloc::size_type >::get_new_size_for_shrink
inlineinherited

Definition at line 98 of file resize_policy.hpp.

◆ notify_arbitrary()

void __gnu_pbds::detail::resize_policy< _Alloc::size_type >::notify_arbitrary ( size_type  actual_size)
inlineinherited

Definition at line 110 of file resize_policy.hpp.

◆ notify_grow_resize()

void __gnu_pbds::detail::resize_policy< _Alloc::size_type >::notify_grow_resize
inlineinherited

Definition at line 104 of file resize_policy.hpp.

◆ notify_shrink_resize()

void __gnu_pbds::detail::resize_policy< _Alloc::size_type >::notify_shrink_resize
inlineinherited

Definition at line 107 of file resize_policy.hpp.

◆ resize_needed_for_grow()

bool __gnu_pbds::detail::resize_policy< _Alloc::size_type >::resize_needed_for_grow ( size_type  size) const
inlineinherited

Definition at line 83 of file resize_policy.hpp.

◆ resize_needed_for_shrink()

bool __gnu_pbds::detail::resize_policy< _Alloc::size_type >::resize_needed_for_shrink ( size_type  size) const
inlineinherited

Definition at line 86 of file resize_policy.hpp.

◆ swap()

void __gnu_pbds::detail::resize_policy< _Alloc::size_type >::swap ( resize_policy< _Alloc::size_type > &  other)
inlineinherited

Definition at line 80 of file resize_policy.hpp.

Member Data Documentation

◆ min_size

const _Alloc::size_type __gnu_pbds::detail::resize_policy< _Alloc::size_type >::min_size
staticinherited

Definition at line 70 of file resize_policy.hpp.

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