* @brief A standard container using fixed-size memory allocation and
* constant-time manipulation of elements at either end.
* @ingroup Containers
* @ingroup Sequences
* Meets the requirements of a <a href="tables.html#65">container</a>, a
* <a href="tables.html#66">reversible container</a>, and a
* <a href="tables.html#67">sequence</a>, including the
* <a href="tables.html#68">optional sequence requirements</a>.
* In previous HP/SGI versions of deque, there was an extra template
* parameter so users could control the node size. This extension turned
* out to violate the C++ standard (it can be detected using template
* template parameters), and it was removed.
* @if maint
* Here's how a deque<Tp> manages memory. Each deque has 4 members:
* - Tp** _M_map
* - size_t _M_map_size
* - iterator _M_start, _M_finish
* map_size is at least 8. %map is an array of map_size pointers-to-"nodes".
* (The name %map has nothing to do with the std::map class, and "nodes"
* should not be confused with std::list's usage of "node".)
* A "node" has no specific type name as such, but it is referred to as
* "node" in this file. It is a simple array-of-Tp. If Tp is very large,
* there will be one Tp element per node (i.e., an "array" of one).
* For non-huge Tp's, node size is inversely related to Tp size: the
* larger the Tp, the fewer Tp's will fit in a node. The goal here is to
* keep the total size of a node relatively small and constant over different
* Tp's, to improve allocator efficiency.
* **** As I write this, the nodes are /not/ allocated using the high-speed
* memory pool. There are 20 hours left in the year; perhaps I can fix
* this before 2002.
* Not every pointer in the %map array will point to a node. If the initial
* number of elements in the deque is small, the /middle/ %map pointers will
* be valid, and the ones at the edges will be unused. This same situation
* will arise as the %map grows: available %map pointers, if any, will be on
* the ends. As new nodes are created, only a subset of the %map's pointers
* need to be copied "outward".
* Class invariants:
* - For any nonsingular iterator i:
* - i.node points to a member of the %map array. (Yes, you read that
* correctly: i.node does not actually point to a node.) The member of
* the %map array is what actually points to the node.
* - i.first == *(i.node) (This points to the node (first Tp element).)
* - i.last == i.first + node_size
* - i.cur is a pointer in the range [i.first, i.last). NOTE:
* the implication of this is that i.cur is always a dereferenceable
* pointer, even if i is a past-the-end iterator.
* - Start and Finish are always nonsingular iterators. NOTE: this means that
* an empty deque must have one node, a deque with <N elements (where N is
* the node buffer size) must have one node, a deque with N through (2N-1)
* elements must have two nodes, etc.
* - For every node other than start.node and finish.node, every element in
* the node is an initialized object. If start.node == finish.node, then
* [start.cur, finish.cur) are initialized objects, and the elements outside
* that range are uninitialized storage. Otherwise, [start.cur, start.last)
* and [finish.first, finish.cur) are initialized objects, and [start.first,
* start.cur) and [finish.cur, finish.last) are uninitialized storage.
* - [%map, %map + map_size) is a valid, non-empty range.
* - [start.node, finish.node] is a valid range contained within
* [%map, %map + map_size).
* - A pointer in the range [%map, %map + map_size) points to an allocated
* node if and only if the pointer is in the range
* [start.node, finish.node].
* Here's the magic: nothing in deque is "aware" of the discontiguous
* The memory setup and layout occurs in the parent, _Base, and the iterator
* class is entirely responsible for "leaping" from one node to the next.
* All the implementation routines for deque itself work only through the
* start and finish iterators. This keeps the routines simple and sane,
* and we can use other standard algorithms as well.