Public Types

PRIORITY_QUEUE_GENERATOR< Tp_, Cmp_, IntM_, MaxS_, Tune_ > Class Template Reference
[Containers]

Priority queue type generator. More...

#include <priority_queue.h>

List of all members.

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 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.

The documentation for this class was generated from the following file:
Generated by  doxygen 1.7.1