STXXL Priority Queue

This page introduces into the stxxl::priority_queue container (to learn more about the structure of stxxl::priority_queue, see section Priority Queue).

Basically, the priority queue provides insertion of new elements as well as access and deletion of the element on top. The invariant guarantees that the top element is the largest (or smallest if desired) of all inserted elements identified by comparison realized by the customizable comparator class.

Creating a STXXL priority queue

To manage the configuration of the priority queue type, we use the generator template stxxl::PRIORITY_QUEUE_GENERATOR. This generator template expects a value type (which is an integer in our example), a class which we name Comparator(a,b) to compare two given elements a and b, a internal memory limit in bytes and the number of elements to be stored (in 1024 units). See section stxxl::PRIORITY_QUEUE_GENERATOR for additional configuration parameters and information.

Thus the definition may look as follows:

// template parameter <value_type, CompareType, internal_memory_limit, number_of_elements>
typedef stxxl::PRIORITY_QUEUE_GENERATOR<int, ComparatorGreater, 64*1024*1024, 1024*1024>::result pqueue_type;

The ComparatorGreater(a,b) class is needed to compare two given elements a and b and has to be defined by hand (and before the priority queue definition above):

struct ComparatorGreater
{
    bool operator () (const int &a, const int &b) const
    { return (a > b); }

    int min_value() const
    { return std::numeric_limits<int>::max(); }
};

The compare-operator () of two elements a and b returns true, if a is larger than b, otherwise false. Consequently, this priority queue serves it's smallest element on top . The additional min_value() function ensures that Comparator(min_value(),x) is true for each and every x.

iLikewise the minimum-on-top Comparator, we can easily define a largest element on top Comparator which stores the the largest contained integer on top as well:

struct ComparatorLess
{
    bool operator () (const int & a, const int & b) const
    { return a<b; }

    int min_value() const
    { return std::numeric_limits<int>::min(); }
};

Note that CompareType must define a strict weak ordering. These and some other details are available in the Notes part of stxxl::PRIORITY_QUEUE_GENERATOR

To create a STXXL priority queue instance, a resizable buffered writing and prefetched reading pool (to overlap I/O and computation) is needed:

typedef pqueue_type::block_type block_type;
const unsigned int mem_for_pools = 16 * 1024 * 1024;  // restricts memory consumption of the pools

stxxl::read_write_pool<block_type> pool((mem_for_pools / 2) / block_type::raw_size, (mem_for_pools / 2) / block_type::raw_size);
pqueue_type my_pqueue(pool);  // creates priority queue object with read-write-pool

Insert / Access / Delete elements

To insert a new element into the priority queue, call push():

my_pqueue.push(5);

The priority queue only allows to access the top element, which is the smallest or largest element (depending on the used comparator class) of all inserted elements. Calling top() on an instance returns this element:

int x;
x = my_pqueue.top();

Erasing elements is only possible on the top of the priority queue by calling pop(). Note that after removing the element on top, the priority queue still holds the above mentioned property.

my_pqueue.pop();

Determine size / Check whether the priority queue is empty

To determine the size (i.e. the number of elements) of an instance, call size():

std::cout << "priority queue stores: " << my_pqueue.size() << " elements" << std::endl;

To check if the priority queue is empty, call empty() which returns true in case:

std::cout << "empty priority queue? " << my_pqueue.empty() << std::endl;

A minimal working example of STXXL's priority queue

(See examples/containers/pqueue1.cpp for the sourcecode of the following example).

#include <stxxl/priority_queue>
#include <iostream>
#include <limits>

// comparison struct for priority queue where top() returns the smallest contained value:
struct ComparatorGreater
{
    bool operator () (const int& a, const int& b) const
    { return (a > b); }

    int min_value() const
    { return std::numeric_limits<int>::max(); }
};

int main()
{
    typedef stxxl::PRIORITY_QUEUE_GENERATOR<int, ComparatorGreater, 128*1024*1024, 1024*1024>::result pqueue_type;
    typedef pqueue_type::block_type block_type;

    // block_type::raw_size = 262144 bytes
    // use 64 block read and write pools each to enable overlapping between I/O and computation
    const unsigned int mem_for_pools = 32 * 1024 * 1024;
    stxxl::read_write_pool<block_type> pool((mem_for_pools / 2) / block_type::raw_size, (mem_for_pools / 2) / block_type::raw_size);
    pqueue_type my_pqueue(pool);  // creates stxxl priority queue instance with read-write-pool

    my_pqueue.push(5);
    my_pqueue.push(4);
    my_pqueue.push(19);
    my_pqueue.push(1);
    assert(my_pqueue.size() == 4);

    assert(my_pqueue.top() == 1);
    STXXL_MSG("Smallest inserted value in my: " << my_pqueue.top());

    my_pqueue.pop();  // pop the 1 on top

    assert(my_pqueue.top() == 4);
    STXXL_MSG("Smallest value after 1 pop(): " << my_pqueue.top());

    return 0;
}

See examples/containers/pqueue2.cpp for the sourcecode of another small example.