Implements a priority queue using a vector-based max-heap. More...

#include <priority_queue.h>

Inheritance diagram for Priority_queue< T, Container, Less, Marker >:

Public Types
typedef Container	container_type

typedef Less	less_type

typedef container_type::value_type	value_type

typedef container_type::size_type	size_type

typedef container_type::iterator	iterator

typedef container_type::const_iterator	const_iterator

typedef container_type::allocator_type	allocator_type

Public Member Functions
	Priority_queue (Less const &less=Less(), const allocator_type &alloc=allocator_type(), const Marker &marker=Marker())
	Constructs an empty priority queue. More...

template<typename Input_iterator >
	Priority_queue (Input_iterator first, Input_iterator beyond, Less const &less=Less(), const allocator_type &alloc=allocator_type(), const Marker &marker=Marker())
	Constructs a heap of the objects between first and beyond. More...

void	assign (const container_type &container)
	Constructs a heap based on input argument. More...

void	build_heap ()
	Constructs a heap based on container contents. More...

value_type const &	top () const
	Returns a const reference to the top element of the priority queue. More...

value_type &	top ()
	Returns a reference to the top element of the priority queue. More...

bool	push (value_type const &x)
	Inserts an element in the priority queue. More...

void	pop ()
	Pops the top-most element in the priority queue. More...

void	remove (size_type i)
	Removes the element at position i from the priority queue. More...

void	decrease (size_type i, value_type const &x)
	Decreases the priority of the element at position i, where the new priority is x. More...

void	increase (size_type i, value_type const &x)
	Increases the priority of the element at position i, where the new priority is x. More...

void	update (size_type i, value_type const &x)
	Changes the priority of the element at position i, where the new priority is x. More...

void	increase (size_type i)
	Assumes that the i-th element's value has increased and rebuilds the priority queue. More...

void	decrease (size_type i)
	Assumes that the i-th element's value has decreased and rebuilds the priority queue. More...

void	update (size_type i)
	Assumes that the i-th element's value has changed and rebuilds the priority queue. More...

void	update_top ()
	Assumes that the top element's value has changed and rebuilds the priority queue. More...

size_type	size () const
	Returns the number of elements of the priority queue. More...

bool	empty () const
	Returns true if the priority queue is empty. More...

value_type const &	operator[] (size_type i) const
	Returns a const reference to the i-th element in the underlying container. More...

value_type &	operator[] (size_type i)
	Returns a reference to the i-th element in the underlying container. More...

const_iterator	begin () const
	Returns a const iterator to the first element of the underlying container. More...

const_iterator	end () const
	Returns a const iterator to the end element of the underlying container. More...

iterator	begin ()
	Returns an iterator to the first element of the underlying container. More...

iterator	end ()
	Returns an iterator to the end element of the underlying container. More...

void	swap (Priority_queue &other)
	Swaps the contents of two priority queues. More...

bool	is_valid () const
	Returns true if the priority queue has the heap property. More...

void	sort ()
	Sorts the elements of the priority queue according to the strict partial ordering defined by the object of type Less passed to the priority queue. More...

void	clear ()
	Clears the priority queue. More...

void	delete_elements ()
	Clears the priority queue, but deletes all elements first. More...

size_type	capacity () const
	Returns the capacity of the internal container. More...

bool	reserve (size_type n)
	Reserves space for array elements. More...

Private Types
typedef Less	Base

Private Member Functions
void	heapify (size_type i, size_type last)

void	heapify (size_type i)

void	reverse_heapify (size_type i)

void	decrease_key (size_type i, value_type const &x)

void	increase_key (size_type i, value_type const &x)

Static Private Member Functions
static size_type	parent (size_type i)

static size_type	left (size_type i)

static size_type	right (size_type i)

Private Attributes
container_type	m_container

Marker	m_marker

Friends
class	priority_queue_unittest::PriorityQueueTest

Detailed Description

template<typename T, typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>
class Priority_queue< T, Container, Less, Marker >

Implements a priority queue using a vector-based max-heap.

A priority queue is a container specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.

For object locality, the implementation is vector-based, rather than node-based.

The priority queue is mutable, which means that the priority of an element can be changed. See increase/decrease/update member functions. The typical use case is to change the value/priority of the root node.

We provide iterators, which can be used to visit all elements. Iterators do not visit queue elements in priority order. Iterators should not be used to change the priority of elements.

