PriorityQueueBinaryHeapStoreKeys< T, Key, GetKey, CompareKeys, Sequence > Class Template Reference

A priority queue implemented with a binary heap that stores the keys. More...

#include <PriorityQueueBinaryHeapStoreKeys.h>

Inheritance diagram for PriorityQueueBinaryHeapStoreKeys< T, Key, GetKey, CompareKeys, Sequence >:

List of all members.

Public Types
typedef base_type::element_type	element_type
	The element type.
typedef base_type::const_reference	const_reference
	A const reference to the element type.
typedef base_type::key_type	key_type
	The key type.
typedef base_type::size_type	size_type
	The size type.
typedef base_type::value_type	value_type
	The type stored in the binary heap.
Public Member Functions
	PriorityQueueBinaryHeapStoreKeys (const sequence_type &container=sequence_type())
	Make from a container of values.
	PriorityQueueBinaryHeapStoreKeys (size_type n)
	Construct and reserve memory for n elements.
template<class InputIterator >
	PriorityQueueBinaryHeapStoreKeys (InputIterator first, InputIterator last, const sequence_type &container=sequence_type())
	Add the values in the range to the container then make the heap.
virtual	~PriorityQueueBinaryHeapStoreKeys ()
	Destructor.
size_type	size () const
	Return the number of elements in the priority queue.
bool	empty () const
	Return true if the priority queue is empty.
const_reference	top () const
	Return the element at the top of the priority queue.
void	push (element_type x)
	Add an element to the priority queue.
void	push (element_type x, key_type k)
	Add an element with the specified key to the priority queue.
void	pop ()
	Remove the element at the top of the priority queue.
Protected Attributes
get_key_functor	_get_key
	The functor for getting a key from the element.
compare_values_functor	_compare
	The value type comparison functor.
sequence_type	_container
	The container for storing the values.

---

Detailed Description

template<typename T, typename Key = typename std::iterator_traits<T>::value_type, class GetKey = Dereference<T>, class CompareKeys = std::greater<Key>, class Sequence = std::vector< std::pair<Key,T> >>
class PriorityQueueBinaryHeapStoreKeys< T, Key, GetKey, CompareKeys, Sequence >

A priority queue implemented with a binary heap that stores the keys.

This priority queue is similar to ads::PriorityQueueBinaryHeap, but it stores the key values along with the elements in the heap. The template parameters are the same as for ads::PriorityQueueBinaryHeap. However, this class does not necessarily use the GetKey functor. Thus this class is useful when the key cannot be determined from the element.

Again, the element type is the only required parameter. The remaining parameters have default values. By default, it is assumed that the element type is a handle and that the key is obtained by dereferencing this handle.

The implementation uses the following STL heap functions.

• std::make_heap()
• std::push_heap()
• std::pop_heap()

This priority queue does not support dynamic keys. The key values are not allowed to change while an element is in the queue.

Parameters:

	T	is the element type.
	Key	is the key type.
	GetKey	is the functor that gets the key from the element. By default it is dereference<T>. This functor is used only if the push( element_type x ) member function is used.
	CompareKeys	is a functor that takes two keys as arguments and returns a boolean. It is used to order the objects in the priority queue. For greater than comparisons, the top of the priority queue holds the element with minimum key. This is the default behavior.
	Sequence	is the container for the binary heap. It is std::vector< std::pair<Key,T> > by default.

---

Constructor & Destructor Documentation

template<typename T , typename Key = typename std::iterator_traits<T>::value_type, class GetKey = Dereference<T>, class CompareKeys = std::greater<Key>, class Sequence = std::vector< std::pair<Key,T> >>

PriorityQueueBinaryHeapStoreKeys< T, Key, GetKey, CompareKeys, Sequence >::PriorityQueueBinaryHeapStoreKeys

(

const sequence_type &

container = sequence_type()

)

[inline, explicit]

Make from a container of values.

The default constructor makes an empty queue.

References PriorityQueueBinaryHeapStoreKeys< T, Key, GetKey, CompareKeys, Sequence >::_compare, and PriorityQueueBinaryHeapStoreKeys< T, Key, GetKey, CompareKeys, Sequence >::_container.

---

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

• PriorityQueueBinaryHeapStoreKeys.h