MySQL  8.0.24
Source Code Documentation
Priority_queue< T, Container, Less > Class Template Reference

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

#include <priority_queue.h>

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

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())
 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())
 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_typetop ()
 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_typeoperator[] (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
 

Friends

class priority_queue_unittest::PriorityQueueTest
 

Detailed Description

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

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
TType of the elements of the priority queue.
ContainerType of the underlying container object where elements are stored. Its value_type shall be T.
LessA 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.

Member Typedef Documentation

◆ allocator_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef container_type::allocator_type Priority_queue< T, Container, Less >::allocator_type

◆ Base

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef Less Priority_queue< T, Container, Less >::Base
private

◆ const_iterator

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef container_type::const_iterator Priority_queue< T, Container, Less >::const_iterator

◆ container_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef Container Priority_queue< T, Container, Less >::container_type

◆ iterator

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef container_type::iterator Priority_queue< T, Container, Less >::iterator

◆ less_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef Less Priority_queue< T, Container, Less >::less_type

◆ size_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef container_type::size_type Priority_queue< T, Container, Less >::size_type

◆ value_type

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
typedef container_type::value_type Priority_queue< T, Container, Less >::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>>
Priority_queue< T, Container, Less >::Priority_queue ( Less const &  less = Less(),
const allocator_type alloc = allocator_type() 
)
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>>
template<typename Input_iterator >
Priority_queue< T, Container, Less >::Priority_queue ( Input_iterator  first,
Input_iterator  beyond,
Less const &  less = Less(),
const allocator_type alloc = allocator_type() 
)
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>>
void Priority_queue< T, Container, Less >::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>>
iterator Priority_queue< T, Container, Less >::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>>
const_iterator Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
size_type Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
bool Priority_queue< T, Container, Less >::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>>
iterator Priority_queue< T, Container, Less >::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>>
const_iterator Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::heapify ( size_type  i)
inlineprivate

◆ heapify() [2/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
bool Priority_queue< T, Container, Less >::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>>
static size_type Priority_queue< T, Container, Less >::left ( size_type  i)
inlinestaticprivate

◆ operator[]() [1/2]

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
value_type& Priority_queue< T, Container, Less >::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>>
value_type const& Priority_queue< T, Container, Less >::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>>
static size_type Priority_queue< T, Container, Less >::parent ( size_type  i)
inlinestaticprivate

◆ pop()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
void Priority_queue< T, Container, Less >::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>>
bool Priority_queue< T, Container, Less >::push ( value_type const &  x)
inline

Inserts an element in the priority queue.

Parameters
xvalue to be pushed.
Return values
trueif out-of-memory, false otherwise.

◆ remove()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
void Priority_queue< T, Container, Less >::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>>
bool Priority_queue< T, Container, Less >::reserve ( size_type  n)
inline

Reserves space for array elements.

Parameters
nnumber of elements.
Return values
trueif out-of-memory, false otherwise.

◆ reverse_heapify()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
void Priority_queue< T, Container, Less >::reverse_heapify ( size_type  i)
inlineprivate

◆ right()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
static size_type Priority_queue< T, Container, Less >::right ( size_type  i)
inlinestaticprivate

◆ size()

template<typename T , typename Container = std::vector<T>, typename Less = std::less<typename Container::value_type>>
size_type Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::swap ( Priority_queue< T, Container, Less > &  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>>
value_type& Priority_queue< T, Container, Less >::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>>
value_type const& Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
void Priority_queue< T, Container, Less >::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>>
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>>
container_type Priority_queue< T, Container, Less >::m_container
private

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