bslalg_dequeimputil

Macros
#define	bslalg_DequeImpUtil   bslalg::DequeImpUtil
	This alias is defined for backward compatibility.

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

bslalg_dequeprimitives, 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>).

Macro Definition Documentation

bslalg_DequeImpUtil

#define bslalg_DequeImpUtil   bslalg::DequeImpUtil