Priority queue type generator. More...

#include <priority_queue.h>

Public Types
enum	{ B = settings::B, m = settings::m, X = B * (settings::k - m) / settings::element_size, Buffer1Size = 32 }
enum	{ N = ComputeN::N, AI = ComputeN::AI, AE = (m / 2 < 2) ? 2 : (m / 2) }
enum	{ EConsumption = X * settings::element_size + settings::B * AE + ((MaxS_ / X) / AE) * settings::B * 1024 }
typedef priority_queue_local::find_settings < sizeof(Tp_), IntM_, MaxS_ > ::result	settings
typedef priority_queue_local::compute_N <(1<< Tune_), X, 4 *Buffer1Size >::result	ComputeN
typedef priority_queue < priority_queue_config< Tp_, Cmp_, Buffer1Size, N, AI, 2, B, AE, 2 > >	result

Detailed Description

template<class Tp_, class Cmp_, unsigned_type IntM_, unsigned MaxS_, unsigned Tune_ = 6>
class stxxl::PRIORITY_QUEUE_GENERATOR< Tp_, Cmp_, IntM_, MaxS_, Tune_ >

Priority queue type generator.

Implements a data structure from "Peter Sanders. Fast Priority Queues for Cached Memory. ALENEX'99" for external memory.

Template Parameters:

type of the contained objects (POD with no references to internal memory)

the

comparison type used to determine whether one element is smaller than another element. If Cmp_(x,y) is true, then x is smaller than y. The element returned by Q.top() is the largest element in the priority queue. That is, it has the property that, for every other element x in the priority queue, Cmp_(Q.top(), x) is false. Cmp_ must also provide min_value method, that returns value of type Tp_ that is smaller than any element of the queue x , i.e. Cmp_(Cmp_.min_value(),x) is always true .

Example: comparison object for priority queue where top() returns the smallest contained integer:

//! struct CmpIntGreater
//! {
//!   bool operator () (const int & a, const int & b) const { return a>b; }
//!   int min_value() const  { return std::numeric_limits<int>::max(); }
//! };
//!

Example: comparison object for priority queue where top() returns the largest contained integer:

//! struct CmpIntLess
//! {
//!   bool operator () (const int & a, const int & b) const { return a<b; }
//!   int min_value() const  { return std::numeric_limits<int>::min(); }
//! };
//!

Note that Cmp_ must define strict weak ordering. (see what it is)

IntM_ upper limit for internal memory consumption in bytes.
MaxS_ upper limit for number of elements contained in the priority queue (in 1024 units). Example: if you are sure that priority queue contains no more than one million elements in a time, then the right parameter is (1000000/1024)= 976 .
Tune_ tuning parameter. Try to play with it if the code does not compile (larger than default values might help). Code does not compile if no suitable internal parameters were found for given IntM_ and MaxS_. It might also happen that given IntM_ is too small for given MaxS_, try larger values.
PRIORITY_QUEUE_GENERATOR is template meta program that searches for 7 configuration parameters of stxxl::priority_queue that both minimize internal memory consumption of the priority queue to match IntM_ and maximize performance of priority queue operations. Actual memory consumption might be larger (use stxxl::priority_queue::mem_cons() method to track it), since the search assumes rather optimistic schedule of push'es and pop'es for the estimation of the maximum memory consumption. To keep actual memory requirements low increase the value of MaxS_ parameter.
For functioning a priority queue object requires two pools of blocks (See constructor of priority_queue ). To construct <stxxl> block pools you might need block type that will be used by priority queue. Note that block's size and hence it's type is generated by the PRIORITY_QUEUE_GENERATOR in compile type from IntM_, MaxS_ and sizeof(Tp_) and not given directly by user as a template parameter. Block type can be extracted as PRIORITY_QUEUE_GENERATOR<some_parameters>::result::block_type . For an example see p_queue.cpp . Configured priority queue type is available as PRIORITY_QUEUE_GENERATOR<>::result.

Examples:: containers/pq_benchmark.cpp, and containers/test_pqueue.cpp.

Definition at line 1020 of file priority_queue.h.