The underlying container must be constructible from an iterator range, should provide const and non-const random access iterators to access its elements, as well as the following operations:

size()
empty()
push_back()
pop_back()
swap()
clear()
capacity()
reserve()
max_size()

Template Parameters

T	Type of the elements of the priority queue.
Container	Type of the underlying container object where elements are stored. Its value_type shall be T.
Less	A binary predicate that takes two elements (of type T) and returns a bool. The expression less(a,b), where less is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.
Marker	A functor, with signature void operator()(size_t, T *), that gets called whenever an element gets a new position in the queue (including initial insert, but excluding removals). The marker can then store the element's position somewhere, for later calls to update() as needed.

Member Typedef Documentation

◆ allocator_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef container_type::allocator_type Priority_queue< T, Container, Less, Marker >::allocator_type

◆ Base

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef Less Priority_queue< T, Container, Less, Marker >::Base

private

◆ const_iterator

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef container_type::const_iterator Priority_queue< T, Container, Less, Marker >::const_iterator

◆ container_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef Container Priority_queue< T, Container, Less, Marker >::container_type

◆ iterator

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef container_type::iterator Priority_queue< T, Container, Less, Marker >::iterator

◆ less_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef Less Priority_queue< T, Container, Less, Marker >::less_type

◆ size_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef container_type::size_type Priority_queue< T, Container, Less, Marker >::size_type

◆ value_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

typedef container_type::value_type Priority_queue< T, Container, Less, Marker >::value_type

Constructor & Destructor Documentation

◆ Priority_queue() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

Priority_queue< T, Container, Less, Marker >::Priority_queue	(	Less const &	less = `Less()`,
		const allocator_type &	alloc = `allocator_type()`,
		const Marker &	marker = `Marker()`
	)

inline

Constructs an empty priority queue.

◆ Priority_queue() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

template<typename Input_iterator >

Priority_queue< T, Container, Less, Marker >::Priority_queue	(	Input_iterator	first,
		Input_iterator	beyond,
		Less const &	less = `Less()`,
		const allocator_type &	alloc = `allocator_type()`,
		const Marker &	marker = `Marker()`
	)

inline

Constructs a heap of the objects between first and beyond.

Member Function Documentation

◆ assign()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::assign ( const container_type & container )

inline

Constructs a heap based on input argument.

◆ begin() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

iterator Priority_queue< T, Container, Less, Marker >::begin ( )

inline

Returns an iterator to the first element of the underlying container.

◆ begin() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

const_iterator Priority_queue< T, Container, Less, Marker >::begin ( ) const

inline

Returns a const iterator to the first element of the underlying container.

◆ build_heap()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::build_heap ( )

inline

Constructs a heap based on container contents.

Can also be used when many elements have changed.

◆ capacity()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

size_type Priority_queue< T, Container, Less, Marker >::capacity ( ) const

inline

Returns the capacity of the internal container.

◆ clear()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::clear ( )

inline

Clears the priority queue.

◆ decrease() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::decrease ( size_type i )

inline

Assumes that the i-th element's value has decreased and rebuilds the priority queue.

◆ decrease() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::decrease	(	size_type	i,
		value_type const &	x
	)

inline

Decreases the priority of the element at position i, where the new priority is x.

◆ decrease_key()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::decrease_key	(	size_type	i,
		value_type const &	x
	)

inlineprivate

◆ delete_elements()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::delete_elements ( )

inline

Clears the priority queue, but deletes all elements first.

◆ empty()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

bool Priority_queue< T, Container, Less, Marker >::empty ( ) const

inline

Returns true if the priority queue is empty.

◆ end() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

iterator Priority_queue< T, Container, Less, Marker >::end ( )

inline

Returns an iterator to the end element of the underlying container.

◆ end() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

const_iterator Priority_queue< T, Container, Less, Marker >::end ( ) const

inline

Returns a const iterator to the end element of the underlying container.

◆ heapify() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::heapify ( size_type i )

inlineprivate

◆ heapify() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::heapify	(	size_type	i,
		size_type	last
	)

inlineprivate

◆ increase() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::increase ( size_type i )

inline

Assumes that the i-th element's value has increased and rebuilds the priority queue.

◆ increase() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::increase	(	size_type	i,
		value_type const &	x
	)

inline

Increases the priority of the element at position i, where the new priority is x.

◆ increase_key()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::increase_key	(	size_type	i,
		value_type const &	x
	)

