PriorityQueueList< ID, R, 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 newrank)
Item	pop ()
bool	empty ()
size_t	size ()

Public Attributes
std::vector< Item >	m_List

Detailed Description

template<typename ID, typename R, typename CMP = std::less<R>>
class PriorityQueueList< ID, R, 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.

Definition at line 134 of file PriorityQueue.h.

Member Function Documentation

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

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

inline

Definition at line 186 of file PriorityQueue.h.

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

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

inline

Definition at line 148 of file PriorityQueue.h.

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

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

inline

Definition at line 163 of file PriorityQueue.h.

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

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

inline

Definition at line 158 of file PriorityQueue.h.

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

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

inline

Definition at line 143 of file PriorityQueue.h.

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

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

inline

Definition at line 191 of file PriorityQueue.h.

Member Data Documentation

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

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

Definition at line 196 of file PriorityQueue.h.

---

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

• /home/sathyam/0ad.svn/source/simulation2/helpers/PriorityQueue.h