PriorityQueueList< ID, R, H, CMP > Class Template Reference

Priority queue implemented as an unsorted array. More...

#include <PriorityQueue.h>

Classes
struct	Item

Public Member Functions
void	push (const Item &item)
Item *	find (ID id)
void	promote (ID id, R oldrank, R newrank, H newh)
Item	pop ()
bool	empty ()
size_t	size ()
void	clear ()

Public Attributes
std::vector< Item >	m_List

Detailed Description

template<typename ID, typename R, typename H, typename CMP = std::less<R>>
class PriorityQueueList< ID, R, H, CMP >

Priority queue implemented as an unsorted array.

This means pop() is O(n), but push and promote are O(1), and n is typically small (average around 50-100 in some rough tests). It seems fractionally slower than a binary heap in optimised builds, but is much simpler and less susceptible to MSVC's painfully slow debug STL.

Member Function Documentation

clear()

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

void PriorityQueueList< ID, R, H, CMP >::clear ( )

inline

empty()

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

bool PriorityQueueList< ID, R, H, CMP >::empty ( )

inline

find()

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

Item * PriorityQueueList< ID, R, H, CMP >::find ( ID  id )

inline

pop()

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

Item PriorityQueueList< ID, R, H, CMP >::pop ( )

inline

promote()

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

void PriorityQueueList< ID, R, H, CMP >::promote ( ID  id, R  oldrank, R  newrank, H  newh  )

inline

push()

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

void PriorityQueueList< ID, R, H, CMP >::push ( const Item &  item )

inline

size()

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

size_t PriorityQueueList< ID, R, H, CMP >::size ( )

inline

Member Data Documentation

m_List

template<typename ID , typename R , typename H , typename CMP = std::less<R>>

std::vector<Item> PriorityQueueList< ID, R, H, CMP >::m_List

---

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

• /home/docker/jenkins/workspace/technical-docs/source/simulation2/helpers/PriorityQueue.h