[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

| BucketQueue< ValueType, Ascending > Class Template Reference |

Priority queue implemented using bucket sort. More...

`#include <vigra/bucket_queue.hxx>`

Inheritance diagram for BucketQueue< ValueType, Ascending >:

List of all members.

## Public Member Functions

| BucketQueue (size_type bucket_count=256)
| Create bucket queue with.
bool | empty () const
| Queue contains no elements. Equivalent to `size() == 0`.
priority_type | maxIndex () const
| Maximum index (i.e. priority) allowed in this queue. Equivalent to `bucket_count - 1`.
void | pop ()
| Remove the current top element.
void | push (value_type const &v, priority_type priority)
| Insert new element.
size_type | size () const
| Number of elements in this queue.
const_reference | top () const
| The current top element.
priority_type | topPriority () const
| Priority of the current top element.

## Detailed Description

### template<class ValueType, bool Ascending = false>
class vigra::BucketQueue< ValueType, Ascending >

Priority queue implemented using bucket sort.

This template implements functionality similar to `std::priority_queue`, but uses a more efficient algorithm based on bucket sort. It can be used when all priorities are positive integers in a given range (typically, 0...255). By default, `BucketQueue<ValueType>` sorts the elements in descending order, i.e. like in `std::priority_queue` the largest element has highest priority. An ascending queue can be specified as `BucketQueue<ValueType, true>`. Elements with equal priorities are returned in a first-in first-out fashion.

The main difference to `std::priority_queue` is the function `push` which explicitly takes the priority of the element to be added as a second argument. This allows optimization of `ValueType`: since the bucket uniquely determines an element's priority, there is no need for `ValueType` to store redundant priority information. If compatibility to `std::priority_queue` is more important, use vigra::MappedBucketQueue.

#include <vigra/bucket_queue.hxx>
Namespace: vigra

## Constructor & Destructor Documentation

BucketQueue | ( | size_type | bucket_count = `256` | ) |

Create bucket queue with.

- bucket_count entries. Priorities must be integers in the range `[0, ..., bucket_count-1]`.

## Member Function Documentation

void push | ( | value_type const & | v,
|  | priority_type | priority
| ) |  |

Insert new element.

- v with given
- priority.

The documentation for this class was generated from the following file:

- vigra/bucket_queue.hxx

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.9.0 (Tue Nov 6 2012)