File RingDeque.h

↰ Parent directory (ADS/queue)

A double ended queue on a circular vector that grows, beyond the book: the circular vector of ArrayQueue [see File ArrayQueue.h] whose capacity is a power of 2, so that a place is reduced by a mask instead of a division, and that doubles when full, the items moved in order to the front of the new vector (O( 1 ) amortized time per insertion).

Definition (ADS/queue/RingDeque.h)

Detailed Description

The four operations at the ends take O( 1 ) time, an item is read by its rank in O( 1 ), and the items lie in at most two contiguous pieces, which the moves and the visits run through at the speed of the memory. The doubling of a deque of :math:` 2^j ` places moves its :math:` 2^j ` items, so that n insertions move fewer than :math:` 2 n ` items in all, and the places are fewer than :math:` 2 n + 8 ` for n items at the largest.

Compared with std::deque, which keeps the items in blocks of 512 bytes reached by a map of pointers, there is no indirection and no allocation but at the doublings; compared with boost::circular_buffer, the vector grows by itself; compared with boost::container::devector, the items freed at one end serve the insertions at the other, so that a queue used as a FIFO never moves its items. The places are raw memory, the items being built in them when inserted and destroyed when removed.

The contracts [see File Contract.h]: front(), back() and the removals need a deque that is not empty, and operator[] a rank below size(); the invariant is that the capacity is 0 or a power of 2 at least size(). The operations are defined in RingDeque.tpp.

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/queue/impl/RingDeque.tpp

  • bit

  • compare

  • cstddef

  • cstring

  • initializer_list

  • iterator

  • memory (File Allocators.h)

  • new

  • type_traits

  • utility

Namespaces

Classes

Defines