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

External memory priority queue implementation. More...

#include <tpie/priority_queue.h>

Public Member Functions
	priority_queue (double f=1.0, float b=0.0625)
	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...

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.

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 77 of file priority_queue.h.

Constructor & Destructor Documentation

template<typename T , typename Comparator , typename OPQType >

tpie::priority_queue< T, Comparator, OPQType >::priority_queue	(	double	f = 1.0,
		float	b = 0.0625
	)

Constructor.

Parameters

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

Definition at line 22 of file priority_queue.h.

               {

template<typename T , typename Comparator , typename OPQType >

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

(

)

Destructor.

Definition at line 207 of file priority_queue.h.

                  {

Member Function Documentation

template<typename T , typename Comparator , typename OPQType >

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

(

)

const

Return true if queue is empty otherwise false.

Returns

Boolean - empty or not

Definition at line 358 of file priority_queue.h.

template<typename T , typename Comparator , typename OPQType >

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

(

)

Remove the top element from the priority queue.

Definition at line 299 of file priority_queue.h.

template<typename T , typename Comparator , typename OPQType >

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

Definition at line 363 of file priority_queue.h.

template<typename T , typename Comparator , typename OPQType >

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

(

const T &

x

)

Insert an element into the priority queue.

Parameters

x

The item

Definition at line 217 of file priority_queue.h.

                  {
        using tpie::priority_queue;
    }  //  ami namespace

}  //  tpie namespace

#endif

template<typename T , typename Comparator , typename OPQType >

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

(

)

const

Returns the size of the queue.

Returns

Queue size

Definition at line 353 of file priority_queue.h.

template<typename T , typename Comparator , typename OPQType >

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

(

)

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

Returns

Top element

Definition at line 325 of file priority_queue.h.

---

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

• priority_queue.h