Component bslalg_dequeiterator [Package bslalg]

Provide a primitive iterator over deque data structures. More...

Namespaces
namespace	bslalg

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage

Purpose:

Provide a primitive iterator over deque data structures.

Classes:

bslalg::DequeIterator

primitive iterator over a deque data structure

See also:

Component bslalg_dequeimputil, Component bslalg_dequeprimitives

Description:

This component provides an in-core value semantic class, bslalg::DequeIterator, that is a primitive iterator type for enumerating elements in a deque (implemented in the form of a dynamic array) knowing only its value type and a nominal block size. Conceptually, a deque is an array of block pointers, each block capable of containing a fixed number of objects. An element in the deque is identified by an iterator that consists of two pointers:

• a pointer to the block pointer array, and
• a pointer to a value within the block referred to by the first pointer.

Dereferencing the iterator dereferences the second pointer. Incrementing or decrementing the iterator consists of incrementing the value pointer, unless the iterator crosses a block boundary in which case it must increment or decrement its pointer to the block pointer. Computing the distance between two iterators involves figuring out how many block are in between and how the offsets-in-block differ.

Note that an iterator is valid as long as the element it points to still belongs to the deque and there is no reallocation of the block pointer array. Inserting elements at either end of the deque usually maintains iterator validity, but inserting enough elements at the end of the queue might force the creating of sufficiently many blocks to trigger a reallocation of the block pointer array and invalidate all iterators into the deque; how many depends on the distances between the front and back of the deque and the first/last iterator in the block pointer array (19 in the picture below).

The picture is as follows:

                       v--- Iterator to 'I': ptr to this BlockPtr
  +-----+-----+-----+-----+-----+-----+-----+-----+
  |  *  |  *  |  *  |  *  |  *  |  *  |  *  |  *  |    BlockPtr array
  +-----+-----+--|--+--|--+--|--+--|--+-----+-----+
                 |     |     |     |                  Block
                 |     |     |     |  +---+---+---+---+---+---+---+---+
                 |     |     |     `--| V | W | X | Y | Z |   |   |   |
                 |     |     |        +---+---+---+---+---+---+---+---+
                 |     |     |                  Block
                 |     |     |  +---+---+---+---+---+---+---+---+
                 |     |     `--| N | O | P | Q | R | S | T | U |
                 |     |        +---+---+---+---+---+---+---+---+
                 |     |                v---- Iterator to 'I': ptr to value
                 |     |  +---+---+---+---+---+---+---+---+
                 |     `--| F | G | H | I | J | K | L | M |
                 |        +---+---+---+---+---+---+---+---+
                 |                  Block
                 |  +---+---+---+---+---+---+---+---+
                 `--|   |   |   | A | B | C | D | E |
                    +---+---+---+---+---+---+---+---+

Depicted above is a deque consisting 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. An iterator to the I element consists of a pointer to the fourth block pointer and a pointer to the sixth element of that block. 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).

This component does not provide the full interface of a C++ standard library iterator as we do not want a dependency on iterator_traits in a package below bslstl. bslalg::DequeIterator provides the minimal necessary set of features to implement such an iterator for a standard conforming deque implementation in a higher level component.

Usage:

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