tpie::priority_queue< T, Comparator, OPQType > Class Template Reference

External memory priority queue implementation. The top of the queue is the least element in the specified ordering. More...

#include <tpie/priority_queue.h>

Public Member Functions
	priority_queue (double f=1.0, float b=default_blocksize, stream_size_type n=std::numeric_limits< stream_size_type >::max())
	Constructor. More...
	~priority_queue ()
	Destructor. More...
void	push (const T &x)
	Insert an element into the priority queue. More...
void	pop ()
	Remove the top element from the priority queue. More...
const T &	top ()
	See what's on the top of the priority queue. More...
stream_size_type	size () const
	Returns the size of the queue. More...
bool	empty () const
	Return true if queue is empty otherwise false. More...
template<typename F >
F	pop_equals (F f)
	Pop all elements with priority equal to that of the top element, and process each by invoking f's call operator on the element. More...

Static Public Member Functions
static memory_size_type	memory_usage (stream_size_type n, float b=default_blocksize)
	Compute the maximal amount of memory it makes sence to give a queue that will contain atmount n elements. More...

Static Public Attributes
static constexpr float	default_blocksize = 0.0625

Detailed Description

template<typename T, typename Comparator = std::less<T>, typename OPQType = pq_overflow_heap<T, Comparator>>
class tpie::priority_queue< T, Comparator, OPQType >

External memory priority queue implementation. The top of the queue is the least element in the specified ordering.

Originally implemented by Lars Hvam Petersen for his Master's thesis titled "External Priority Queues in Practice", June 2007. This implementation, named "PQSequence3", is the fastest among the priority queue implementations studied in the paper. Inspiration: Sanders - Fast priority queues for cached memory (1999).

For an overview of the algorithm, refer to Sanders (1999) section 2 and figure 1, or Lars Hvam's thesis, section 4.4.

In the debug log, the priority queue reports two values setting_k and setting_m. The priority queue has a maximum capacity which is on the order of setting_m * setting_k**setting_k elements (where ** denotes exponentiation).

However, even with as little as 8 MB of memory, this maximum capacity in practice exceeds 2**48, corresponding to a petabyte-sized dataset of 32-bit integers.

Definition at line 78 of file priority_queue.h.

Constructor & Destructor Documentation

priority_queue()

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

tpie::priority_queue< T, Comparator, OPQType >::priority_queue	(	double	f = 1.0,
		float	b = default_blocksize,
		stream_size_type	n = std::numeric_limits< stream_size_type >::max()
	)

Constructor.

Parameters

f	Factor of memory that the priority queue is allowed to use.
b	Block factor

~priority_queue()

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

tpie::priority_queue< T, Comparator, OPQType >::~priority_queue

(

)

Destructor.

Member Function Documentation

empty()

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

bool tpie::priority_queue< T, Comparator, OPQType >::empty

(

)

const

Return true if queue is empty otherwise false.

Returns

Boolean - empty or not

memory_usage()

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

static memory_size_type tpie::priority_queue< T, Comparator, OPQType >::memory_usage ( stream_size_type  n, float  b = default_blocksize  )

static

Compute the maximal amount of memory it makes sence to give a queue that will contain atmount n elements.

pop()

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

void tpie::priority_queue< T, Comparator, OPQType >::pop

(

)

Remove the top element from the priority queue.

pop_equals()

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

template<typename F >

F tpie::priority_queue< T, Comparator, OPQType >::pop_equals

(

F

f

)

Pop all elements with priority equal to that of the top element, and process each by invoking f's call operator on the element.

Parameters

f	- assumed to have a call operator with parameter of type T.

Returns

The argument f

push()

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

void tpie::priority_queue< T, Comparator, OPQType >::push

(

const T &

x

)

Insert an element into the priority queue.

Parameters

x

The item

size()

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

stream_size_type tpie::priority_queue< T, Comparator, OPQType >::size

(

)

const

Returns the size of the queue.

Returns

Queue size

top()

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

const T& tpie::priority_queue< T, Comparator, OPQType >::top

(

)

See what's on the top of the priority queue.

Returns

the least element in the specified ordering

---

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

• priority_queue.h