STXXL Queue

This page introduces into the stxxl::queue Container (to learn more about the structure of stxxl::stack, see section Queue).

Creating a STXXL queue

Before using a STXXL queue, we initially have to define and then to instantiate a queue object. The implementation holds the head and the tail blocks in the main memory. Prefetch and write block pools might be used to overlap I/O and computation during queue operations. A minimal configuration is shown below - the value_type (integer in our example case) is the only stricly neccessary parameter. The default configuration initializes a write_pool and a prefetch_pool of size 1.

typedef stxxl::queue<int> queue;
// create queue object with default parameters:
// write_pool size = ?, prefetch_pool size = 1, blocks2prefetch = number of blocks in the prefetch pool (i.e. 1)
queue my_queue;

The STXXL queue implementation provides three different types of constructors to customize your individual caching. See stxxl::queue more details. Additional optional template parameters are block_size, allocation_strategy, size_type, see stxxl::queue for further details.

Insert / Access / Delete elements

To insert a new value at the beginning of the queue, call push(). Accessing elements are possible on both endings of the queue, back() returns the value at the beginning, front() returns the value at the end. Deleting a value by pop() erases the first inserted element.

my_queue.push(5);  // queue now stores: |5|
my_queue.push(9);  // queue now stores: |9|5|
my_queue.push(1);  // queue now stores: |1|9|5|
x = my_queue.back();  // x = 1
y = my_queue.front();  // y = 5
my_queue.pop();  // queue now stores: |1|9|

Determine size / Check whether queue is empty

To determine the number of elements a queue currently stores, call size():

std::cout << "size of queue: " << my_queue.size() << std::endl;

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

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

A minimal working example of STXXL's queue

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

#include <stxxl/queue>
#include <iostream>

int main()
{
    typedef stxxl::queue<unsigned int> queue;
    queue my_queue;

    my_queue.push(5);
    my_queue.push(11);
    my_queue.push(3);
    my_queue.push(7);
    // my_queue now stores: |7|3|11|5|

    assert(my_queue.size() == 4);

    std::cout << "back element " << my_queue.back() << std::endl;   // prints out 7 (last inserted element)
    assert(my_queue.back() == 7);
    std::cout << "front element " << my_queue.front() << std::endl; // prints out 5 (first inserted element)
    assert(my_queue.front() == 5);
    my_queue.pop();                                                 // deletes element 5, queue now stores: |7|3|11|

    std::cout << "front element " << my_queue.front() << std::endl; // prints out 11
    assert(my_queue.front() == 11);

    return 0;
}

See examples/containers/queue2.cpp for the sourcecode of a more comprehensive example.