Priority queue type generator. More...
#include <priority_queue.h>
Priority queue type generator.
Implements a data structure from "Peter Sanders. Fast Priority Queues
for Cached Memory. ALENEX'99" for external memory.
Template parameters:
//! struct CmpIntGreater //! { //! bool operator () (const int & a, const int & b) const { return a>b; } //! int min_value() const { return std::numeric_limits<int>::max(); } //! }; //!
//! struct CmpIntLess //! { //! bool operator () (const int & a, const int & b) const { return a<b; } //! int min_value() const { return std::numeric_limits<int>::min(); } //! }; //!
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. 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
.