inlineprivate

◆ is_valid()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

bool Priority_queue< T, Container, Less, Marker >::is_valid ( ) const

inline

Returns true if the priority queue has the heap property.

◆ left()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

static size_type Priority_queue< T, Container, Less, Marker >::left ( size_type i )

inlinestaticprivate

◆ operator[]() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

value_type & Priority_queue< T, Container, Less, Marker >::operator[] ( size_type i )

inline

Returns a reference to the i-th element in the underlying container.

◆ operator[]() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

value_type const & Priority_queue< T, Container, Less, Marker >::operator[] ( size_type i ) const

inline

Returns a const reference to the i-th element in the underlying container.

◆ parent()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

static size_type Priority_queue< T, Container, Less, Marker >::parent ( size_type i )

inlinestaticprivate

◆ pop()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::pop ( )

inline

Pops the top-most element in the priority queue.

◆ push()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

bool Priority_queue< T, Container, Less, Marker >::push ( value_type const & x )

inline

Inserts an element in the priority queue.

Parameters

x	value to be pushed.

Return values

true	if out-of-memory, false otherwise.

◆ remove()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::remove ( size_type i )

inline

Removes the element at position i from the priority queue.

◆ reserve()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

bool Priority_queue< T, Container, Less, Marker >::reserve ( size_type n )

inline

Reserves space for array elements.

Parameters

n	number of elements.

Return values

true	if out-of-memory, false otherwise.

◆ reverse_heapify()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::reverse_heapify ( size_type i )

inlineprivate

◆ right()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

static size_type Priority_queue< T, Container, Less, Marker >::right ( size_type i )

inlinestaticprivate

◆ size()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

size_type Priority_queue< T, Container, Less, Marker >::size ( ) const

inline

Returns the number of elements of the priority queue.

◆ sort()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::sort ( )

inline

Sorts the elements of the priority queue according to the strict partial ordering defined by the object of type Less passed to the priority queue.

The heap property of the priority queue is invalidated by this operation.

◆ swap()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::swap ( Priority_queue< T, Container, Less, Marker > & other )

inline

Swaps the contents of two priority queues.

◆ top() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

value_type & Priority_queue< T, Container, Less, Marker >::top ( )

inline

Returns a reference to the top element of the priority queue.

◆ top() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

value_type const & Priority_queue< T, Container, Less, Marker >::top ( ) const

inline

Returns a const reference to the top element of the priority queue.

◆ update() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::update ( size_type i )

inline

Assumes that the i-th element's value has changed and rebuilds the priority queue.

◆ update() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::update	(	size_type	i,
		value_type const &	x
	)

inline

Changes the priority of the element at position i, where the new priority is x.

◆ update_top()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

void Priority_queue< T, Container, Less, Marker >::update_top ( )

inline

Assumes that the top element's value has changed and rebuilds the priority queue.

Friends And Related Function Documentation

◆ priority_queue_unittest::PriorityQueueTest

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

friend class priority_queue_unittest::PriorityQueueTest

friend

Member Data Documentation

◆ m_container

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

container_type Priority_queue< T, Container, Less, Marker >::m_container

private

◆ m_marker

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>, typename Marker = NoopMarker<T>>

Marker Priority_queue< T, Container, Less, Marker >::m_marker

private

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

include/priority_queue.h

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ Base

◆ const_iterator

◆ container_type

◆ iterator

◆ less_type

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ Priority_queue() [1/2]

◆ Priority_queue() [2/2]

Member Function Documentation

◆ assign()

◆ begin() [1/2]

◆ begin() [2/2]

◆ build_heap()

◆ capacity()

◆ clear()

◆ decrease() [1/2]

◆ decrease() [2/2]

◆ decrease_key()

◆ delete_elements()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ heapify() [1/2]

◆ heapify() [2/2]

◆ increase() [1/2]

◆ increase() [2/2]

◆ increase_key()

◆ is_valid()

◆ left()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ parent()

◆ pop()

◆ push()

◆ remove()

◆ reserve()

◆ reverse_heapify()

◆ right()

◆ size()

◆ sort()

◆ swap()

◆ top() [1/2]

◆ top() [2/2]

◆ update() [1/2]

◆ update() [2/2]

◆ update_top()

Friends And Related Function Documentation

◆ priority_queue_unittest::PriorityQueueTest

Member Data Documentation

◆ m_container

◆ m_marker