Queues

template<typename T, typename... Properties>
using Queue = Store<sequence<T>, fifo | lifo | by_priority, Properties...>;
class Queue

A queue: Store<sequence<T>, fifo | lifo | by_priority, Properties...>. The name Queue stands for the resolved Store type on this page.

A queue is reached by its front or top, and visited by iteration (not a bucket queue). An access tag makes a value Store a queue.

Request

Representation

Store<queue<T>, fifo>

Fifo (a deque); stable_refs too: the front stays put while elements queue behind it

Store<queue<T>, fifo, retains>

RingFifo: one vector used as a ring, kept on pop and clear

Store<queue<T>, lifo>

Lifo (a vector)

Store<queue<T>, by_priority>

Heap (a binary heap; the least element leaves first)

Store<queue<T>, by_priority, order_by<by<&T::cost>>>

Heap by the cost: the comparator given, nothing else

Store<queue<T>, by_priority, handles>

AddressableHeap: push gives a handle; update(h, e), erase(h)

Store<queue<I>, by_priority, monotone_priority>

BucketQueue (a bucket per integral priority)

Template parameters

T

Any type; orderable with by_priority (or what order_by projects it to).

Member types

value_type is T; handle_type is the representation’s handle, with handles.

Member functions

Construction (Store(), from elements) and capacity (size, empty, reserve) are as for Sets. A queue is not compared: a heap’s order is no part of its contents.

const_iterator begin() const
const_iterator end() const

The elements in the order pushed (fifo, lifo), or in no particular order (by_priority), O(n). Not with monotone_priority: a bucket queue would visit the bucket of every priority in its range.

void push(const value_type &element)
void push(value_type &&element)
template<typename ...Args>
void emplace(Args&&... args)

With handles, push and emplace give the handle that reaches the element later.

void pop()

Removes the next element; the Store must not be empty. Offered under monotone too: pop is how a queue is consumed, and monotone takes only clear away. nonempty is not a queue’s to promise, since pop empties it: a request for one is rejected.

const value_type &front() const
const value_type &back() const

fifo: the element that came first, and the one that came last.

const value_type &top() const

lifo: the element that came last; by_priority: the least by the order.

void clear()

Shrinkable queues; a monotone queue empties only by pop.

void update(const handle_type &handle, const value_type &element)
void erase(const handle_type &handle)

With handles: replaces the element of handle, which moves to its place in the order; removes it, wherever it is.

const value_type &operator[](const handle_type &handle) const

With handles: the element of handle, wherever it is in the order, O(1).

Complexity

Representation

iterate

clear

push

pop

top

memory

holds

fifo: queue (a deque, first in first out)

O(n)

O(n)

O(1)*

O(1)

O(1)

O(n), 1.2 words

a deque; stable references

ring_fifo: ring fifo (one vector used as a ring, kept on pop and clear)

O(n)

O(n)

O(1)*

O(1)

O(1)

O(n), 1.5 words

one vector as a ring; retains

lifo: stack (a vector, last in first out)

O(n)

O(n)

O(1)*

O(1)

O(1)

O(n), 1.5 words

a vector; retains

heap: binary heap (a vector, least first, by urd::Less or an order_by)

O(n)

O(n)

O(log n)*

O(log n)

O(1)

O(n), 1.5 words

a vector as a binary heap; retains

addressable_heap: addressable heap (push gives a handle to update or erase by)

O(n)

O(n)

O(log n)*

O(log n)

O(1)

O(n), 5 words

a heap of handles + a slot per handle

bucket_queue: bucket queue (a bucket per integral priority)

—

O(U)

O(1)*

O(1)*

O(1)

O(U), 6.2 words

a vector per priority

* amortized, ~ expected; n elements, U the key range, r a row’s length, k a delta’s changes. Memory is the heap it holds (urd::memory_usage): what it grows in, and per element (or key, or slot) at most so many words, each the size of an element and at least a machine word. The declared costs; what they measure to is in Benchmarks.

Example

struct Node { double f; State state; static constexpr auto identifying_members() noexcept { return Members<&Node::f, &Node::state> {}; } };
using Open = Store<queue<Node>, by_priority, order_by<by<&Node::f>>>;
auto open = Open();
open.push({ 3.5, start });
while (!open.empty()) { const auto node = open.top(); open.pop(); /* expand */ }