|
BucketQueue< ValueType, Ascending > Class Template Reference |  |
Priority queue implemented using bucket sort. More...
#include <vigra/priority_queue.hxx>
Public Member Functions | |
| BucketQueue (size_type bucket_count=256) | |
| Create bucket queue with. More... | |
| 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. More... | |
| 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/priority_queue.hxx