PriorityQueue< T, Comparator > Class Template Reference

Priority queue with erase element functionality. More...

#include <PriorityQueue.hxx>

Inheritance diagram for PriorityQueue< T, Comparator >:

Collaboration diagram for PriorityQueue< T, Comparator >:

Public Types
using	Container = std::vector< T >
using	container_type = Container
using	value_compare = Comparator
using	value_type = typename Container::value_type
using	size_type = typename Container::size_type
using	reference = typename Container::reference
using	const_reference = typename Container::const_reference
using	allocator_type = typename Container::allocator_type
using	different_type = typename Container::difference_type
using	pointer = typename Container::pointer
using	const_pointer = typename Container::const_pointer
using	iterator = typename Container::iterator
using	const_iterator = typename Container::const_iterator

Public Member Functions
bool	empty () const noexcept
	Check whether queue is empty. More...
reference	top ()
	Get top element from the queue. More...
const_reference	top () const
	Get top element from the queue. More...
void	push (value_type &&element)
	Add new element to the queue. More...
void	push (const value_type &element)
	Add new element to the queue. More...
void	pop ()
	Remove first element from the queue (from top). More...
template<typename Predicate >
size_type	erase_if (Predicate &&predicate)
	Remove all elements from queue for which predicate returns true. More...
void	clear (void) noexcept
	Remove all elements from queue. More...

Private Attributes
Container	m_container

Detailed Description

template<typename T, typename Comparator = std::less<T>>
class PriorityQueue< T, Comparator >

Priority queue with erase element functionality.

Definition at line 10 of file PriorityQueue.hxx.

Member Typedef Documentation

allocator_type

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::allocator_type = typename Container::allocator_type

Definition at line 20 of file PriorityQueue.hxx.

const_iterator

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::const_iterator = typename Container::const_iterator

Definition at line 25 of file PriorityQueue.hxx.

const_pointer

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::const_pointer = typename Container::const_pointer

Definition at line 23 of file PriorityQueue.hxx.

const_reference

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::const_reference = typename Container::const_reference

Definition at line 19 of file PriorityQueue.hxx.

Container

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::Container = std::vector<T>

Definition at line 13 of file PriorityQueue.hxx.

container_type

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::container_type = Container

Definition at line 14 of file PriorityQueue.hxx.

different_type

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::different_type = typename Container::difference_type

Definition at line 21 of file PriorityQueue.hxx.

iterator

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::iterator = typename Container::iterator

Definition at line 24 of file PriorityQueue.hxx.

pointer

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::pointer = typename Container::pointer

Definition at line 22 of file PriorityQueue.hxx.

reference

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::reference = typename Container::reference

Definition at line 18 of file PriorityQueue.hxx.

size_type

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::size_type = typename Container::size_type

Definition at line 17 of file PriorityQueue.hxx.

value_compare

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::value_compare = Comparator

Definition at line 15 of file PriorityQueue.hxx.

value_type

template<typename T , typename Comparator = std::less<T>>

using PriorityQueue< T, Comparator >::value_type = typename Container::value_type

Definition at line 16 of file PriorityQueue.hxx.

Member Function Documentation

clear()

template<typename T , typename Comparator >

void PriorityQueue< T, Comparator >::clear ( void  )

inlinenoexcept

Remove all elements from queue.

Definition at line 53 of file PriorityQueue.inl.hxx.

{ m_container.clear(); }

empty()

template<typename T , typename Comparator >

bool PriorityQueue< T, Comparator >::empty

inlinenoexcept

Check whether queue is empty.

Returns

true if queue is empty otherwise false.

Definition at line 1 of file PriorityQueue.inl.hxx.

{
  return m_container.empty();
}

Here is the caller graph for this function:

erase_if()

template<typename T , typename Comparator >

template<typename Predicate >

PriorityQueue< T, Comparator >::size_type PriorityQueue< T, Comparator >::erase_if

(

Predicate &&

predicate

)

Remove all elements from queue for which predicate returns true.

Parameters

predicate

Unary predicate which returns true if element should be removed.

Definition at line 38 of file PriorityQueue.inl.hxx.

{
  auto removedIter = std::remove_if(m_container.begin(), m_container.end(), std::forward<Predicate>(predicate));
  PriorityQueue<T, Comparator>::size_type numOfRemovedElements = 0;
 
  if (removedIter != m_container.end())
  {
    numOfRemovedElements = m_container.end() - removedIter;
    m_container.erase(removedIter, m_container.end());
    std::make_heap(m_container.begin(), m_container.end(), Comparator{});
  }
 
  return numOfRemovedElements;
}

pop()

template<typename T , typename Comparator >

void PriorityQueue< T, Comparator >::pop

Remove first element from the queue (from top).

Definition at line 30 of file PriorityQueue.inl.hxx.

{
  std::pop_heap(m_container.begin(), m_container.end(), Comparator{});
  m_container.pop_back();
}

Here is the caller graph for this function:

push() [1/2]

template<typename T , typename Comparator >

void PriorityQueue< T, Comparator >::push

(

const value_type &

element

)

Add new element to the queue.

Parameters

element

item to add to the queue

Definition at line 24 of file PriorityQueue.inl.hxx.

{
  m_container.emplace_back(element);
  std::push_heap(m_container.begin(), m_container.end(), Comparator{});
}

push() [2/2]

template<typename T , typename Comparator >

void PriorityQueue< T, Comparator >::push

(

value_type &&

element

)

Add new element to the queue.

Parameters

element

item to add to the queue

Definition at line 18 of file PriorityQueue.inl.hxx.

{
  m_container.emplace_back(std::move(element));
  std::push_heap(m_container.begin(), m_container.end(), Comparator{});
}

Here is the caller graph for this function:

top() [1/2]

template<typename T , typename Comparator >

PriorityQueue< T, Comparator >::const_reference PriorityQueue< T, Comparator >::top

inline

Get top element from the queue.

Returns

Top element from queue.

Definition at line 7 of file PriorityQueue.inl.hxx.

{
  return m_container.front();
}

Here is the caller graph for this function:

top() [2/2]

template<typename T , typename Comparator = std::less<T>>

const_reference PriorityQueue< T, Comparator >::top

(

)

const

Get top element from the queue.

Returns

Top element from queue.

Member Data Documentation

m_container

template<typename T , typename Comparator = std::less<T>>

Container PriorityQueue< T, Comparator >::m_container

private

Definition at line 74 of file PriorityQueue.hxx.

---

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

• src/util/PriorityQueue.hxx
• src/util/PriorityQueue.inl.hxx