Component bslalg_dequeimputil [Package bslalg]

Provide basic parameters and primitive data structures for deques. More...

Namespaces
namespace	bslalg
Defines
#define	bslalg_DequeImpUtil   bslalg::DequeImpUtil

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage

Purpose:

Provide basic parameters and primitive data structures for deques.

Classes:

bslalg::DequeImpUtil

deque parameters and primitive data structures

See also:

Component bslalg_dequeprimitives, Component bslalg_arrayprimitives

Description:

This component provides primitive data structures for implementing a deque knowing only its value type and the number of objects in a block. Conceptually, a deque is an array of blocks pointers, each block capable of containing a fixed number of objects. An element in the deque is identified by an iterator that consists of a pointer to the block pointer array, and a pointer to a value. A deque implementation is parameterized by the VALUE_TYPE and a BLOCK_LENGTH (fixed number of objects in a block). bslalg::DequeImpUtil provides a namespace for the following types and constants:

  Type                   Short description
  ----                   -----------------
  ValueType              An alias for the templatized 'VALUE_TYPE'
  Block                  An array (of length 'BLOCK_LENGTH') of 'ValueType'
  BlockPtr               An alias for a pointer to a block

  Constant               Short description
  --------               -----------------
  BLOCK_BYTES            Number of bytes in a block
  BLOCK_ARRAY_PADDING    Number of empty blocks to keep at both ends of the
                         block array pointer (one on each side).

The picture is as follows:

  +-----+-----+-----+-----+-----+-----+-----+-----+
  |  *  |  *  |  *  |  *  |  *  |  *  |  *  |  *  |  (BlockPtr array)
  +-----+-----+--|--+--|--+--|--+--|--+-----+-----+
                 |     |     |     |                     Block
                 |     |     |     |  +---+---+---+---+---+---+---+---+
                 |     |     |     `--| V | W | X | Y | Z |   |   |   |
                 |     |     |        +---+---+---+---+---+---+---+---+
                 |     |     |                      Block
                 |     |     |  +---+---+---+---+---+---+---+---+
                 |     |     `--| N | O | P | Q | R | S | T | U |
                 |     |        +---+---+---+---+---+---+---+---+
                 |     |                      Block
                 |     |  +---+---+---+---+---+---+---+---+
                 |     `--| F | G | H | I | J | K | L | M |
                 |        +---+---+---+---+---+---+---+---+
                 |                      Block
                 |  +---+---+---+---+---+---+---+---+
                 `--|   |   |   | A | B | C | D | E |
                    +---+---+---+---+---+---+---+---+

Depicted above is a deque consisting of an array of eight block pointers, only four actually used to point to blocks of eight elements. In the first block, the first three elements are uninitialized, and the twenty six elements follow in sequence across the different blocks. The value of the corresponding deque would be [ A, B, C, ... X, Y, Z ], its logical length 26, and its capacity would be 19 (the minimum number of prepend/append to force a reallocation of the block pointer array).

Usage:

This component is for use by the bslalg package. Other clients should use the STL deque (in header <deque>).

---

Define Documentation

#define bslalg_DequeImpUtil   bslalg::DequeImpUtil