bslstl_deque.h

Go to the documentation of this file.

/// @file bslstl_deque.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslstl_deque.h                                                     -*-C++-*-
#ifndef INCLUDED_BSLSTL_DEQUE
#define INCLUDED_BSLSTL_DEQUE
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslstl_deque bslstl_deque
/// @brief  Provide an STL-compliant deque class.
/// @addtogroup bsl
/// @{
/// @addtogroup bslstl
/// @{
/// @addtogroup bslstl_deque
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslstl_deque-purpose"> Purpose</a>
/// * <a href="#bslstl_deque-classes"> Classes </a>
/// * <a href="#bslstl_deque-canonical-header"> Canonical Header </a>
/// * <a href="#bslstl_deque-description"> Description </a>
///   * <a href="#bslstl_deque-requirements-on-value_type"> Requirements on VALUE_TYPE </a>
///   * <a href="#bslstl_deque-glossary"> Glossary </a>
///   * <a href="#bslstl_deque-memory-allocation"> Memory Allocation </a>
///     * <a href="#bslstl_deque-bslma-style-allocators"> bslma-Style Allocators </a>
///   * <a href="#bslstl_deque-operations"> Operations </a>
///   * <a href="#bslstl_deque-exceptional-behavior"> Exceptional Behavior </a>
///   * <a href="#bslstl_deque-usage"> Usage </a>
///     * <a href="#bslstl_deque-example-1-using-a-deque-to-implement-a-laundry-queue"> Example 1: Using a deque to Implement a Laundry Queue </a>
///
/// # Purpose {#bslstl_deque-purpose}
/// Provide an STL-compliant deque class.
///
/// # Classes {#bslstl_deque-classes}
///
/// -  bsl::deque: STL-compliant deque template
///
/// # Canonical Header {#bslstl_deque-canonical-header}
/// bsl_deque.h
///
/// @see  bslstl_vector
///
/// # Description {#bslstl_deque-description}
/// This component defines a single class template, `bsl::deque`,
/// implementing the standard sequential container, `std::deque`, holding a
/// dynamic sequence of values of a template parameter type.
///
/// An instantiation of `deque` is an allocator-aware, value-semantic type
/// whose salient attributes are its size (number of contained elements) and the
/// (ordered) sequence of values the deque contains.  If `deque` is instantiated
/// with a value type that is not value-semantic, then the deque will not retain
/// all of its value-semantic qualities.  In particular, if a value type cannot
/// be tested for equality, then a `deque` containing elements of that type
/// cannot be tested for equality.  It is even possible to instantiate `deque`
/// with a value type that does not have a copy-constructor, in which case the
/// `deque` will not be copyable.
///
/// A deque meets the requirements of a sequential container with random access
/// iterators in section [deque] of the C++ standard.  The `deque` implemented
/// here adheres to the C++11 standard when compiled with a C++11 compiler, and
/// makes the best approximation when compiled with a C++03 compiler.  In
/// particular, for C++03 we emulate move semantics, but limit forwarding (in
/// `emplace`) to `const` lvalues, and make no effort to emulate `noexcept` or
/// initializer-lists.
///
/// ## Requirements on VALUE_TYPE {#bslstl_deque-requirements-on-value_type}
///
///
/// A `deque` is a fully Value-Semantic Type (see @ref bsldoc_glossary ) only if
/// the supplied `VALUE_TYPE` template parameter is fully value-semantic.  It is
/// possible to instantiate a `deque` with a `VALUE_TYPE` parameter that does
/// not have a full set of value-semantic operations, but then some methods of
/// the container may not be instantiable.  The following terminology, adopted
/// from the C++11 standard, is used in the function documentation of `deque`
/// to describe a function's requirements for the `VALUE_TYPE` template
/// parameter.  These terms are also defined in section [17.6.3.1] of the C++11
/// standard.  Note that, in the context of a `deque` instantiation, the
/// requirements apply specifically to the deque's entry type, `value_type`,
/// which is an alias for `VALUE_TYPE`.
///
/// ## Glossary {#bslstl_deque-glossary}
///
///
/// @code
/// Legend
/// ------
/// 'X'    - denotes an allocator-aware container type (e.g., 'deque')
/// 'T'    - 'value_type' associated with 'X'
/// 'A'    - type of the allocator used by 'X'
/// 'm'    - lvalue of type 'A' (allocator)
/// 'p',   - address ('T *') of uninitialized storage for a 'T' within an 'X'
/// 'rv'   - rvalue of type (non-'const') 'T'
/// 'v'    - rvalue or lvalue of type (possibly 'const') 'T'
/// 'args' - 0 or more arguments
/// @endcode
/// The following terms are used to more precisely specify the requirements on
/// template parameter types in function-level documentation.
///
///  *default-insertable*: `T` has a default constructor.  More precisely, `T`
///    is `default-insertable` into `X` means that the following expression is
///    well-formed:
///    `allocator_traits<A>::construct(m, p)`
/// 
///  *move-insertable*: `T` provides a constructor that takes an rvalue of type
///    (non-`const`) `T`.  More precisely, `T` is `move-insertable` into `X`
///    means that the following expression is well-formed:
///    `allocator_traits<A>::construct(m, p, rv)`
/// 
///  *copy-insertable*: `T` provides a constructor that takes an lvalue or
///    rvalue of type (possibly `const`) `T`.  More precisely, `T` is
///    `copy-insertable` into `X` means that the following expression is
///    well-formed:
///    `allocator_traits<A>::construct(m, p, v)`
/// 
///  *move-assignable*: `T` provides an assignment operator that takes an rvalue
///    of type (non-`const`) `T`.
/// 
///  *copy-assignable*: `T` provides an assignment operator that takes an lvalue
///    or rvalue of type (possibly `const`) `T`.
/// 
///  *emplace-constructible*: `T` is `emplace-constructible` into `X` from
///    `args` means that the following expression is well-formed:
///    `allocator_traits<A>::construct(m, p, args)`
/// 
///  *erasable*: `T` provides a destructor.  More precisely, `T` is `erasable`
///    from `X` means that the following expression is well-formed:
///    `allocator_traits<A>::destroy(m, p)`
/// 
///  *equality-comparable*: The type provides an equality-comparison operator
///    that defines an equivalence relationship and is both reflexive and
///    transitive.
///
/// ## Memory Allocation {#bslstl_deque-memory-allocation}
///
///
/// The type supplied as a deque's `ALLOCATOR` template parameter determines
/// how that deque will allocate memory.  The `deque` template supports
/// allocators meeting the requirements of the C++03 standard, in addition it
/// supports scoped-allocators derived from the `bslma::Allocator` memory
/// allocation protocol.  Clients intending to use `bslma` style allocators
/// should use the template's default `ALLOCATOR` type: The default type for the
/// `ALLOCATOR` template parameter, `bsl::allocator`, provides a C++11
/// standard-compatible adapter for a `bslma::Allocator` object.
///
/// ### bslma-Style Allocators {#bslstl_deque-bslma-style-allocators}
///
///
/// If the (template parameter) type `ALLOCATOR` of a `deque` instantiation' is
/// `bsl::allocator`, then objects of that deque type will conform to the
/// standard behavior of a `bslma`-allocator-enabled type.  Such a deque
/// accepts an optional `bslma::Allocator` argument at construction.  If the
/// address of a `bslma::Allocator` object is explicitly supplied at
/// construction, it is used to supply memory for the deque throughout its
/// lifetime; otherwise, the deque will use the default allocator installed at
/// the time of the deque's construction (see @ref bslma_default ).  In addition to
/// directly allocating memory from the indicated `bslma::Allocator`, a deque
/// supplies that allocator's address to the constructors of contained objects
/// of the (template parameter) `VALUE_TYPE` if it defines the
/// `bslma::UsesBslmaAllocator` trait.
///
/// ## Operations {#bslstl_deque-operations}
///
///
/// This section describes the run-time complexity of operations on instances
/// of `deque`:
/// @code
/// Legend
/// ------
/// 'V'                - (template parameter) 'VALUE_TYPE' of the deque
/// 'a', 'b'           - two distinct objects of type 'deque<V>'
/// 'rv'               - modifiable rvalue of type 'deque<V>'
/// 'n', 'm'           - number of elements in 'a' and 'b', respectively
/// 'i'                - valid index into the deque
/// 'k'                - non-negative integer
/// 'al                - an STL-style memory allocator
/// 'i1', 'i2'         - two iterators defining a sequence of 'V' objects
/// 'rg'               - range of objects convertible to 'V'
/// 'il'               - object of type 'std::initializer_list<V>'
/// 'lil'              - length of 'il'
/// 'vt'               - object of type 'VALUE_TYPE'
/// 'rvt'              - modifiable rvalue of type 'VALUE_TYPE'
/// 'p1', 'p2'         - two 'const_iterator's belonging to 'a'
/// 'distance(i1, i2)' - number of elements in the range '[i1 .. i2)'
/// 'minHalf(p1)'      - 'min(distance(a.begin(), p1), distance(p1, a.end()))'
/// 'args'             - 0 or more arguments
///
/// |-----------------------------------------+-------------------------------|
/// | Operation                               | Complexity                    |
/// |=========================================+===============================|
/// | deque<V> a       (default construction) | O[1]                          |
/// | deque<V> a(al)                          |                               |
/// |-----------------------------------------+-------------------------------|
/// | deque<V> a(b)    (copy construction)    | O[n]                          |
/// | deque<V> a(b, al)                       |                               |
/// |-----------------------------------------+-------------------------------|
/// | deque<V> a(rv)   (move construction)    | O[1] if 'a' and 'rv' use the  |
/// | deque<V> a(rv, al)                      | same allocator; O[n] otherwise|
/// |-----------------------------------------+-------------------------------|
/// | deque<V> a(k)                           | O[k]                          |
/// | deque<V> a(k, al)                       |                               |
/// |-----------------------------------------+-------------------------------|
/// | deque<V> a(k, vt)                       | O[k]                          |
/// | deque<V> a(k, vt, al)                   |                               |
/// |-----------------------------------------+-------------------------------|
/// | deque<V> a(i1, i2)                      | O[distance(i1, i2)]           |
/// | deque<V> a(i1, i2, al)                  |                               |
/// |-----------------------------------------+-------------------------------|
/// | deque<V> a(from_range, rg)              | O[ranges::distance(rg)]       |
/// | deque<V> a(from_range, rg, al)          |                               |
/// |-----------------------------------------+-------------------------------|
/// | deque<V> a(il)                          | O[lil]                        |
/// | deque<V> a(il, al)                      |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.~deque<V>()   (destruction)           | O[n]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.assign(k, vt)                         | O[k]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.assign(i1, i2)                        | O[distance(i1, i2)]           |
/// |-----------------------------------------+-------------------------------|
/// | a.assign_range(rg)                      | O[ranges::distance(rg)]       |
/// |-----------------------------------------+-------------------------------|
/// | a.assign(il)                            | O[lil]                        |
/// |-----------------------------------------+-------------------------------|
/// | get_allocator()                         | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.begin(), a.end()                      | O[1]                          |
/// | a.cbegin(), a.cend()                    |                               |
/// | a.rbegin(), a.rend()                    |                               |
/// | a.crbegin(), a.crend()                  |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.size()                                | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.max_size()                            | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.resize(k)                             | O[k]                          |
/// | a.resize(k, vt)                         |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.empty()                               | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.reserve(k)                            | O[k]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.shrink_to_fit()                       | O[n]                          |
/// |-----------------------------------------+-------------------------------|
/// | a[i]                                    | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.at(i)                                 | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.front()                               | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.back()                                | O[1]                          |
/// |-----------------------------------------+-------------------------------|
/// | a.push_back(vt)                         | O[1]                          |
/// | a.push_front(vt)                        |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.push_back(rvt)                        | O[1]                          |
/// | a.push_front(rvt)                       |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.pop_back()                            | O[1]                          |
/// | a.pop_front()                           |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.emplace_back(args)                    | O[1]                          |
/// | a.emplace_front(args)                   |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.prepend_range(rg)                     | O[ranges::distance(rg)]       |
/// | a.append_range(rg)                      |                               |
/// |-----------------------------------------+-------------------------------|
/// | a.emplace(p1, args)                     | O[1 + minHalf(p1)]            |
/// |-----------------------------------------+-------------------------------|
/// | a.insert(p1, vt)                        | O[1 + minHalf(p1)]            |
/// |-----------------------------------------+-------------------------------|
/// | a.insert(p1, rvt)                       | O[1 + minHalf(p1)]            |
/// |-----------------------------------------+-------------------------------|
/// | a.insert(p1, k, vt)                     | O[k + minHalf(p1)]            |
/// |-----------------------------------------+-------------------------------|
/// | a.insert(p1, i1, i2)                    | O[distance(i1, i2)            |
/// |                                         |                + minHalf(p1)] |
/// |-----------------------------------------+-------------------------------|
/// | a.insert_range(p1, rg)                  | O[ranges::distance(rg)        |
/// |                                         |                + minHalf(p1)] |
/// |-----------------------------------------+-------------------------------|
/// | a.insert(p1, il)                        | O[lil + minHalf(p1)]          |
/// |-----------------------------------------+-------------------------------|
/// | a.erase(p1)                             | O[1 + minHalf(p1)]            |
/// |-----------------------------------------+-------------------------------|
/// | a.erase(p1, p2)                         | O[distance(p1, p2)            |
/// |                                         |  + min(distance(a.begin, p1), |
/// |                                         |        distance(p2, a.end())] |
/// |-----------------------------------------+-------------------------------|
/// | a.swap(b), swap(a, b)                   | O[1] if 'a' and 'b' use the   |
/// |                                         | same allocator; O[n + m]      |
/// |                                         | otherwise                     |
/// |-----------------------------------------+-------------------------------|
/// | a.clear()                               | O[n]                          |
/// |-----------------------------------------+-------------------------------|
/// | a = b;           (copy assignment)      | O[n]                          |
/// |-----------------------------------------+-------------------------------|
/// | a = rv;          (move assignment)      | O[1] if 'a' and 'rv' use the  |
/// |                                         | same allocator; O[n] otherwise|
/// |-----------------------------------------+-------------------------------|
/// | a = il;                                 | O[lil]                        |
/// |-----------------------------------------+-------------------------------|
/// | a == b, a != b                          | O[n]                          |
/// |-----------------------------------------+-------------------------------|
/// | a < b, a <= b, a > b, a >= b            | O[n]                          |
/// |-----------------------------------------+-------------------------------|
/// @endcode
///
/// ## Exceptional Behavior {#bslstl_deque-exceptional-behavior}
///
///
/// Since this component is below the BSL STL, we centralize all the exceptional
/// behavior into a `bslstl::StdExceptUtil` class, which has a dual purpose:
///
/// * Remove the dependency of this header on the `<exception>` header, so that
///   this implementation can offer an exception handler with the native
///   exceptions, and so that all the C-strings may be defined in a single
///   library (`bsl`) and not in all the translation units including this
///   header.
/// * Allow installation of exception handlers at a higher level to throw BSL
///   STL exceptions (which differ from the native exceptions) and thus
///   establish a full standard compliance for this component when used as
///   `bsl::deque` in the BSL STL.
///
/// ## Usage {#bslstl_deque-usage}
///
///
/// In this section we show intended usage of this component.
///
/// ### Example 1: Using a deque to Implement a Laundry Queue {#bslstl_deque-example-1-using-a-deque-to-implement-a-laundry-queue}
///
///
/// Suppose we want to define a class to maintain a process queue of names of
/// customers who are dropping off their laundry at a drop-off laundry service.
/// We can accomplish this by defining a new class characterizing a
/// laundry-process queue that uses `bsl::deque` in its implementation.
///
/// The process queue provides two methods, `push` and `expeditedPush`, for
/// inserting names of customers onto the queue.  When calling the `push`
/// method, the customer's name will be inserted at the back of the queue -- his
/// laundry will be done after the laundry of customers previously on the queue.
/// The `expeditedPush` method is reserved for customers who have bribed the
/// merchant for expedited service.  When calling the `expeditedPush` method,
/// the customer's name will be inserted onto the front of the queue -- his
/// laundry will be done before customers previously on the queue.
///
/// When the workers are ready to do some laundry, they call the `next` method
/// of the queue, which returns the name of the customer whose laundry is to be
/// done next.  For brevity of the usage example, we do not show how customers
/// are track while or after their laundry is being done.
///
/// In addition, the laundry queue also provides the `find` method, which
/// returns a `bool` to indicate whether a given customer is still in the queue.
///
/// First, we declare a class `LaundryQueue` based on a deque, to store names of
/// customers at a drop-off laundry:
/// @code
/// // This `class` keeps track of customers enqueued to have their laundry
/// // done by a laundromat.
/// class LaundryQueue {
///
///     // DATA
///     bsl::deque<bsl::string> d_queue;
///
///   public:
///     // CREATORS
///
///     /// Create a `LaundryQueue` object using the specified
///     /// `basicAllocator`.  If `basicAllocator` is not provided, use the
///     /// default allocator.
///     LaundryQueue(bslma::Allocator *basicAllocator = 0);
///
///     // MANIPULATORS
///
///     /// Add the specified `customerName` to the back of the laundry
///     /// queue.
///     void push(const bsl::string& customerName);
///
///     /// Add the specified `customerName` to the laundry queue at the
///     /// front.
///     void expeditedPush(const bsl::string& customerName);
///
///     /// Return the name from the front of the queue, removing it from
///     /// the queue.  If the queue is empty, return `(* empty *)` which is
///     /// not a valid name for a customer.
///     bsl::string next();
///
///     // ACCESSORS
///
///     /// Return `true` if `customerName` is in the queue, and `false`
///     /// otherwise.
///     bool find(const bsl::string& customerName);
/// };
/// @endcode
/// Then, we define the implementation of the methods of `LaundryQueue`
/// @code
/// // CREATORS
/// LaundryQueue::LaundryQueue(bslma::Allocator *basicAllocator)
/// : d_queue(basicAllocator)
/// {
///     // Note that the allocator is propagated to the underlying `deque`,
///     // which will use the default allocator is `0 == basicAllocator`.
/// }
///
/// // MANIPULATORS
/// void LaundryQueue::push(const bsl::string& customerName)
/// {
///     d_queue.push_back(customerName);     // note constant time
/// }
///
/// void LaundryQueue::expeditedPush(const bsl::string& customerName)
/// {
///     d_queue.push_front(customerName);    // note constant time
/// }
///
/// bsl::string LaundryQueue::next()
/// {
///     if (d_queue.empty()) {
///         return "(* empty *)";
///     }
///
///     bsl::string ret = d_queue.front();   // note constant time
///
///     d_queue.pop_front();                 // note constant time
///
///     return ret;
/// }
///
/// // ACCESSORS
/// bool LaundryQueue::find(const bsl::string& customerName)
/// {
///     // Note `d_queue.empty() || d_queue[0] == d_queue.front()`
///
///     for (size_t i = 0; i < d_queue.size(); ++i) {
///         if (customerName == d_queue[i]) {    // note '[]' is constant time
///             return true;
///         }
///     }
///
///     return false;
/// }
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslstl
 * @{
 */
/** @addtogroup bslstl_deque
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslstl_algorithm.h>
#include <bslstl_iterator.h>
#include <bslstl_iteratorutil.h>
#include <bslstl_randomaccessiterator.h>
#include <bslstl_ranges.h>
#include <bslstl_stdexceptutil.h>
 
#include <bslalg_containerbase.h>
#include <bslalg_dequeimputil.h>
#include <bslalg_dequeiterator.h>
#include <bslalg_dequeprimitives.h>
#include <bslalg_rangecompare.h>
#include <bslalg_synththreewayutil.h>
#include <bslalg_typetraithasstliterators.h>
 
#include <bslma_allocatortraits.h>
#include <bslma_allocatorutil.h>
#include <bslma_destructionutil.h>
#include <bslma_isstdallocator.h>
#include <bslma_bslallocator.h>
#include <bslma_usesbslmaallocator.h>
 
#include <bslmf_assert.h>
#include <bslmf_containercompatiblerange.h>
#include <bslmf_isconvertible.h>
#include <bslmf_issame.h>
#include <bslmf_matchanytype.h>
#include <bslmf_matcharithmetictype.h>
#include <bslmf_movableref.h>
#include <bslmf_nil.h>
#include <bslmf_typeidentity.h>
#include <bslmf_util.h>    // 'forward(V)'
 
#include <bsls_assert.h>
#include <bsls_compilerfeatures.h>
#include <bsls_keyword.h>
#include <bsls_libraryfeatures.h>
#include <bsls_performancehint.h>
#include <bsls_util.h>     // 'forward<T>(V)'
 
#include <cstring>
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
#include <initializer_list>
#endif
 
#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
#include <bsls_nativestd.h>
#endif // BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
 
#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
 
#include <stdexcept>
#endif
 
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
# define BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(R, T) \
                  requires ::BloombergLP::bslmf::ContainerCompatibleRange<R, T>
#else
# define BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(R, T)
#endif
 
#if BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
// clang-format off
// Include version that can be compiled with C++03
// Generated on Mon Jan 13 08:31:39 2025
// Command line: sim_cpp11_features.pl bslstl_deque.h
 
# define COMPILING_BSLSTL_DEQUE_H
# include <bslstl_deque_cpp03.h>
# undef COMPILING_BSLSTL_DEQUE_H
 
// clang-format on
#else
 
namespace bsl {
 
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_BlockCreator;
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_BlockProctor;
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_ClearGuard;
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_Guard;
 
                       // ================================
                       // struct Deque_BlockLengthCalcUtil
                       // ================================
 
/// This `struct` provides a namespace for the calculation of block length
/// (the number of elements per block within a `deque`).  This ensures that
/// each block in the deque can hold at least 16 elements.
///
/// See @ref bslstl_deque 
template <class VALUE_TYPE>
struct Deque_BlockLengthCalcUtil {
 
    // TYPES
    enum {
        DEFAULT_BLOCK_SIZE = 200,  // number of bytes per block
 
        BLOCK_LENGTH       = (16 * sizeof(VALUE_TYPE) >= DEFAULT_BLOCK_SIZE)
                             ? 16
                             : (DEFAULT_BLOCK_SIZE / sizeof(VALUE_TYPE))
                                   // number of elements per block
    };
};
 
                          // =================
                          // struct Deque_Util
                          // =================
 
/// This `struct` provides a namespace to implement the `swap` member
/// function of `deque<VALUE_TYPE, ALLOCATOR>`.  This function can be
/// implemented irrespective of the `VALUE_TYPE` or `ALLOCATOR` template
/// parameters, which is why we implement it in this non-parameterized,
/// non-inlined utility.
///
/// See @ref bslstl_deque 
struct Deque_Util {
 
    // CLASS METHODS
 
    /// Assign the value of the specified `dst` deque to that of the
    /// specified `src` deque, and reset the `src` deque to a raw state.
    static void move(void *dst, void *src);
 
    /// Exchange the value of the specified `a` deque with that of the
    /// specified `b` deque.
    static void swap(void *a, void *b);
};
 
                        // ================
                        // class Deque_Base
                        // ================
 
/// This class describes the basic layout for a deque class.  It is
/// important that this class has the same layout as the deque class
/// implementation.  It is parameterized by `VALUE_TYPE` only and implements
/// the portion of `bsl::deque` that does not need to know about its
/// (template parameter) type `ALLOCATOR` (in order to generate shorter debug strings).  
/// 
/// \note Note that   this class must have the same layout as
/// `Deque_Imp` (see implementation file).
///
/// See @ref bslstl_deque 
template <class VALUE_TYPE>
class Deque_Base {
 
    // PRIVATE TYPES
    enum {
        BLOCK_LENGTH = Deque_BlockLengthCalcUtil<VALUE_TYPE>::BLOCK_LENGTH
    };
 
    typedef BloombergLP::bslalg::DequeImpUtil<VALUE_TYPE,
                                              BLOCK_LENGTH>    Imp;
    typedef typename Imp::Block                                Block;
    typedef typename Imp::BlockPtr                             BlockPtr;
    typedef BloombergLP::bslalg::DequeIterator<VALUE_TYPE,
                                               BLOCK_LENGTH>   IteratorImp;
    typedef BloombergLP::
            bslstl::RandomAccessIterator<VALUE_TYPE, IteratorImp>
                                                               Iterator;
 
    typedef BloombergLP::
            bslstl::RandomAccessIterator<const VALUE_TYPE, IteratorImp>
                                                               ConstIterator;
 
  public:
    // PUBLIC TYPES
    typedef VALUE_TYPE&                             reference;
    typedef const VALUE_TYPE&                       const_reference;
    typedef Iterator                                iterator;
    typedef ConstIterator                           const_iterator;
    typedef std::size_t                             size_type;
    typedef std::ptrdiff_t                          difference_type;
    typedef VALUE_TYPE                              value_type;
 
    // For consistent behavior on all compilers, we must 'bsl::'-qualify
    // @ref reverse_iterator .  (For most compilers, @ref reverse_iterator  is in
    // namespace 'std', and NOT in namespace 'bsl'.  Hence, we need to
    // actively look into a different namespace to find the iterator.  However,
    // on Solaris we explicitly provide a @ref reverse_iterator  implementation, IN
    // namespace 'bsl', to replace their broken one.  See 'bslstl_iterator.h'.)
 
    typedef bsl::reverse_iterator<Iterator>         reverse_iterator;
    typedef bsl::reverse_iterator<ConstIterator>    const_reverse_iterator;
 
  protected:
    // PROTECTED DATA
    BlockPtr    *d_blocks_p;      // array of pointer to blocks (owned)
    std::size_t  d_blocksLength;  // length of 'd_blocks_p' array
    IteratorImp  d_start;         // iterator to first element
    IteratorImp  d_finish;        // iterator to one past last element
 
  public:
    // MANIPULATORS
 
    // *** iterators ***
 
    /// Return an iterator providing modifiable access to the first element
    /// in this deque, and the past-the-end iterator if this deque is empty.
    iterator begin() BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end (forward) iterator providing modifiable
    /// access to this deque.
    iterator end() BSLS_KEYWORD_NOEXCEPT;
 
    /// Return a reverse iterator providing modifiable access to the last
    /// element in this deque, and the past-the-end reverse iterator if this
    /// deque is empty.
    reverse_iterator rbegin() BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end reverse iterator providing modifiable access
    /// to this deque.
    reverse_iterator rend() BSLS_KEYWORD_NOEXCEPT;
 
    // *** element access ***
 
    /// Return a reference providing modifiable access to the element at the
    /// specified `position` in this deque.  
    /// 
    /// \pre The behavior is undefined   unless `position < size()`.
    reference operator[](size_type position);
 
    /// Return a reference providing modifiable access to the element at the
    /// specified `position` in this deque.  Throw a `std::out_of_range`
    /// exception if `position >= size()`.
    reference at(size_type position);
 
    /// Return a reference providing modifiable access to the first element in this deque.  
    /// 
    /// \pre The behavior is undefined   unless this deque is not
    /// empty.
    reference front();
 
    /// Return a reference providing modifiable access to the last element in this deque.  
    /// 
    /// \pre The behavior is undefined   unless this deque is not
    /// empty.
    reference back();
 
    // ACCESSORS
 
    // *** iterators ***
 
    const_iterator  begin() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return an iterator providing non-modifiable access to the first
    /// element in this deque, and the past-the-end iterator if this deque
    /// is empty.
    const_iterator cbegin() const BSLS_KEYWORD_NOEXCEPT;
 
    const_iterator  end() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end (forward) iterator providing non-modifiable
    /// access to this deque.
    const_iterator cend() const BSLS_KEYWORD_NOEXCEPT;
 
    const_reverse_iterator  rbegin() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return a reverse iterator providing non-modifiable access to the
    /// last element in this deque, and the past-the-end reverse iterator if
    /// this deque is empty.
    const_reverse_iterator crbegin() const BSLS_KEYWORD_NOEXCEPT;
 
    const_reverse_iterator rend() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end reverse iterator providing non-modifiable
    /// access to this deque.
    const_reverse_iterator crend() const BSLS_KEYWORD_NOEXCEPT;
 
    // *** capacity ***
 
    /// Return the number of elements contained by this deque.
    size_type size() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the sum of the current size of this deque plus the minimum
    /// number of `push_front` or `push_back` operations needed to invalidate iterators in this deque.  
    /// 
    /// \note Note that   this method is not
    /// part of the C++ standard.
    size_type capacity() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return `true` if this deque contains no elements, and `false`
    /// otherwise.
    bool empty() const BSLS_KEYWORD_NOEXCEPT;
 
    // *** element access ***
 
    /// Return a reference providing non-modifiable access to the element at
    /// the specified `position` in this deque.  
    /// 
    /// \pre The behavior is undefined   unless `position < size()`.
    const_reference operator[](size_type position) const;
 
    /// Return a reference providing non-modifiable access to the element at
    /// the specified `position` in this deque.  Throw a `std::out_of_range`
    /// exception if `position >= size()`.
    const_reference at(size_type position) const;
 
    /// Return a reference providing non-modifiable access to the first element in this deque.  
    /// 
    /// \pre The behavior is undefined   unless this deque
    /// is not empty.
    const_reference front() const;
 
    /// Return a reference providing non-modifiable access to the last element in this deque.  
    /// 
    /// \pre The behavior is undefined   unless this deque
    /// is not empty.
    const_reference back() const;
};
 
                        // ===========
                        // class deque
                        // ===========
 
/// This class template provides an STL-compliant `deque` that conforms to
/// the `bslma::Allocator` model.  For the requirements of a deque class,
/// consult the C++11 standard.  In particular, this implementation offers
/// the general rules that:
/// 1. A call to any method that would result in a deque having a size
///    greater than the value returned by @ref max_size  triggers a call to
///    `bslstl::StdExceptUtil::throwLengthError`.
/// 2. A call to an `at` method that attempts to access a position
///    outside of the valid range of a deque triggers a call to
///    `bslstl::StdExceptUtil::throwOutOfRange`.
///
/// 
/// \note Note that  portions of the standard methods are implemented in
/// `Deque_Base`, which is parameterized on only `VALUE_TYPE` in order to
/// generate smaller debug strings.
///
/// This class:
/// * supports a complete set of *value-semantic* operations
///   - except for `BDEX` serialization
/// * is *exception-neutral*
/// * is *alias-safe*
/// * is `const` *thread-safe*
/// For terminology see @ref bsldoc_glossary .
///
/// In addition, the following members offer a full guarantee of rollback:
/// if an exception is thrown during the invocation of `insert`,
/// `push_front`, or `push_back` on a pre-existing object, the object is
/// left in a valid state and its value is unchanged.
template <class VALUE_TYPE, class ALLOCATOR = allocator<VALUE_TYPE> >
class deque : public  Deque_Base<VALUE_TYPE>
            , private BloombergLP::bslalg::ContainerBase<ALLOCATOR> {
 
    // PRIVATE TYPES
    enum {
        BLOCK_LENGTH = Deque_BlockLengthCalcUtil<VALUE_TYPE>::BLOCK_LENGTH
    };
 
    typedef Deque_Base<VALUE_TYPE>                             Base;
 
    typedef BloombergLP::bslalg::ContainerBase<ALLOCATOR>      ContainerBase;
 
    typedef BloombergLP::bslalg::DequeImpUtil<VALUE_TYPE,
                                             BLOCK_LENGTH>     Imp;
    typedef typename Imp::Block                                Block;
    typedef typename Imp::BlockPtr                             BlockPtr;
 
    typedef BloombergLP::bslalg::DequeIterator<VALUE_TYPE,
                                              BLOCK_LENGTH>    IteratorImp;
 
    typedef BloombergLP::
            bslstl::RandomAccessIterator<VALUE_TYPE,
                                        IteratorImp>           Iterator;
 
    typedef BloombergLP::
            bslstl::RandomAccessIterator<const VALUE_TYPE,
                                        IteratorImp>           ConstIterator;
 
    typedef Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>          BlockCreator;
    typedef Deque_BlockProctor<VALUE_TYPE, ALLOCATOR>          BlockProctor;
    typedef Deque_ClearGuard<VALUE_TYPE, ALLOCATOR>            ClearGuard;
    typedef Deque_Guard<VALUE_TYPE, ALLOCATOR>                 Guard;
 
    typedef BloombergLP::bslalg::DequePrimitives<VALUE_TYPE,
                                                BLOCK_LENGTH>  DequePrimitives;
 
    typedef BloombergLP::bslma::AllocatorUtil                  AllocatorUtil;
    typedef bsl::allocator_traits<ALLOCATOR>                   AllocatorTraits;
 
    /// This typedef is a convenient alias for the utility associated with
    /// movable references.
    typedef BloombergLP::bslmf::MovableRefUtil                 MoveUtil;
 
    /// Special type (and value) used to create a "raw" deque, which has a
    /// block length of 0, and null start and finish pointers.
    enum RawInit { k_RAW_INIT = 0 };
 
  public:
    // PUBLIC TYPES
    typedef VALUE_TYPE&                             reference;
    typedef const VALUE_TYPE&                       const_reference;
    typedef Iterator                                iterator;
    typedef ConstIterator                           const_iterator;
    typedef std::size_t                             size_type;
    typedef std::ptrdiff_t                          difference_type;
    typedef VALUE_TYPE                              value_type;
 
    typedef ALLOCATOR                               allocator_type;
    typedef typename AllocatorTraits::pointer       pointer;
    typedef typename AllocatorTraits::const_pointer const_pointer;
 
    // As above, we must 'bsl::'-qualify @ref reverse_iterator .
 
    typedef bsl::reverse_iterator<Iterator>         reverse_iterator;
    typedef bsl::reverse_iterator<ConstIterator>    const_reverse_iterator;
 
  private:
    // STATIC ASSERTIONS
 
    BSLMF_ASSERT((is_same<reference, typename Base::reference>::value));
    BSLMF_ASSERT((is_same<const_reference,
                  typename Base::const_reference>::value));
        // These need not necessarily be true as per the C++ standard, but are
        // safe assumptions for this implementation and allow us to implement
        // the element access within the 'Base' type (that is parameterized by
        // 'VALUE_TYPE' only).
 
    // PRIVATE CREATORS
 
    /// Create a "raw" deque (i.e., a deque that obeys the raw deque
    /// invariants and is destructible) that uses the specified `allocator`
    /// to supply memory.  The following holds for a raw deque:
    /// `0 == d_blocks_p`, `0 == d_blocksLength`, and `d_start` and
    /// `d_finish` are singular iterators (i.e., have null internal pointers).  
    /// 
    /// \note Note that   the constructed deque contains no allocated
    /// storage.  Also note that the purpose of a raw deque is to provide an
    /// exception-safe repository for intermediate calculations.
    deque(RawInit, const allocator_type& allocator);
 
    // PRIVATE MANIPULATORS
 
    /// Return one block allocated from this object's allocator.  
    /// 
    /// \note Note that   the block is not initialized.
    Block *allocateBlock();
 
    /// Allocate an array having the specified `n` elements of type `BlockPtr` from this object's allocator.  
    /// 
    /// \note Note that   the array
    /// elements are not initialized.
    BlockPtr *allocateBlockPtrs(std::size_t n);
 
    /// Deallocate from this object's allocator the block at the specified `p` address.  
    /// 
    /// \note Note that   this function does not call any destructors
    /// on `p` or `*p`.
    void deallocateBlock(Block *p);
 
    /// Deallocate from this object's allocator an array at the specified
    /// `p` address having the specified `n` elements of type `BlockPtr`. 
    /// 
    /// \note Note that   if any of the array elements point to an allocated block,
    /// then that block is not deallocated (and might be leaked).
    void deallocateBlockPtrs(BlockPtr *p, std::size_t n);
 
    /// Append the elements in the range specified by `[first .. last)` to
    /// this deque, and return the number of elements appended.  
    /// 
    /// \pre The behavior is undefined   unless `first` and `last` refer to a sequence of valid
    /// values where `first` is at a position at or before `last`.
    template <class INPUT_ITERATOR, class SENTINEL>
    size_type privateAppend(INPUT_ITERATOR first, SENTINEL last);
 
    /// Append the elements in the range specified by `[first .. last)` to
    /// this deque, and return the number of elements appended.  The third
    /// argument is used for overload resolution.  
    /// 
    /// \pre The behavior is undefined   unless `first` and `last` refer to a sequence of valid values where
    /// `first` is at a position at or before `last`.
    template <class INPUT_ITERATOR, class SENTINEL>
    size_type privateAppend(INPUT_ITERATOR                  first,
                            SENTINEL                        last,
                            std::input_iterator_tag);
    template <class INPUT_ITERATOR, class SENTINEL>
    size_type privateAppend(INPUT_ITERATOR                  first,
                            SENTINEL                        last,
                            std::random_access_iterator_tag);
 
    /// Append the specified `numElements` value-inititalized objects to
    /// this deque.
    void privateAppendDefaultInsertable(size_type numElements);
 
    /// Append the specified `numElements` copies of the specified `value`
    /// to this deque.
    void privateAppendRaw(size_type numElements, const VALUE_TYPE& value);
 
    /// Assign the elements in the range specified by `[first .. last)` to this
    /// deque.
    template <class t_ITERATOR, class t_SENTINEL>
    void privateAssign(t_ITERATOR first, t_SENTINEL last);
 
    /// Initialize `d_start` and `d_finish` for eventual insertion of the
    /// specified `numElements` elements.  After this method returns, this
    /// object is fully constructed with memory allocated for `numElements`,
    /// with all member variables obeying the class invariants, and with size 0.  
    /// 
    /// \pre The behavior is undefined   unless this object is in a "raw" state.  
    /// 
    /// \note Note that   this method must not be called while constructing
    /// this object (although a constructor may call it for a temporary
    /// object).
    void privateInit(size_type numElements);
 
    /// Insert the specified `numElements` copies of the specified `value`
    /// into this deque at the specified `position`.  This overload matches
    /// `privateInsert` when the second and third arguments are of the same
    /// type which happens to be an integral type.  The fourth and fifth
    /// arguments are used for overload resolution only.
    template <class INTEGER_TYPE>
    void privateInsertDispatch(
                           const_iterator                          position,
                           INTEGER_TYPE                            numElements,
                           INTEGER_TYPE                            value,
                           BloombergLP::bslmf::MatchArithmeticType,
                           BloombergLP::bslmf::Nil);
 
    /// Insert the elements in the range specified by `[first .. last)` into
    /// this deque at the specified `position`.  The third and fourth
    /// arguments are used for overload resolution only, so that this
    /// function is not called if `first` and `last` are of integral type. 
    /// 
    /// \pre The behavior is undefined   unless `first` and `last` refer to a
    /// sequence of valid values where `first` is at a position at or before
    /// `last`.
    template <class INPUT_ITERATOR>
    void privateInsertDispatch(const_iterator                   position,
                               INPUT_ITERATOR                   first,
                               INPUT_ITERATOR                   last,
                               BloombergLP::bslmf::MatchAnyType,
                               BloombergLP::bslmf::MatchAnyType);
 
    /// Insert the elements in the range specified by `[first .. last)` into
    /// this deque at the specified `position`.
    template <class INPUT_ITERATOR, class SENTINEL>
    void privateInsert(const_iterator position,
                       INPUT_ITERATOR first,
                       SENTINEL       last);
 
    /// Specialized insertion for input iterators.
    template <class INPUT_ITERATOR, class SENTINEL>
    void privateInsert(const_iterator                  position,
                       INPUT_ITERATOR                  first,
                       SENTINEL                        last,
                       std::input_iterator_tag);
 
    /// Specialized insertion for forward, bidirectional, and random-access
    /// iterators.
    template <class INPUT_ITERATOR, class SENTINEL>
    void privateInsert(const_iterator                  position,
                       INPUT_ITERATOR                  first,
                       SENTINEL                        last,
                       std::random_access_iterator_tag);
 
    /// Join `*this` and the specified `other` deque into one.  After the
    /// join, `*this` contains the concatenated sequence, in order, of
    /// `*other` and `*this` elements, and 'other is made a raw deque.
    void privateJoinPrepend(deque *other);
 
    /// Join `*this` and the specified `other` deque into one.  After the
    /// join, `*this` contains the concatenated sequence, in order, of
    /// `*this` and `*other` elements, and 'other is made a raw deque.
    void privateJoinAppend(deque *other);
 
    /// Prepend the elements in the range specified by `[first .. last)` to
    /// this deque, and return the number of elements prepended.  
    /// 
    /// \pre The behavior is undefined   unless `first` and `last` refer to a sequence of valid
    /// values where `first` is at a position at or before `last`.
    template <class INPUT_ITERATOR, class SENTINEL>
    size_type privatePrepend(INPUT_ITERATOR first, SENTINEL last);
 
    /// Prepend the elements in the range specified by `[first .. last)` to
    /// this deque, and return the number of elements prepended.  The third
    /// argument is used for overload resolution only.  
    /// 
    /// \pre The behavior is undefined   unless `first` and `last` refer to a sequence of valid
    /// values where `first` is at a position at or before `last`.
    template <class INPUT_ITERATOR, class SENTINEL>
    size_type privatePrepend(INPUT_ITERATOR                  first,
                             SENTINEL                        last,
                             std::input_iterator_tag);
    template <class INPUT_ITERATOR, class SENTINEL>
    size_type privatePrepend(INPUT_ITERATOR                  first,
                             SENTINEL                        last,
                             std::bidirectional_iterator_tag);
    template <class INPUT_ITERATOR, class SENTINEL>
    size_type privatePrepend(INPUT_ITERATOR                  first,
                             SENTINEL                        last,
                             std::random_access_iterator_tag);
 
    /// Prepend the specified `numElements` copies of the specified `value`
    /// to this deque.
    void privatePrependRaw(size_type numElements, const VALUE_TYPE& value);
 
    /// Split this deque in two such that after the split, `*this` contains
    /// elements formerly in the range specified by `[d_start .. pos)` and
    /// the specified `other` deque contains elements formerly in the range `[pos .. d_finish)`.  
    /// 
    /// \pre The behavior is undefined   unless `other` is a
    /// raw deque, i.e., the `RawInit` constructor was used to create
    /// `other`.
    void privateSplit(deque *other, IteratorImp pos);
 
    // FRIENDS
    template <class VALUE_TYPE2, class ALLOCATOR2>
    friend class Deque_BlockCreator;
 
    template <class VALUE_TYPE2, class ALLOCATOR2>
    friend class Deque_BlockProctor;
 
    template <class VALUE_TYPE2, class ALLOCATOR2>
    friend class Deque_Guard;
 
  public:
    // CREATORS
 
    // *** construct/copy/destroy ***
 
    /// Create an empty deque.  Optionally specify a `basicAllocator` used
    /// to supply memory.  If `basicAllocator` is not supplied, a
    /// default-constructed object of the (template parameter) type
    /// `ALLOCATOR` is used.  If the type `ALLOCATOR` is `bsl::allocator`
    /// (the default), then `basicAllocator`, if supplied, shall be
    /// convertible to `bslma::Allocator *`.  If the type `ALLOCATOR` is
    /// `bsl::allocator` and `basicAllocator` is not supplied, the currently
    /// installed default allocator is used.
    deque();
    explicit deque(const ALLOCATOR& basicAllocator);
 
    /// Create a deque of the specified `numElements` size whose every
    /// element is value-initialized.  Optionally specify a `basicAllocator`
    /// used to supply memory.  If `basicAllocator` is not supplied, a
    /// default-constructed object of the (template parameter) type
    /// `ALLOCATOR` is used.  If the type `ALLOCATOR` is `bsl::allocator`
    /// (the default), then `basicAllocator`, if supplied, shall be
    /// convertible to `bslma::Allocator *`.  If the type `ALLOCATOR` is
    /// `bsl::allocator` and `basicAllocator` is not supplied, the currently
    /// installed default allocator is used.  Throw `bsl::length_error` if
    /// `numElements > max_size()`.  This method requires that the (template
    /// parameter) `VALUE_TYPE` be `default-insertable` into this deque (see
    /// {Requirements on `VALUE_TYPE`}).
    explicit
    deque(size_type        numElements,
          const ALLOCATOR& basicAllocator = ALLOCATOR());
 
    /// Create a deque of the specified `numElements` size whose every
    /// element has the specified `value`.  Optionally specify a
    /// `basicAllocator` used to supply memory.  If `basicAllocator` is not
    /// supplied, a default-constructed object of the (template parameter)
    /// type `ALLOCATOR` is used.  If the type `ALLOCATOR` is
    /// `bsl::allocator` (the default), then `basicAllocator`, if supplied,
    /// shall be convertible to `bslma::Allocator *`.  If the type
    /// `ALLOCATOR` is `bsl::allocator` and `basicAllocator` is not
    /// supplied, the currently installed default allocator is used.  Throw
    /// `bsl::length_error` if `numElements > max_size()`.  This method
    /// requires that the (template parameter) `VALUE_TYPE` be
    /// `copy-insertable` into this deque (see {Requirements on
    /// `VALUE_TYPE`}).
    deque(size_type         numElements,
          const VALUE_TYPE& value,
          const ALLOCATOR&  basicAllocator = ALLOCATOR());
 
    /// Create a deque initially containing copies of the values in the
    /// range starting at the specified `first` and ending immediately
    /// before the specified `last` iterators of the (template parameter)
    /// type `INPUT_ITERATOR`.  Optionally specify a `basicAllocator` used
    /// to supply memory.  If `basicAllocator` is not supplied, a
    /// default-constructed object of the (template parameter) type
    /// `ALLOCATOR` is used.  If the type `ALLOCATOR` is `bsl::allocator`
    /// (the default), then `basicAllocator`, if supplied, shall be
    /// convertible to `bslma::Allocator *`.  If the type `ALLOCATOR` is
    /// `bsl::allocator` and `basicAllocator` is not supplied, the currently
    /// installed default allocator is used.  Throw `bsl::length_error` if
    /// the number of elements in `[first .. last)` exceeds the size
    /// returned by @ref max_size .  The (template parameter) type
    /// `INPUT_ITERATOR` shall meet the requirements of an input iterator
    /// defined in the C++11 standard [input.iterators] providing access to
    /// values of a type convertible to `value_type`, and `value_type` must
    /// be `emplace-constructible` from `*i` into this deque, where `i` is a
    /// dereferenceable iterator in the range `[first .. last)` (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless
    /// `first` and `last` refer to a sequence of valid values where `first`
    /// is at a position at or before `last`.
    template <class INPUT_ITERATOR>
    deque(INPUT_ITERATOR   first,
          INPUT_ITERATOR   last,
          const ALLOCATOR& basicAllocator = ALLOCATOR());
 
    /// Create a deque from the elements of the specifed `range`.  Optionally
    /// specify an `basicAllocator` used to supply memory.  If `basicAllocator`
    /// is not specified, a default-constructed object of the (template parameter) type `ALLOCATOR` is used.  
    /// 
    /// \note Note that   `range` must meet the
    /// requirements of an input range and the values from `range` must have a
    /// type matching or convertible to (template parameter) `VALUE_TYPE`.
    template <class t_RANGE>
    BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
    deque(from_range_t                               ,
          BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range,
          const ALLOCATOR&                           basicAllocator =
                                                                  ALLOCATOR());
 
    /// Create a deque that has the same value as the specified `original`
    /// object.  Use the allocator returned by
    /// 'bsl::allocator_traits<ALLOCATOR>::
    /// select_on_container_copy_construction(original.get_allocator())' to
    /// supply memory.  If the (template parameter) type `ALLOCATOR` is
    /// `bsl::allocator` (the default), the currently installed default
    /// allocator is used.  This method requires that the (template
    /// parameter) `VALUE_TYPE` be `copy-insertable` into this deque (see
    /// {Requirements on `VALUE_TYPE`}).
    deque(const deque& original);
 
    /// Create a deque that has the same value as the specified `original`
    /// object and that uses the specified `basicAllocator` to supply
    /// memory.  This method requires that the (template parameter)
    /// `VALUE_TYPE` be `copy-insertable` into this deque (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \note Note that   a `bslma::Allocator *`
    /// can be supplied for `basicAllocator` if the (template parameter)
    /// type `ALLOCATOR` is `bsl::allocator` (the default).
    deque(const deque&                                   original,
          const typename type_identity<ALLOCATOR>::type& basicAllocator);
 
    /// Create a deque having the same value as the specified `original`
    /// object by moving (in constant time) the contents of `original` to
    /// the new deque.  The allocator associated with `original` is
    /// propagated for use in the newly-created deque.  `original` is left
    /// in a valid but unspecified state.
    deque(BloombergLP::bslmf::MovableRef<deque> original);          // IMPLICIT
 
    /// Create a deque having the same value as the specified `original`
    /// object that uses the specified `basicAllocator` to supply memory.
    /// The contents of `original` are moved (in constant time) to the new
    /// deque if `basicAllocator == original.get_allocator()`, and are move-
    /// inserted (in linear time) using `basicAllocator` otherwise.
    /// `original` is left in a valid but unspecified state.  This method
    /// requires that the (template parameter) `VALUE_TYPE` be
    /// `move-insertable` into this deque (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \note Note that   a `bslma::Allocator *` can be supplied
    /// for `basicAllocator` if the (template parameter) `ALLOCATOR` is
    /// `bsl::allocator` (the default).
    deque(BloombergLP::bslmf::MovableRef<deque>          original,
          const typename type_identity<ALLOCATOR>::type& basicAllocator);
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    /// Create a deque and append each `value_type` object in the specified
    /// `values` initializer list.  Optionally specify a `basicAllocator`
    /// used to supply memory.  If `basicAllocator` is not supplied, a
    /// default-constructed object of the (template parameter) type
    /// `ALLOCATOR` is used.  If the type `ALLOCATOR` is `bsl::allocator`
    /// (the default), then `basicAllocator`, if supplied, shall be
    /// convertible to `bslma::Allocator *`.  If the type `ALLOCATOR` is
    /// `bsl::allocator` and `basicAllocator` is not supplied, the currently
    /// installed default allocator is used.  This method requires that the
    /// (template parameter) `VALUE_TYPE` be `copy-insertable` into this
    /// deque (see {Requirements on `VALUE_TYPE`}).
    deque(std::initializer_list<value_type> values,
          const ALLOCATOR&                  basicAllocator = ALLOCATOR());
#endif
 
    /// Destroy this object.
    ~deque();
 
    // MANIPULATORS
 
    /// Assign to this object the value of the specified `rhs` object,
    /// propagate to this object the allocator of `rhs` if the `ALLOCATOR`
    /// type has trait @ref propagate_on_container_copy_assignment , and return
    /// a reference providing modifiable access to this object.  If an
    /// exception is thrown, `*this` is left in a valid but unspecified
    /// state.  This method requires that the (template parameter)
    /// `VALUE_TYPE` be `copy-assignable` and `copy-insertable` into this
    /// deque (see {Requirements on `VALUE_TYPE`}).
    deque& operator=(const deque& rhs);
 
    /// Assign to this object the value of the specified `rhs` object,
    /// propagate to this object the allocator of `rhs` if the `ALLOCATOR`
    /// type has trait @ref propagate_on_container_move_assignment , and return
    /// a reference providing modifiable access to this object.  The
    /// contents of `rhs` are moved (in constant time) to this deque if
    /// `get_allocator() == rhs.get_allocator()` (after accounting for the
    /// aforementioned trait); otherwise, all elements in this deque are
    /// either destroyed or move-assigned to and each additional element in
    /// `rhs` is move-inserted into this deque.  `rhs` is left in a valid
    /// but unspecified state, and if an exception is thrown, `*this` is
    /// left in a valid but unspecified state.  This method requires that
    /// the (template parameter) `VALUE_TYPE` be `move-assignable` and
    /// `move-insertable` into this deque (see {Requirements on
    /// `VALUE_TYPE`}).
    deque& operator=(BloombergLP::bslmf::MovableRef<deque> rhs)
        BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
                                      AllocatorTraits::is_always_equal::value);
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    /// Assign to this object the value resulting from first clearing this
    /// deque and then appending each `value_type` object in the specified
    /// `values` initializer list; return a reference providing modifiable
    /// access to this object.  This method requires that the (template
    /// parameter) `VALUE_TYPE` be `copy-insertable` into this deque (see
    /// {Requirements on `VALUE_TYPE`}).
    deque& operator=(std::initializer_list<value_type> values);
#endif
 
    /// Assign to this deque the values in the range starting at the
    /// specified `first` and ending immediately before the specified `last`
    /// iterators of the (template parameter) type `INPUT_ITERATOR`.  The
    /// (template parameter) type `INPUT_ITERATOR` shall meet the
    /// requirements of an input iterator defined in the C++11 standard
    /// [input.iterators] providing access to values of a type convertible
    /// to `value_type`, and `value_type` must be `copy-assignable` and
    /// `emplace-constructible` from `*i` into this deque, where `i` is a
    /// dereferenceable iterator in the range `[first .. last)` (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless
    /// `first` and `last` refer to a sequence of valid values where `first`
    /// is at a position at or before `last`.
    template <class INPUT_ITERATOR>
    void assign(INPUT_ITERATOR first, INPUT_ITERATOR last);
 
    /// Assign to this object the value resulting from first clearing this
    /// deque and then appending the specified `numElements` having the
    /// specified `value`.  This method requires that the (template
    /// parameter) `VALUE_TYPE` be `copy-assignable` and `copy-insertable`
    /// into this deque (see {Requirements on `VALUE_TYPE`}).
    void assign(size_type numElements, const VALUE_TYPE& value);
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    /// Assign to this object the value resulting from first clearing this
    /// deque and then appending each `value_type` object in the specified
    /// `values` initializer list.  This method requires that the (template
    /// parameter) `VALUE_TYPE` be `copy-assignable` and `copy-insertable`
    /// into this deque (see {Requirements on `VALUE_TYPE`}).
    void assign(std::initializer_list<value_type> values);
#endif
 
    /// Assign to this object the elements of the specified `range`.  
    /// 
    /// \note Note that   `range` must meet the requirements of an input range and the values
    /// from `range` must have a type matching or convertible to (template
    /// parameter) `VALUE_TYPE`.
    template <class t_RANGE>
    BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
    void assign_range(BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range);
 
    // *** capacity ***
 
    /// Change the capacity of this deque such that, after this method
    /// returns, iterators remain valid provided that no more than the
    /// specified `numElements` objects are pushed to the front or back of
    /// the deque after this call.  If it is already possible to push
    /// `numElements` objects to either end of this deque without
    /// invalidating iterators, this method has no effect.  
    /// 
    /// \note Note that   inserting elements into the deque may still incur memory allocation.
    /// Also note that this method, if it has any effect, will invalidate
    /// iterators initialized prior to the call.  Also note that this method
    /// is not part of the C++ standard.
    void reserve(size_type numElements);
 
    /// Change the size of this deque to the specified `newSize`.  Erase
    /// `size() - newSize` elements at the back if `newSize < size()`.
    /// Append `newSize - size()` elements at the back having the optionally
    /// specified `value` if `newSize > size()`; if `value` is not
    /// specified, value-initialized objects of the (template parameter)
    /// `VALUE_TYPE` are emplaced.  This method has no effect if
    /// `newSize == size()`.  Throw `bsl::length_error` if
    /// `newSize > max_size()`.
    void resize(size_type newSize);
    void resize(size_type newSize, const VALUE_TYPE& value);
 
    /// Minimize the memory used by this deque to the extent possible
    /// without moving any contained elements.  If an exception is thrown, the value of this object is unchanged.  
    /// 
    /// \note Note that   this method has no
    /// effect on the memory used by individual elements of the (template
    /// parameter) `VALUE_TYPE`.
    void shrink_to_fit();
 
    // *** modifiers ***
 
    /// Append to the end of this object the elements of the specified `range`. 
    /// 
    /// \note Note that   `range` must meet the requirements of an input range and the
    /// values from `range` must have a type matching or convertible to
    /// (template parameter) `VALUE_TYPE`.
    template <class t_RANGE>
    BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
    void append_range(BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range);
 
    /// Prepend to the front of this object the elements of the specified `range`.  
    /// 
    /// \note Note that   `range` must meet the requirements of an input
    /// range and the values from `range` must have a type matching or
    /// convertible to (template parameter) `VALUE_TYPE`.
    template <class t_RANGE>
    BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
    void prepend_range(BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range);
 
    /// Prepend to the front of this deque a copy of the specified `value`.
    /// This method offers full guarantee of rollback in case an exception
    /// is thrown.  This method requires that the (template parameter)
    /// `VALUE_TYPE` be `copy-constructible` (see {Requirements on
    /// `VALUE_TYPE`}).
    void push_front(const VALUE_TYPE& value);
 
    /// Prepend to the front of this deque the specified move-insertable
    /// `value`.  `value` is left in a valid but unspecified state.  If an
    /// exception is thrown (other than by the move constructor of a
    /// non-copy-insertable `value_type`), this method has no effect.  This
    /// method requires that the (template parameter) `VALUE_TYPE` be
    /// `move-insertable` into this deque (see {Requirements on
    /// `VALUE_TYPE`}).
    void push_front(BloombergLP::bslmf::MovableRef<value_type> value);
 
    /// Append to the back of this deque a copy of the specified `value`.
    /// This method offers full guarantee of rollback in case an exception
    /// is thrown.  This method requires that the (template parameter)
    /// `VALUE_TYPE` be `copy-constructible` (see {Requirements on
    /// `VALUE_TYPE`}).
    void push_back(const VALUE_TYPE& value);
 
    /// Append to the back of this deque the specified move-insertable
    /// `value`.  `value` is left in a valid but unspecified state.  If an
    /// exception is thrown (other than by the move constructor of a
    /// non-copy-insertable `value_type`), this method has no effect.  This
    /// method requires that the (template parameter) `VALUE_TYPE` be
    /// `move-insertable` into this deque (see {Requirements on
    /// `VALUE_TYPE`}).
    void push_back(BloombergLP::bslmf::MovableRef<value_type> value);
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// Prepend to the front of this deque a newly created `value_type`
    /// object, constructed by forwarding `get_allocator()` (if required)
    /// and the specified (variable number of) `arguments` to the
    /// corresponding constructor of `value_type`.  Return a reference
    /// providing modifiable access to the inserted element.  If an
    /// exception is thrown (other than by the move constructor of a
    /// non-copy-insertable `value_type`), this method has no effect.  This
    /// method requires that the (template parameter) `VALUE_TYPE` be
    /// `move-insertable` into this deque and `emplace-constructible` from
    /// `arguments` (see
    /// {Requirements on `VALUE_TYPE`}).
    template <class... Args>
    reference emplace_front(Args&&... arguments);
 
    /// Append to the back of this deque a newly created `value_type`
    /// object, constructed by forwarding `get_allocator()` (if required)
    /// and the specified (variable number of) `arguments` to the
    /// corresponding constructor of `value_type`.  Return a reference
    /// providing modifiable access to the inserted element.  If an
    /// exception is thrown (other than by the move constructor of a
    /// non-copy-insertable `value_type`), this method has no effect.  This
    /// method requires that the (template parameter) `VALUE_TYPE` be
    /// `move-insertable` into this deque and `emplace-constructible` from
    /// `arguments` (see
    /// {Requirements on `VALUE_TYPE`}).
    template <class... Args>
    reference emplace_back(Args&&... arguments);
#endif
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// Insert at the specified `position` in this deque a newly created
    /// `value_type` object, constructed by forwarding `get_allocator()` (if
    /// required) and the specified (variable number of) `arguments` to the
    /// corresponding constructor of `value_type`, and return an iterator
    /// providing modifiable access to the newly created and inserted
    /// element.  If an exception is thrown (other than by the copy
    /// constructor, move constructor, assignment operator, or move
    /// assignment operator of `value_type`), this method has no effect.
    /// This method requires that the (template parameter) `VALUE_TYPE` be
    /// `move-insertable` into this deque and `emplace-constructible` from
    /// `arguments` (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless `position` is an iterator in the range
    /// `[cbegin() .. cend()]` (both endpoints included).
    template <class... Args>
    iterator emplace(const_iterator position, Args&&... arguments);
#endif
 
    /// Erase the first element from this deque.  
    /// 
    /// \pre The behavior is undefined   if this deque is empty.
    void pop_front();
 
    /// Erase the last element from this deque.  
    /// 
    /// \pre The behavior is undefined   if this deque is empty.
    void pop_back();
 
    /// Insert at the specified `position` in this deque a copy of the
    /// specified `value`, and return an iterator providing modifiable
    /// access to the newly inserted element.  This method offers full
    /// guarantee of rollback in case an exception is thrown other than by
    /// the `VALUE_TYPE` copy constructor or assignment operator.  This
    /// method requires that the (template parameter) `VALUE_TYPE` be
    /// `copy-insertable` into this deque (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless `position` is an
    /// iterator in the range `[cbegin() .. cend()]` (both endpoints
    /// included).
    iterator insert(const_iterator position, const VALUE_TYPE& value);
 
    /// Insert at the specified `position` in this deque the specified
    /// move-insertable `value`, and return an iterator providing modifiable
    /// access to the newly inserted element.  `value` is left in a valid
    /// but unspecified state.  If an exception is thrown (other than by the
    /// copy constructor, move constructor, assignment operator, or move
    /// assignment operator of `value_type`), this method has no effect.
    /// This method requires that the (template parameter) `VALUE_TYPE` be
    /// `move-insertable` into this deque (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless `position` is an
    /// iterator in the range `[cbegin() .. cend()]` (both endpoints
    /// included).
    iterator insert(const_iterator                             position,
                    BloombergLP::bslmf::MovableRef<value_type> value);
 
    /// Insert at the specified `position` in this deque the specified
    /// `numElements` copies of the specified `value`, and return an
    /// iterator providing modifiable access to the first element in the
    /// newly inserted sequence of elements.  This method offers full
    /// guarantee of rollback in case an exception is thrown other than by
    /// the `VALUE_TYPE` copy constructor or assignment operator.  This
    /// method requires that the (template parameter) `VALUE_TYPE` be
    /// `copy-insertable` into this deque (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless `position` is an
    /// iterator in the range `[cbegin() .. cend()]` (both endpoints
    /// included).
    iterator insert(const_iterator    position,
                    size_type         numElements,
                    const VALUE_TYPE& value);
 
    /// Insert at the specified `position` in this deque the values in the
    /// range starting at the specified `first` and ending immediately
    /// before the specified `last` iterators of the (template parameter)
    /// type `INPUT_ITERATOR`, and return an iterator providing modifiable
    /// access to the first element in the newly inserted sequence of
    /// elements.  This method offers full guarantee of rollback in case an
    /// exception is thrown other than by the `VALUE_TYPE` copy constructor
    /// or assignment operator.  The (template parameter) type
    /// `INPUT_ITERATOR` shall meet the requirements of an input iterator
    /// defined in the C++11 standard [input.iterators] providing access to
    /// values of a type convertible to `value_type`, and `value_type` must
    /// be `emplace-constructible` from `*i` into this deque, where `i` is a
    /// dereferenceable iterator in the range `[first .. last)` (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless
    /// `position` is an iterator in the range `[cbegin() .. cend()]` (both
    /// endpoints included), and `first` and `last` refer to a sequence of
    /// valid values where `first` is at a position at or before `last`.
    template <class INPUT_ITERATOR>
    iterator insert(const_iterator position,
                    INPUT_ITERATOR first,
                    INPUT_ITERATOR last);
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    /// Insert at the specified `position` in this deque the value of each
    /// `value_type` object in the specified `values` initializer list, and
    /// return an iterator providing modifiable access to the first element
    /// in the newly inserted sequence of elements.  This method offers full
    /// guarantee of rollback in case an exception is thrown other than by
    /// the `VALUE_TYPE` copy constructor or assignment operator.  This
    /// method requires that the (template parameter) `VALUE_TYPE` be
    /// `copy-insertable` into this deque (see {Requirements on `VALUE_TYPE`}).  
    /// 
    /// \pre The behavior is undefined   unless `position` is an
    /// iterator in the range `[cbegin() .. cend()]` (both endpoints
    /// included).
    iterator insert(const_iterator                    position,
                    std::initializer_list<value_type> values);
#endif
 
    /// Insert at the specified `position` in this object the elements of the specified `range`.  
    /// 
    /// \note Note that   `range` must meet the requirements of an
    /// input range and the values from `range` must have a type matching or
    /// convertible to (template parameter) `VALUE_TYPE`.
    template <class t_RANGE>
    BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
    iterator insert_range(const_iterator                             position,
                          BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range);
 
    /// Remove from this deque the element at the specified `position`, and
    /// return an iterator providing modifiable access to the element
    /// immediately following the removed element, or the position returned
    /// by the method `end` if the removed element was the last in the sequence.  
    /// 
    /// \pre The behavior is undefined   unless `position` is an
    /// iterator in the range `[cbegin() .. cend())`.
    iterator erase(const_iterator position);
 
    /// Remove from this deque the sequence of elements starting at the
    /// specified `first` position and ending before the specified `last`
    /// position, and return an iterator providing modifiable access to the
    /// element immediately following the last removed element, or the
    /// position returned by the method `end` if the removed elements were last in the sequence.  
    /// 
    /// \pre The behavior is undefined   unless `first` is
    /// an iterator in the range `[cbegin() .. cend()]` (both endpoints
    /// included) and `last` is an iterator in the range
    /// `[first .. cend()]` (both endpoints included).
    iterator erase(const_iterator first, const_iterator last);
 
    /// Exchange the value of this object with that of the specified `other`
    /// object; also exchange the allocator of this object with that of
    /// `other` if the (template parameter) type `ALLOCATOR` has the
    /// @ref propagate_on_container_swap  trait, and do not modify either
    /// allocator otherwise.  This method provides the no-throw
    /// exception-safety guarantee.  This operation has `O[1]` complexity if
    /// either this object was created with the same allocator as `other` or
    /// `ALLOCATOR` has the @ref propagate_on_container_swap  trait; otherwise,
    /// it has `O[n + m]` complexity, where `n` and `m` are the number of elements in this object and `other`, respectively.  
    /// 
    /// \note Note that   this
    /// method`s support for swapping objects created with different
    /// allocators when `ALLOCATOR` does not have the
    /// @ref propagate_on_container_swap  trait is a departure from the
    /// C++ Standard.
    void swap(deque<VALUE_TYPE, ALLOCATOR>& other)
        BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
                                      AllocatorTraits::is_always_equal::value);
 
    /// Remove all elements from this deque making its size 0.  
    /// 
    /// \note Note that   although this deque is empty after this method returns, it preserves
    /// the same capacity it had before the method was called.
    void clear() BSLS_KEYWORD_NOEXCEPT;
 
    // ACCESSORS
 
    // *** construct/copy/destroy ***
 
    /// Return the allocator used by this deque to supply memory.
    allocator_type get_allocator() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the maximum possible size of this deque.  
    /// \note Note that  this is a
    /// theoretical maximum (such as the maximum value that can be held by
    /// `size_type`).  Also note that any request to create or enlarge a
    /// deque to a size greater than `max_size()` is guaranteed to raise a
    /// `bsl::length_error` exception.
    size_type max_size() const BSLS_KEYWORD_NOEXCEPT;
};
 
#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
// CLASS TEMPLATE DEDUCTION GUIDES
 
/// Deduce the template parameter `VALUE` from the corresponding parameter
/// supplied to the constructor of `deque`.  This deduction guide does not
/// participate unless the supplied allocator is convertible to
/// `bsl::allocator<VALUE>`.
template <
    class SIZE_TYPE,
    class VALUE,
    class ALLOC,
    class DEFAULT_ALLOCATOR = bsl::allocator<VALUE>,
    class = bsl::enable_if_t<
              bsl::is_convertible_v<
                SIZE_TYPE,
                typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type>>,
    class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
    >
deque(SIZE_TYPE, VALUE, ALLOC *) -> deque<VALUE>;
 
/// Deduce the template parameter `VALUE` from the `value_type` of the
/// iterators supplied to the constructor of `deque`.
template <
    class INPUT_ITERATOR,
    class VALUE =
          typename BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>
    >
deque(INPUT_ITERATOR, INPUT_ITERATOR) -> deque<VALUE>;
 
/// Deduce the template parameter `VALUE` from the `value_type` of the
/// iterators supplied to the constructor of `deque`.  This deduction guide
/// does not participate unless the supplied allocator meets the
/// requirements of a standard allocator.
template<
    class INPUT_ITERATOR,
    class ALLOCATOR,
    class VALUE =
         typename BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
    class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>>
deque(INPUT_ITERATOR, INPUT_ITERATOR, ALLOCATOR) -> deque<VALUE, ALLOCATOR>;
 
/// Deduce the template parameter `VALUE` from the `value_type` of the
/// iterators supplied to the constructor of `deque`.  This deduction guide
/// does not participate unless the supplied allocator is convertible to
/// `bsl::allocator<VALUE>`.
template<
    class INPUT_ITERATOR,
    class ALLOC,
    class VALUE =
         typename BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
    class DEFAULT_ALLOCATOR = bsl::allocator<VALUE>,
    class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
    >
deque(INPUT_ITERATOR, INPUT_ITERATOR, ALLOC *)
-> deque<VALUE>;
 
/// Deduce the template parameter `VALUE` from the `value_type` of the
/// initializer_list supplied to the constructor of `deque`.  This deduction
/// guide does not participate unless the supplied allocator is convertible
/// to `bsl::allocator<VALUE>`.
template<
    class VALUE,
    class ALLOC,
    class DEFAULT_ALLOCATOR = bsl::allocator<VALUE>,
    class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
    >
deque(std::initializer_list<VALUE>, ALLOC *)
-> deque<VALUE>;
 
#if defined(BSLS_LIBRARYFEATURES_HAS_CPP20_CONCEPTS) \
 && defined(BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES)
/// Deduce the template parameters `VALUE_TYPE` and `ALLOCATOR` from the
/// parameters supplied to the constructor of `deque`.
template <ranges::input_range t_RANGE,
          class               t_ALLOCATOR =
                                     allocator<ranges::range_value_t<t_RANGE>>>
deque(from_range_t, t_RANGE&&, t_ALLOCATOR = t_ALLOCATOR())
-> deque<ranges::range_value_t<t_RANGE>, t_ALLOCATOR>;
#endif
#endif
 
// FREE OPERATORS
 
/// Return `true` if the specified `lhs` and `rhs` objects have the same
/// value, and `false` otherwise.  Two `deque` objects `lhs` and `rhs` have
/// the same value if they have the same number of elements, and each
/// element in the ordered sequence of elements of `lhs` has the same value
/// as the corresponding element in the ordered sequence of elements of
/// `rhs`.  This method requires that the (template parameter) type
/// `VALUE_TYPE` be `equality-comparable` (see {Requirements on
/// `VALUE_TYPE`}).
template <class VALUE_TYPE, class ALLOCATOR>
bool operator==(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs);
 
#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
/// Return `true` if the specified `lhs` and `rhs` objects do not have the
/// same value, and `false` otherwise.  Two `deque` objects `lhs` and `rhs`
/// do not have the same value if they do not have the same number of
/// elements, or some element in the ordered sequence of elements of `lhs`
/// does not have the same value as the corresponding element in the ordered
/// sequence of elements of `rhs`.  This method requires that the (template
/// parameter) type `VALUE_TYPE` be `equality-comparable` (see {Requirements
/// on `VALUE_TYPE`}).
template <class VALUE_TYPE, class ALLOCATOR>
bool operator!=(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs);
#endif
 
#ifdef BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
/// Perform a lexicographic three-way comparison of the specified `lhs` and
/// the specified `rhs` containers by using the comparison operators of
/// `VALUE_TYPE` on each element; return the result of that comparison.
template <class VALUE_TYPE, class ALLOCATOR>
BloombergLP::bslalg::SynthThreeWayUtil::Result<VALUE_TYPE> operator<=>(
                                      const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                                      const deque<VALUE_TYPE, ALLOCATOR>& rhs);
 
#else
 
/// Return `true` if the value of the specified `lhs` deque is
/// lexicographically less than that of the specified `rhs` deque, and
/// `false` otherwise.  Given iterators `i` and `j` over the respective
/// sequences `[lhs.begin() .. lhs.end())` and `[rhs.begin() .. rhs.end())`,
/// the value of deque `lhs` is lexicographically less than that of deque
/// `rhs` if `true == *i < *j` for the first pair of corresponding iterator
/// positions where `*i < *j` and `*j < *i` are not both `false`.  If no
/// such corresponding iterator position exists, the value of `lhs` is
/// lexicographically less than that of `rhs` if `lhs.size() < rhs.size()`.
/// This method requires that `operator<`, inducing a total order, be
/// defined for `value_type`.
template <class VALUE_TYPE, class ALLOCATOR>
bool operator<(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
               const deque<VALUE_TYPE, ALLOCATOR>& rhs);
 
/// Return `true` if the value of the specified `lhs` deque is
/// lexicographically greater than that of the specified `rhs` deque, and
/// `false` otherwise.  The value of deque `lhs` is lexicographically
/// greater than that of deque `rhs` if `rhs` is lexicographically less than
/// `lhs` (see `operator<`).  This method requires that `operator<`, inducing a total order, be defined for `value_type`.  
/// 
/// \note Note that   this
/// operator returns `rhs < lhs`.
template <class VALUE_TYPE, class ALLOCATOR>
bool operator>(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
               const deque<VALUE_TYPE, ALLOCATOR>& rhs);
 
/// Return `true` if the value of the specified `lhs` deque is
/// lexicographically less than or equal to that of the specified `rhs`
/// deque, and `false` otherwise.  The value of deque `lhs` is
/// lexicographically less than or equal to that of deque `rhs` if `rhs` is
/// not lexicographically less than `lhs` (see `operator<`).  This method
/// requires that `operator<`, inducing a total order, be defined for `value_type`.  
/// 
/// \note Note that   this operator returns `!(rhs < lhs)`.
template <class VALUE_TYPE, class ALLOCATOR>
bool operator<=(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs);
 
/// Return `true` if the value of the specified `lhs` deque is
/// lexicographically greater than or equal to that of the specified `rhs`
/// deque, and `false` otherwise.  The value of deque `lhs` is
/// lexicographically greater than or equal to that of deque `rhs` if `lhs`
/// is not lexicographically less than `rhs` (see `operator<`).  This method
/// requires that `operator<`, inducing a total order, be defined for `value_type`.  
/// 
/// \note Note that   this operator returns `!(lhs < rhs)`.
template <class VALUE_TYPE, class ALLOCATOR>
bool operator>=(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs);
 
#endif  // BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
// FREE FUNCTIONS
 
/// Erase all the elements in the specified deque `deq` that compare equal
/// to the specified `value`.  Return the number of elements erased.
template <class VALUE_TYPE, class ALLOCATOR, class BDE_OTHER_TYPE>
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
erase(deque<VALUE_TYPE, ALLOCATOR>& deq, const BDE_OTHER_TYPE& value);
 
/// Erase all the elements in the specified deque `deq` that satisfy the
/// specified predicate `predicate`.  Return the number of elements erased.
template <class VALUE_TYPE, class ALLOCATOR, class PREDICATE>
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
erase_if(deque<VALUE_TYPE, ALLOCATOR>& deq, PREDICATE predicate);
 
/// Exchange the value of the specified `a` object with that of the
/// specified `b` object; also exchange the allocator of `a` with that of
/// `b` if the (template parameter) type `ALLOCATOR` has the
/// @ref propagate_on_container_swap  trait, and do not modify either allocator
/// otherwise.  This function provides the no-throw exception-safety
/// guarantee.  This operation has `O[1]` complexity if either `a` was
/// created with the same allocator as `b` or `ALLOCATOR` has the
/// @ref propagate_on_container_swap  trait; otherwise, it has `O[n + m]`
/// complexity, where `n` and `m` are the number of elements in `a` and `b`, respectively.  
/// 
/// \note Note that   this function`s support for swapping objects
/// created with different allocators when `ALLOCATOR` does not have the
/// @ref propagate_on_container_swap  trait is a departure from the C++
/// Standard.
template <class VALUE_TYPE, class ALLOCATOR>
void swap(deque<VALUE_TYPE, ALLOCATOR>& a, deque<VALUE_TYPE, ALLOCATOR>& b)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(BSLS_KEYWORD_NOEXCEPT_OPERATOR(
                                                                   a.swap(b)));
 
                      // ========================
                      // class Deque_BlockCreator
                      // ========================
 
/// This class allocates blocks at the front or back of a deque and
/// tentatively adds them to the deque.  It also keeps track of how many of
/// the newly allocated blocks have actually been used by the deque.  The
/// destructor automatically frees any unused blocks (e.g., in case an
/// exception is thrown).
///
/// See @ref bslstl_deque 
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_BlockCreator {
 
    // PRIVATE TYPES
    enum {
        BLOCK_LENGTH = Deque_BlockLengthCalcUtil<VALUE_TYPE>::BLOCK_LENGTH
    };
 
    typedef BloombergLP::bslalg::DequeImpUtil<VALUE_TYPE,
                                             BLOCK_LENGTH> Imp;
    typedef typename Imp::Block                            Block;
    typedef typename Imp::BlockPtr                         BlockPtr;
    typedef std::size_t                                    size_type;
 
    // DATA
    deque<VALUE_TYPE, ALLOCATOR> *d_deque_p;
    BlockPtr                     *d_boundary_p;
 
  private:
    // NOT IMPLEMENTED
    Deque_BlockCreator(const Deque_BlockCreator&);
    Deque_BlockCreator& operator=(const Deque_BlockCreator&);
 
  public:
    // CREATORS
 
    /// Construct a block allocator for the specified `deque`.
    explicit
    Deque_BlockCreator(deque<VALUE_TYPE, ALLOCATOR> *deque);
 
    /// Free any blocks that have been allocated by this allocator but have
    /// not yet been used by the deque.
    ~Deque_BlockCreator();
 
    // MANIPULATORS
 
    /// Allocate the specified `n` blocks at the front of the block array.
    /// This method invalidates all iterators except `d_deque_p->d_start`
    /// and `d_deque_p->d_finish`.
    void insertAtFront(size_type n);
 
    /// Allocate the specified `n` blocks at the back of the block array.
    /// This method invalidates all iterators except `d_deque_p->d_start`
    /// and `d_deque_p->d_finish`.
    void insertAtBack(size_type n);
 
    /// Make room for the specified `numNewBlocks` pointers in the blocks
    /// array.  If the specified `atFront` is `true`, then make room at the
    /// front of the array, else make room at the back of the array.  Return
    /// a pointer to the insertion point, i.e., the point where new blocks
    /// can be stored into the array, working backwards if `atFront` is
    /// `true`, or working forwards if `atFront` is `false`.  This method
    /// invalidates all iterators and updates `d_deque_p->d_start` and
    /// `d_deque_p->d_finish`.
    BlockPtr *reserveBlockSlots(size_type numNewBlocks, bool atFront);
 
    /// Relinquish control over any allocated blocks.  The destructor will
    /// do nothing following a call to this method.
    void release();
};
 
                        // ========================
                        // class Deque_BlockProctor
                        // ========================
 
/// This class implements a proctor that, upon destruction and unless its
/// `release` method has previously been invoked, deallocates empty blocks
/// at one end (i.e., front or back) of a proctored deque.  The end at which
/// empty blocks are to be proctored is indicated by a flag supplied at
/// construction.  See `emplace` for a use case.
///
/// See @ref bslstl_deque 
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_BlockProctor {
 
    // PRIVATE TYPES
    enum {
        BLOCK_LENGTH = Deque_BlockLengthCalcUtil<VALUE_TYPE>::BLOCK_LENGTH
    };
 
    typedef BloombergLP::bslalg::DequeImpUtil<VALUE_TYPE,
                                              BLOCK_LENGTH> Imp;
 
    typedef typename Imp::BlockPtr                          BlockPtr;
 
    // DATA
    deque<VALUE_TYPE, ALLOCATOR> *d_deque_p;     // proctored deque
 
    BlockPtr                     *d_boundary_p;  // boundary of proctored
                                                 // blocks
 
    bool                          d_atFront;     // if 'true', proctor blocks
                                                 // at the front of the deque;
                                                 // otherwise, proctor blocks
                                                 // at the block
 
  private:
    // NOT IMPLEMENTED
    Deque_BlockProctor(const Deque_BlockProctor&);
    Deque_BlockProctor& operator=(const Deque_BlockProctor&);
 
  public:
    // CREATORS
 
    /// Create a block proctor object to proctor blocks at one end (i.e.,
    /// front or back) of the specified `deque` as indicated by the
    /// specified `atFront` flag.  If `atFront` is `true`, blocks at the
    /// front of `deque` are proctored; otherwise, blocks at the back of
    /// `deque` are proctored.
    Deque_BlockProctor(deque<VALUE_TYPE, ALLOCATOR> *deque, bool atFront);
 
    /// Destroy this block proctor, and deallocate empty blocks at the back
    /// of the proctored deque as indicated by the `atFront` flag supplied
    /// at construction.  If no deque is currently being managed, this
    /// method has no effect.
    ~Deque_BlockProctor();
 
    // MANIPULATORS
 
    /// Release from management the deque currently managed by this proctor.
    /// If no deque is currently being managed, this method has no effect.
    void release();
};
 
                        // ======================
                        // class Deque_ClearGuard
                        // ======================
 
/// This class provides a proctor which, at destruction, calls `clear` on
/// the deque supplied at construction, unless the guard has been released
/// prior.
///
/// See @ref bslstl_deque 
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_ClearGuard {
 
    // PRIVATE TYPES
    typedef BloombergLP::bslalg::ContainerBase<ALLOCATOR> ContainerBase;
 
    // DATA
    deque<VALUE_TYPE, ALLOCATOR> *d_deque_p;  // proctored object
 
  private:
    // NOT IMPLEMENTED
    Deque_ClearGuard(const Deque_ClearGuard&);
    Deque_ClearGuard& operator=(const Deque_ClearGuard&);
 
  public:
    // CREATORS
 
    /// Create a clear guard object to proctor the specified `deque`.
    explicit
    Deque_ClearGuard(deque<VALUE_TYPE, ALLOCATOR> *deque);
 
    /// Destroy this guard, and call `clear` on the deque supplied at
    /// construction, unless `release` has been called on this object.
    ~Deque_ClearGuard();
 
    // MANIPULATORS
 
    /// Release from management the deque proctored by this object.
    void release();
};
 
                        // =================
                        // class Deque_Guard
                        // =================
 
/// This class provides a proctor that maintains a count of the number of
/// elements constructed at the front or back of a deque, but not yet
/// committed to the deque's range of valid elements; if the count is
/// non-zero at destruction, the destructor destroys the elements in the
/// range `[d_deque_p->end() .. d_deque_p->end() + d_count)`, or the range
/// `[d_deque_p->begin() - d_count .. d_deque_p->begin())`, depending on
/// whether this proctor guards the back or front.  This guard is used to
/// undo element constructors in the event of an exception.  It is up to the
/// client code to increment the count whenever a new element is constructed
/// and to decrement the count whenever `d_start` or `d_finish` of the
/// guarded deque is moved to incorporate more elements.
///
/// See @ref bslstl_deque 
template <class VALUE_TYPE, class ALLOCATOR>
class Deque_Guard {
 
    // PRIVATE TYPES
    enum {
        BLOCK_LENGTH = Deque_BlockLengthCalcUtil<VALUE_TYPE>::BLOCK_LENGTH
    };
 
    typedef BloombergLP::bslalg::DequeIterator<VALUE_TYPE,
                                               BLOCK_LENGTH>   IteratorImp;
    typedef BloombergLP::bslalg::DequePrimitives<VALUE_TYPE,
                                                 BLOCK_LENGTH> DequePrimitives;
 
    // DATA
    deque<VALUE_TYPE, ALLOCATOR> *d_deque_p;
    std::size_t                   d_count;
    bool                          d_isTail;
 
  private:
    // NOT IMPLEMENTED
    Deque_Guard(const Deque_Guard&);
    Deque_Guard& operator=(const Deque_Guard&);
 
  public:
    // CREATORS
 
    /// Initializes object to guard 0 items from the specified `deque`.
    /// This guards either the tail or the head, as determined by the
    /// specified `isTail` boolean.
    Deque_Guard(deque<VALUE_TYPE, ALLOCATOR> *deque, bool isTail);
 
    /// Call the (template parameter) `VALUE_TYPE` destructor on objects in
    /// the range `[d.end() .. d.end() + count())` if `isTail` was specified
    /// as `true` during construction, or
    /// `[d.start() - count() .. d.start()]` if `isTail` was specified as
    /// `false` during construction, where `d` is the deque used to
    /// construct this guard.
    ~Deque_Guard();
 
    // MANIPULATORS
 
    /// Increment the count of this guard, and return the new count.
    std::size_t operator++();
 
    /// Decrement the count of this guard, and return the new count.
    std::size_t operator--();
 
    /// Set the count of this guard to 0.  
    /// \note Note that  this guard's destructor
    /// will do nothing if count is not incremented again after this call.
    void release();
 
    // ACCESSORS
 
    /// Return the current count maintained by this guard.
    std::size_t count() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return a pointer after the first item in the guarded range.
    IteratorImp begin() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return a pointer after the last item in the guarded range.
    IteratorImp end() const BSLS_KEYWORD_NOEXCEPT;
};
 
// ============================================================================
//                  TEMPLATE AND INLINE FUNCTION DEFINITIONS
// ============================================================================
 
// See IMPLEMENTATION NOTES in the .cpp before modifying anything below.
 
                             // ----------------
                             // class Deque_Base
                             // ----------------
 
// MANIPULATORS
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::iterator
Deque_Base<VALUE_TYPE>::begin() BSLS_KEYWORD_NOEXCEPT
{
    return d_start;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::iterator
Deque_Base<VALUE_TYPE>::end() BSLS_KEYWORD_NOEXCEPT
{
    return d_finish;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::reverse_iterator
Deque_Base<VALUE_TYPE>::rbegin() BSLS_KEYWORD_NOEXCEPT
{
    return reverse_iterator(end());
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::reverse_iterator
Deque_Base<VALUE_TYPE>::rend() BSLS_KEYWORD_NOEXCEPT
{
    return reverse_iterator(begin());
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::reference
Deque_Base<VALUE_TYPE>::operator[](size_type position)
{
    BSLS_ASSERT_SAFE(position < size());
 
    return *(begin() + position);
}
 
template <class VALUE_TYPE>
typename Deque_Base<VALUE_TYPE>::reference
Deque_Base<VALUE_TYPE>::at(size_type position)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(position >= size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwOutOfRange(
                                        "deque<...>::at(n): invalid position");
    }
    return *(begin() + position);
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::reference
Deque_Base<VALUE_TYPE>::front()
{
    BSLS_ASSERT_SAFE(!empty());
 
    return *d_start;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::reference
Deque_Base<VALUE_TYPE>::back()
{
    BSLS_ASSERT_SAFE(!empty());
 
    IteratorImp backIterator = d_finish;
    --backIterator;
    return *backIterator;
}
 
// ACCESSORS
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_iterator
Deque_Base<VALUE_TYPE>::begin() const BSLS_KEYWORD_NOEXCEPT
{
    return d_start;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_iterator
Deque_Base<VALUE_TYPE>::cbegin() const BSLS_KEYWORD_NOEXCEPT
{
    return d_start;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_iterator
Deque_Base<VALUE_TYPE>::end() const BSLS_KEYWORD_NOEXCEPT
{
    return d_finish;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_iterator
Deque_Base<VALUE_TYPE>::cend() const BSLS_KEYWORD_NOEXCEPT
{
    return d_finish;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_reverse_iterator
Deque_Base<VALUE_TYPE>::rbegin() const BSLS_KEYWORD_NOEXCEPT
{
    return const_reverse_iterator(end());
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_reverse_iterator
Deque_Base<VALUE_TYPE>::crbegin() const BSLS_KEYWORD_NOEXCEPT
{
    return const_reverse_iterator(end());
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_reverse_iterator
Deque_Base<VALUE_TYPE>::rend() const BSLS_KEYWORD_NOEXCEPT
{
    return const_reverse_iterator(begin());
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_reverse_iterator
Deque_Base<VALUE_TYPE>::crend() const BSLS_KEYWORD_NOEXCEPT
{
    return const_reverse_iterator(begin());
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::size_type
Deque_Base<VALUE_TYPE>::size() const BSLS_KEYWORD_NOEXCEPT
{
    return d_finish - d_start;
}
 
template <class VALUE_TYPE>
typename Deque_Base<VALUE_TYPE>::size_type
Deque_Base<VALUE_TYPE>::capacity() const BSLS_KEYWORD_NOEXCEPT
{
    // 'allocateBlockPtrs', which creates the 'd_blocks_p' array,
    // does not, in its contract, guarantee to initialize the array to 0.
    // Since we read these values, we have to make sure they're initialized to
    // avoid purify 'read before write' errors.  Note that we initialize them
    // to null in which case they are not valid pointers, but we never
    // dereference them, and the pointer arithmetic we do on them will still
    // work.
 
    if (d_start.blockPtr() > d_blocks_p) {
        d_blocks_p[0] = 0;
    }
    if (d_finish.blockPtr() < d_blocks_p + d_blocksLength - 1) {
        d_blocks_p[d_blocksLength - 1] = 0;
    }
 
    const IteratorImp first(d_blocks_p);
 
    // 'last' points to the empty slot at the end of the last block in
    // 'd_blocks_p', which might not actually be there.
 
    IteratorImp last(d_blocks_p + d_blocksLength - 1);
    last += BLOCK_LENGTH - 1;
 
    BSLS_ASSERT_SAFE(!(d_start < first));          // 'IteratorImp' has no '>='
    BSLS_ASSERT_SAFE(!(last    < d_finish));
 
    const size_type frontCapacity = d_finish - first;
    const size_type backCapacity  = last - d_start;
 
    // Return the min (we are below 'bsl_algorithm.h', so we have to do it by
    // hand).
 
    return frontCapacity < backCapacity ? frontCapacity : backCapacity;
}
 
template <class VALUE_TYPE>
inline
bool Deque_Base<VALUE_TYPE>::empty() const BSLS_KEYWORD_NOEXCEPT
{
    return d_start == d_finish;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_reference
Deque_Base<VALUE_TYPE>::operator[](size_type position) const
{
    BSLS_ASSERT_SAFE(position < size());
 
    return *(begin() + position);
}
 
template <class VALUE_TYPE>
typename Deque_Base<VALUE_TYPE>::const_reference
Deque_Base<VALUE_TYPE>::at(size_type position) const
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(position >= size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwOutOfRange(
                                  "const deque<...>::at(n): invalid position");
    }
    return *(begin() + position);
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_reference
Deque_Base<VALUE_TYPE>::front() const
{
    BSLS_ASSERT_SAFE(!empty());
 
    return *d_start;
}
 
template <class VALUE_TYPE>
inline
typename Deque_Base<VALUE_TYPE>::const_reference
Deque_Base<VALUE_TYPE>::back() const
{
    BSLS_ASSERT_SAFE(!empty());
 
    IteratorImp backIterator = d_finish;
    --backIterator;
    return *backIterator;
}
 
                             // -----------
                             // class deque
                             // -----------
 
// PRIVATE CREATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
deque<VALUE_TYPE, ALLOCATOR>::deque(RawInit, const ALLOCATOR& allocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(allocator)
{
    this->d_blocks_p = 0;
}
 
// PRIVATE MANIPULATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::Block *
deque<VALUE_TYPE, ALLOCATOR>::allocateBlock()
{
    return AllocatorUtil::allocateObject<Block>(this->allocatorRef());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::BlockPtr *
deque<VALUE_TYPE, ALLOCATOR>::allocateBlockPtrs(std::size_t n)
{
    return AllocatorUtil::allocateObject<BlockPtr>(this->allocatorRef(), n);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
void deque<VALUE_TYPE, ALLOCATOR>::deallocateBlock(Block *p)
{
    AllocatorUtil::deallocateObject(this->allocatorRef(), p);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
void
deque<VALUE_TYPE, ALLOCATOR>::deallocateBlockPtrs(BlockPtr *p, std::size_t n)
{
    AllocatorUtil::deallocateObject(this->allocatorRef(), p, n);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::privateAppend(INPUT_ITERATOR first,
                                            SENTINEL       last)
{
    if (first == last) {
        return 0;                                                     // RETURN
    }
    typedef typename iterator_traits<INPUT_ITERATOR>::iterator_category Tag;
    return privateAppend(first, last, Tag());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::privateAppend(
                                         INPUT_ITERATOR                  first,
                                         SENTINEL                        last,
                                         std::random_access_iterator_tag)
{
    BlockCreator newBlocks(this);
    Guard guard(this, true);
 
    const size_type numElements =
                BloombergLP::bslstl::IteratorUtil::insertDistance(first, last);
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                    numElements > max_size() - this->size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
    }
 
    for ( ; first != last; ++first) {
        IteratorImp insertPoint = guard.end();
 
        // There must be room for the iterator to be incremented.  Allocate new
        // block now if necessary.  We cannot wait until after the new element
        // is constructed or else we won't be able to increment the guard right
        // away and there will be a window where an exception will cause a
        // resource leak.
 
        if (1 == insertPoint.remainingInBlock()) {
            newBlocks.insertAtBack(1);
            insertPoint = guard.end();  // 'insertAtBack(1)' invalidated
                                        // iterator
        }
        AllocatorTraits::construct(this->allocatorRef(),
                                   BSLS_UTIL_ADDRESSOF(*insertPoint),
                                   *first);
        ++guard;
    }
 
    this->d_finish += guard.count();
 
    guard.release();
    return numElements;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::privateAppend(INPUT_ITERATOR          first,
                                            SENTINEL                last,
                                            std::input_iterator_tag)
{
    BlockCreator newBlocks(this);
    Guard guard(this, true);
 
    size_type numElements = 0;
    size_type maxNumElements = max_size() - this->size();
    for ( ; first != last; ++first) {
        ++numElements;
        if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                               numElements > maxNumElements)) {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
        }
        IteratorImp insertPoint = guard.end();
 
        // There must be room for the iterator to be incremented.  Allocate new
        // block now if necessary.  We cannot wait until after the new element
        // is constructed or else we won't be able to increment the guard right
        // away and there will be a window where an exception will cause a
        // resource leak.
 
        if (1 == insertPoint.remainingInBlock()) {
            newBlocks.insertAtBack(1);
            insertPoint = guard.end();  // 'insertAtBack(1)' invalidated
                                        // iterator
        }
 
        AllocatorTraits::construct(this->allocatorRef(),
                                   BSLS_UTIL_ADDRESSOF(*insertPoint),
                                   *first);
        ++guard;
    }
 
    this->d_finish += guard.count();
 
    guard.release();
    return numElements;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::privateAppendDefaultInsertable(
                                                         size_type numElements)
{
    // Create new blocks at the back.  In case an exception is thrown, any
    // unused blocks are returned to the allocator.
 
    size_type numNewBlocks = (this->d_finish.offsetInBlock() + numElements) /
                                                                  BLOCK_LENGTH;
    BlockCreator newBlocks(this);
    newBlocks.insertAtBack(numNewBlocks);
    DequePrimitives::valueInititalizeN(&this->d_finish,
                                       this->d_finish,
                                       numElements,
                                       this->allocatorRef());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::privateAppendRaw(
                                                 size_type         numElements,
                                                 const VALUE_TYPE& value)
{
    // Create new blocks at the back.  In case an exception is thrown, any
    // unused blocks are returned to the allocator.
 
    size_type numNewBlocks = (this->d_finish.offsetInBlock() + numElements) /
                                                                  BLOCK_LENGTH;
    BlockCreator newBlocks(this);
    newBlocks.insertAtBack(numNewBlocks);
 
    DequePrimitives::uninitializedFillNBack(&this->d_finish,
                                            this->d_finish,
                                            numElements,
                                            value,
                                            this->allocatorRef());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class t_ITERATOR, class t_SENTINEL>
void deque<VALUE_TYPE, ALLOCATOR>::privateAssign(t_ITERATOR first,
                                                 t_SENTINEL last)
{
    typedef typename iterator_traits<t_ITERATOR>::iterator_category Tag;
 
    // If an exception is thrown, clear the deque to provide standard behavior,
    // which is:
    // ```
    // erase(begin(), end());
    // insert(begin(), first, last);
    // ```
 
    ClearGuard guard(this);
 
    // Copy over existing elements.
 
    IteratorImp i;
    for (i = this->d_start; !(i == this->d_finish) && first != last;
                                                                ++i, ++first) {
        *i = *first;
    }
 
    if (!(i == this->d_finish)) {
        // Erase elements past the last one copied.
 
        erase(i, this->end());
    }
    else {
        // Still more elements to copy.  Append them.
 
        privateAppend(first, last, Tag());
    }
 
    guard.release();
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::privateInit(size_type numElements)
{
    size_type blocksLength = numElements / BLOCK_LENGTH + 1 +
                                                  2 * Imp::BLOCK_ARRAY_PADDING;
 
    // Allocate block pointer array.
 
    this->d_blocks_p     = this->allocateBlockPtrs(blocksLength);
 
    this->d_blocksLength = blocksLength;
 
    // Allocate the first block and store its pointer into the array.  Leave a
    // little room at the front and back of the array for growth.
 
    BlockPtr *firstBlockPtr = &this->d_blocks_p[Imp::BLOCK_ARRAY_PADDING];
    *firstBlockPtr = this->allocateBlock();
 
    // Calculate the offset into the first block such that 'n' elements will
    // leave equal space at the front of the first block and at the end of the
    // last block, remembering that the last element of the last block cannot
    // be used.  Centering the elements reduces the chance that either
    // 'push_back' or 'push_front' will need to allocate a new block.  In case
    // of an odd number of unused elements, slight preference is given to
    // 'push_back' over 'push_front'.
 
    const int offset = static_cast<int>(
                          (BLOCK_LENGTH - 1 - numElements % BLOCK_LENGTH) / 2);
 
    // Initialize the begin and end iterators.
 
    this->d_start = this->d_finish = IteratorImp(
                                            firstBlockPtr,
                                            (*firstBlockPtr)->d_data + offset);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INTEGRAL_TYPE>
inline
void deque<VALUE_TYPE, ALLOCATOR>::privateInsertDispatch(
                           const_iterator                          position,
                           INTEGRAL_TYPE                           numElements,
                           INTEGRAL_TYPE                           value,
                           BloombergLP::bslmf::MatchArithmeticType,
                           BloombergLP::bslmf::Nil)
{
    insert(position,
           static_cast<size_type>(numElements),
           static_cast<VALUE_TYPE>(value));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR>
void deque<VALUE_TYPE, ALLOCATOR>::privateInsertDispatch(
                                     const_iterator                   position,
                                     INPUT_ITERATOR                   first,
                                     INPUT_ITERATOR                   last,
                                     BloombergLP::bslmf::MatchAnyType,
                                     BloombergLP::bslmf::MatchAnyType)
{
    typedef typename iterator_traits<INPUT_ITERATOR>::iterator_category Tag;
 
    if (first == last) {
        return;                                                       // RETURN
    }
 
    if (position == this->cbegin()) {
        privatePrepend(first, last, Tag());
        return;                                                       // RETURN
    }
 
    if (position == this->cend()) {
        privateAppend(first, last, Tag());
        return;                                                       // RETURN
    }
 
    privateInsert(position, first, last, Tag());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
inline
void deque<VALUE_TYPE, ALLOCATOR>::privateInsert(const_iterator position,
                                                 INPUT_ITERATOR first,
                                                 SENTINEL       last)
{
    if (first == last) {
        return;                                                       // RETURN
    }
 
    typedef typename iterator_traits<INPUT_ITERATOR>::iterator_category Tag;
    if (position == this->cbegin()) {
        privatePrepend(first, last, Tag());
    }
    else if (position == this->cend()) {
        privateAppend(first, last, Tag());
    }
    else {
        privateInsert(position, first, last, Tag());
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
void deque<VALUE_TYPE, ALLOCATOR>::privateInsert(
                                              const_iterator          position,
                                              INPUT_ITERATOR          first,
                                              SENTINEL                last,
                                              std::input_iterator_tag tag)
{
    BSLS_ASSERT(first != last);
 
    iterator pos(position.imp());
    const size_type currentSize = this->size();
    const size_type posIdx      = pos - this->begin();
 
    deque temp(k_RAW_INIT, this->get_allocator());
    privateSplit(&temp, position.imp());
 
    if (posIdx <= currentSize / 2) {
        Deque_Util::swap(
                        static_cast<Base *>(this), static_cast<Base *>(&temp));
        privatePrepend(first, last, tag);
        privateJoinPrepend(&temp);
    }
    else {
        privateAppend(first, last, tag);
        privateJoinAppend(&temp);
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::privateSplit(
                                           deque<VALUE_TYPE, ALLOCATOR> *other,
                                           IteratorImp                   pos)
{
    // BEFORE:
    //..
    //  this->d_start.valuePtr() -----------+
    //                                      V
    //  this->d_start.blockPtr() --> H -> __AAA
    //                               I -> AAAAA
    //             pos.blockPtr() -> J -> BBBxx <- pos.valuePtr() (at 1st x)
    //                               K -> yyyyy
    //  this->d_finish.blockPtr() -> L -> y____
    //                                     ^
    //                                     +- this->d_finish.valuePtr()
    //
    // AFTER:
    //  this->d_start.valuePtr() -----------+
    //                                      V
    //  this->d_start.blockPtr() --> H -> __AAA
    //                               I -> AAAAA
    //  this->d_finish.blockPtr() -> J -> BBB__
    //                                       ^
    //                                       +- this->d_finish.valuePtr()
    //
    // other->d_start.valuePtr() ------------+
    //                                       V
    // other->d_start.blockPtr() --> M -> ___xx
    //                               K -> yyyyy
    // other->d_finish.blockPtr() -> L -> y____
    //                                     ^
    //                                     +- other->d_finish.valuePtr()
    //
    // assert(! other.d_blocks_p);
    //..
 
    if (pos.blockPtr() == this->d_finish.blockPtr()) {
        // Split point is in last block.  Just copy portion after the split to
        // new block in 'other'.
 
        difference_type numAfter = this->d_finish.valuePtr() - pos.valuePtr();
        other->privateInit(numAfter);
        BloombergLP::bslalg::ArrayPrimitives::destructiveMove(
                                                  other->d_start.valuePtr(),
                                                  pos.valuePtr(),
                                                  this->d_finish.valuePtr(),
                                                  this->allocatorRef());
        other->d_finish += numAfter;
        this->d_finish = pos;
        return;                                                       // RETURN
    }
 
    if (pos.blockPtr() == this->d_start.blockPtr()) {
        // Split point is in first block.  Copy portion before the split to new
        // block in 'other' and swap.
 
        difference_type numBefore = pos.valuePtr() - this->d_start.valuePtr();
        other->privateInit(numBefore);
        BloombergLP::bslalg::ArrayPrimitives::destructiveMove(
                                                  other->d_start.valuePtr(),
                                                  this->d_start.valuePtr(),
                                                  pos.valuePtr(),
                                                  this->allocatorRef());
        other->d_finish += numBefore;
        this->d_start = pos;
        Deque_Util::swap(
                        static_cast<Base *>(this), static_cast<Base *>(other));
        return;                                                       // RETURN
    }
 
    // Compute number of unsplit blocks to move.
 
    difference_type numMoveBlocks = this->d_finish.blockPtr() - pos.blockPtr();
 
    size_type otherBlocksLength = numMoveBlocks + 1 +
                                              2 * Imp::BLOCK_ARRAY_PADDING;
 
    other->d_blocks_p     = this->allocateBlockPtrs(otherBlocksLength);
    other->d_blocksLength = otherBlocksLength;
 
    // Good time to allocate block for exception safety.
 
    Block *newBlock = this->allocateBlock();
 
    // The following chunk of code will never throw an exception.  Move unsplit
    // blocks from 'this' to 'other', then adjust the iterators.
 
    std::memcpy(other->d_blocks_p + 1 + Imp::BLOCK_ARRAY_PADDING,
                pos.blockPtr() + 1,
                sizeof(BlockPtr) * numMoveBlocks);
 
    other->d_start = IteratorImp(&other->d_blocks_p[
                                                1 + Imp::BLOCK_ARRAY_PADDING]);
    other->d_finish = IteratorImp(other->d_start.blockPtr() +
                                  numMoveBlocks - 1,
                                  this->d_finish.valuePtr());
 
    BlockPtr *newBlockPtr = pos.blockPtr() + 1;
    *newBlockPtr = newBlock;
    this->d_finish = IteratorImp(newBlockPtr);
 
    // Current situation:
    //..
    //  this->d_start.valuePtr() -----------+
    //                                      V
    //  this->d_start.blockPtr() --> H -> __AAA
    //                               I -> AAAAA
    //             pos.blockPtr() -> J -> BBBxx <- pos.valuePtr() (1st x)
    //  this->d_finish.blockPtr() -> M -> _____
    //                              /        ^
    //                newBlockPtr -+         +- this->d_finish.valuePtr()
    //
    //  other->d_start.valuePtr() ---------+
    //                                     V
    //  other->d_start.blockPtr() --> K -> yyyyy
    //  other->d_finish.blockPtr() -> L -> y____
    //                                      ^
    //                                      +- other->d_finish.valuePtr()
    //..
    // Now we split the block containing "BBBxx" into two blocks, with the "xx"
    // part going into '*newBlockPtr'.  An exception can safely occur here
    // because the 'bslalg::ArrayPrimitives' functions are exception-neutral
    // and because all class invariants for both '*this' and 'other' hold going
    // in to this section.
 
    size_type splitOffset = pos.offsetInBlock();
    if (splitOffset >= pos.remainingInBlock()) {
        // Move the tail part of the block into the new block.
 
        value_type *splitValuePtr = newBlock->d_data + splitOffset;
        BloombergLP::bslalg::ArrayPrimitives::destructiveMove(
                                                  splitValuePtr,
                                                  pos.valuePtr(),
                                                  pos.blockEnd(),
                                                  this->allocatorRef());
    }
    else {
        // Move the head part of the block into the new block, then swap the
        // blocks within the 'd_blocks_p' array.
 
        BloombergLP::bslalg::ArrayPrimitives::destructiveMove(
                                                  newBlock->d_data,
                                                  pos.blockBegin(),
                                                  pos.valuePtr(),
                                                  this->allocatorRef());
        *newBlockPtr    = *pos.blockPtr();
        *pos.blockPtr() = newBlock;
    }
 
    // Move block to 'other' and adjust the iterators.  This will not throw.
 
    this->d_finish = IteratorImp(&newBlockPtr[-1],
                                 newBlockPtr[-1]->d_data + splitOffset);
    other->d_start.previousBlock();
    *(other->d_start.blockPtr()) = *newBlockPtr;
    other->d_start = IteratorImp(other->d_start.blockPtr(),
                                 other->d_start.blockBegin() + splitOffset);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
void deque<VALUE_TYPE, ALLOCATOR>::privateJoinPrepend(
                                           deque<VALUE_TYPE, ALLOCATOR> *other)
{
    privatePrepend(other->begin(),
                   other->end(),
                   std::random_access_iterator_tag());
 
    // Make 'other' raw again, and free its resources.
 
    deque<VALUE_TYPE, ALLOCATOR> temp(k_RAW_INIT, other->allocatorRef());
    Deque_Util::move(static_cast<Base *>(&temp), static_cast<Base *>(other));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
void deque<VALUE_TYPE, ALLOCATOR>::privateJoinAppend(
                                           deque<VALUE_TYPE, ALLOCATOR> *other)
{
    privateAppend(other->begin(),
                  other->end(),
                  std::random_access_iterator_tag());
 
    // Make 'other' raw again, and free its resources.
 
    deque<VALUE_TYPE, ALLOCATOR> temp(k_RAW_INIT, other->allocatorRef());
    Deque_Util::move(static_cast<Base *>(&temp), static_cast<Base *>(other));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
void deque<VALUE_TYPE, ALLOCATOR>::privateInsert(
                                      const_iterator                  position,
                                      INPUT_ITERATOR                  first,
                                      SENTINEL                        last,
                                      std::random_access_iterator_tag tag)
{
    BSLS_ASSERT(first != last);
 
    if (position == this->cbegin()) {
        privatePrepend(first, last, tag);
        return;                                                       // RETURN
    }
 
    if (position == this->cend()) {
        privateAppend(first, last, tag);
        return;                                                       // RETURN
    }
 
    const size_type currentSize = this->size();
    const size_type numElements =
                BloombergLP::bslstl::IteratorUtil::insertDistance(first, last);
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                     numElements > max_size() - currentSize)) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
    }
 
    iterator pos(position.imp());
    const size_type posIdx = position - this->cbegin();
    if (posIdx <= currentSize / 2) {
        // Create new blocks at the front.  In case an exception is thrown, any
        // unused blocks are returned to the allocator.
 
        size_type numNewBlocks = (this->d_start.remainingInBlock()
                                             + numElements - 1) / BLOCK_LENGTH;
        BlockCreator newBlocks(this);
        newBlocks.insertAtFront(numNewBlocks);
 
        DequePrimitives::insertAndMoveToFront(&this->d_start,
                                              this->d_start,
                                              this->d_start + posIdx,
                                              first,
                                              last,
                                              numElements,
                                              this->allocatorRef());
    } else {
        // Create new blocks at front.  In case an exception is thrown, any
        // unused blocks are returned to the allocator.
 
        size_type numNewBlocks = (this->d_finish.offsetInBlock() + numElements)
                                                                / BLOCK_LENGTH;
        BlockCreator newBlocks(this);
        newBlocks.insertAtBack(numNewBlocks);
 
        DequePrimitives::insertAndMoveToBack(&this->d_finish,
                                             this->d_finish,
                                             this->d_start + posIdx,
                                             first,
                                             last,
                                             numElements,
                                             this->allocatorRef());
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::privatePrependRaw(
                                                 size_type         numElements,
                                                 const VALUE_TYPE& value)
{
    // Create new blocks at front.  In case an exception is thrown, any unused
    // blocks are returned to the allocator.
 
    size_type numNewBlocks = (this->d_start.remainingInBlock() +
                                               numElements - 1) / BLOCK_LENGTH;
    BlockCreator newBlocks(this);
    newBlocks.insertAtFront(numNewBlocks);
 
    DequePrimitives::uninitializedFillNFront(&this->d_start,
                                             this->d_start,
                                             numElements,
                                             value,
                                             this->allocatorRef());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::privatePrepend(INPUT_ITERATOR first,
                                             SENTINEL       last)
{
    if (first == last) {
        return 0;                                                     // RETURN
    }
    typedef typename iterator_traits<INPUT_ITERATOR>::iterator_category Tag;
    return privatePrepend(first, last, Tag());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::privatePrepend(INPUT_ITERATOR          first,
                                             SENTINEL                last,
                                             std::input_iterator_tag tag)
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(this->size() + 1);
    size_type numElements = temp.privateAppend(first, last, tag);
 
    // Check whether appending or prepending is more economical.
 
    if (numElements > this->size()) {
        Deque_Util::swap((Base *)this, (Base *)&temp);
        privateJoinAppend(&temp);
    }
    else {
        privateJoinPrepend(&temp);
    }
 
    return numElements;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::privatePrepend(
                                         INPUT_ITERATOR                  first,
                                         SENTINEL                        last,
                                         std::bidirectional_iterator_tag)
{
 
    BlockCreator newBlocks(this);
    Guard guard(this, false);
 
    size_type numElements = 0;
    size_type maxNumElements = max_size() - this->size();
    do {
        ++numElements;
        if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                               numElements > maxNumElements)) {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
        }
 
        IteratorImp insertPoint = guard.begin();
 
        // There must be room for the iterator to be decremented.  Allocate new
        // block now if necessary, with same caveat as above.
 
        if (insertPoint.valuePtr() == insertPoint.blockBegin()) {
            newBlocks.insertAtFront(1);
            insertPoint = guard.begin();  // 'insertAtFront' invalidates
                                          // 'insertPoint'
        }
        --insertPoint;
        AllocatorTraits::construct(this->allocatorRef(),
                                   BSLS_UTIL_ADDRESSOF(*insertPoint),
                                   *--last);
        ++guard;
    } while (first != last);
 
    this->d_start -= guard.count();
    guard.release();
    return numElements;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR, class SENTINEL>
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::privatePrepend(
                                         INPUT_ITERATOR                  first,
                                         SENTINEL                        last,
                                         std::random_access_iterator_tag)
{
    BSLS_ASSERT_OPT((BloombergLP::bslstl::IteratorUtil
                    ::canCalculateInsertDistance<INPUT_ITERATOR, SENTINEL>()));
    const size_type numElements =
                BloombergLP::bslstl::IteratorUtil::insertDistance(first, last);
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                    numElements > max_size() - this->size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
    }
 
    BlockCreator newBlocks(this);
    Guard guard(this, false);
 
#ifdef BSLS_LIBRARYFEATURES_HAS_CPP20_RANGES
    INPUT_ITERATOR end;
    if constexpr (std::is_same_v<INPUT_ITERATOR, SENTINEL>) {
        end = last;
    }
    else {
        end = first + numElements;
        BSLS_ASSERT_SAFE(end == last);
    }
#else
    INPUT_ITERATOR end = last;
#endif
    do {
        IteratorImp insertPoint = guard.begin();
 
        // There must be room for the iterator to be decremented.  Allocate new
        // block now if necessary, with same caveat as above.
 
        if (insertPoint.valuePtr() == insertPoint.blockBegin()) {
            newBlocks.insertAtFront(1);
            insertPoint = guard.begin();  // 'insertAtFront' invalidates
                                          // 'insertPoint'
        }
        --insertPoint;
        AllocatorTraits::construct(this->allocatorRef(),
                                   BSLS_UTIL_ADDRESSOF(*insertPoint),
                                   *--end);
        ++guard;
    } while (first != end);
 
    this->d_start -= guard.count();
    guard.release();
    return numElements;
}
 
// CREATORS
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque()
: Deque_Base<VALUE_TYPE>()
, ContainerBase(ALLOCATOR())
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(0);
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(const ALLOCATOR& basicAllocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(basicAllocator)
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(0);
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(size_type        numElements,
                                    const ALLOCATOR& basicAllocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(basicAllocator)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(numElements > max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                        "deque<...>::deque(n): deque too big");
    }
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(numElements);
    temp.privateAppendDefaultInsertable(numElements);
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(size_type         numElements,
                                    const VALUE_TYPE& value,
                                    const ALLOCATOR&  basicAllocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(basicAllocator)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(numElements > max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                      "deque<...>::deque(n,v): deque too big");
    }
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(numElements);
    temp.privateAppendRaw(numElements, value);
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(INPUT_ITERATOR   first,
                                    INPUT_ITERATOR   last,
                                    const ALLOCATOR& basicAllocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(basicAllocator)
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(0);
    temp.insert(temp.begin(), first, last);
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class t_RANGE>
BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
deque<VALUE_TYPE, ALLOCATOR>::deque(
                     from_range_t                               ,
                     BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range,
                     const ALLOCATOR&                           basicAllocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(basicAllocator)
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(0);
    temp.append_range(BSLS_COMPILERFEATURES_FORWARD(t_RANGE, range));
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(const deque& original)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(AllocatorTraits::select_on_container_copy_construction(
                                                     original.get_allocator()))
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(original.size());
    temp.privateAppend(original.begin(),
                       original.end(),
                       std::random_access_iterator_tag());
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(
                 const deque&                                   original,
                 const typename type_identity<ALLOCATOR>::type& basicAllocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(basicAllocator)
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(original.size());
    temp.privateAppend(original.begin(),
                       original.end(),
                       std::random_access_iterator_tag());
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(
                                BloombergLP::bslmf::MovableRef<deque> original)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(MoveUtil::access(original).get_allocator())
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(0);
    Deque_Util::move(static_cast<Base *>(this), static_cast<Base *>(&temp));
 
    deque& lvalue = original;
    Deque_Util::swap(static_cast<Base *>(this), static_cast<Base *>(&lvalue));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::deque(
                 BloombergLP::bslmf::MovableRef<deque>          original,
                 const typename type_identity<ALLOCATOR>::type& basicAllocator)
: Deque_Base<VALUE_TYPE>()
, ContainerBase(basicAllocator)
{
    deque temp(k_RAW_INIT, this->get_allocator());
    temp.privateInit(0);
 
    deque& lvalue = original;
 
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
                                  get_allocator() == lvalue.get_allocator())) {
        Deque_Util::move(static_cast<Base *>(this),
                         static_cast<Base *>(&temp));
        Deque_Util::swap(static_cast<Base *>(this),
                         static_cast<Base *>(&lvalue));
    }
    else {
        const size_type size = lvalue.size();
        temp.reserve(size);
        for (size_type pos = 0; pos < size; ++pos) {
            temp.push_back(MoveUtil::move(lvalue[pos]));
        }
        Deque_Util::move(static_cast<Base *>(this),
                         static_cast<Base *>(&temp));
    }
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE_TYPE, class ALLOCATOR>
inline
deque<VALUE_TYPE, ALLOCATOR>::deque(
                              std::initializer_list<value_type> values,
                              const ALLOCATOR&                  basicAllocator)
: deque(values.begin(), values.end(), basicAllocator)
{
}
#endif
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>::~deque()
{
    if (0 == this->d_blocks_p) {
        // Nothing to do when destroying raw deques.
 
        return;                                                       // RETURN
    }
 
    if (0 != this->d_start.blockPtr()) {
        // Destroy all elements and deallocate all but one block.
        clear();
 
        // Deallocate the remaining (empty) block.
        this->deallocateBlock(*this->d_start.blockPtr());
    }
 
    // Deallocate the array of block pointers.
    this->deallocateBlockPtrs(this->d_blocks_p, this->d_blocksLength);
}
 
// MANIPULATORS
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>&
deque<VALUE_TYPE, ALLOCATOR>::operator=(const deque<VALUE_TYPE,ALLOCATOR>& rhs)
{
    typedef typename
        AllocatorTraits::propagate_on_container_copy_assignment Propagate;
 
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(this != &rhs)) {
        if (Propagate::value && get_allocator() != rhs.get_allocator()) {
            deque other(rhs, rhs.get_allocator());
 
            Deque_Util::swap(static_cast<Base *>(this),
                             static_cast<Base *>(&other));
            AllocatorUtil::swap(&this->allocatorRef(), &other.allocatorRef(),
                                Propagate());
        }
        else {
            size_type origSize = this->size();
            size_type rhsSize  = rhs.size();
            size_type minSize;
 
            if (origSize > rhsSize) {
                // Make shorter by deleting excess elements.
 
                minSize = rhsSize;
                erase(this->begin() + minSize, this->end());
            }
            else {
                // Make longer by appending new elements.
 
                minSize = origSize;
                privateAppend(rhs.begin() + minSize,
                              rhs.end(),
                              std::random_access_iterator_tag());
            }
 
            // Copy the smaller of the number of elements in 'rhs' and '*this'.
 
            IteratorImp from = rhs.d_start;
            IteratorImp to   = this->d_start;
            for (size_type i = 0; i < minSize; ++i) {
                *to = *from;
                ++to;
                ++from;
            }
        }
    }
 
    return *this;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
deque<VALUE_TYPE, ALLOCATOR>&
deque<VALUE_TYPE, ALLOCATOR>::operator=(
                                     BloombergLP::bslmf::MovableRef<deque> rhs)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
                                       AllocatorTraits::is_always_equal::value)
{
    deque& lvalue = rhs;
 
    typedef typename
        AllocatorTraits::propagate_on_container_move_assignment Propagate;
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(this != &lvalue)) {
        if (get_allocator() == lvalue.get_allocator()) {
            Deque_Util::swap(static_cast<Base *>(this),
                             static_cast<Base *>(&lvalue));
        }
        else if (Propagate::value) {
            deque other(MoveUtil::move(lvalue));
            Deque_Util::swap(static_cast<Base *>(this),
                             static_cast<Base *>(&other));
            AllocatorUtil::swap(&this->allocatorRef(), &other.allocatorRef(),
                                Propagate());
        }
        else {
            deque other(MoveUtil::move(lvalue), get_allocator());
            Deque_Util::swap(static_cast<Base *>(this),
                             static_cast<Base *>(&other));
        }
    }
    return *this;
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE_TYPE, class ALLOCATOR>
inline
deque<VALUE_TYPE, ALLOCATOR>&
deque<VALUE_TYPE, ALLOCATOR>::operator=(
                                      std::initializer_list<value_type> values)
{
    assign(values.begin(), values.end());
    return *this;
}
#endif
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR>
void deque<VALUE_TYPE, ALLOCATOR>::assign(INPUT_ITERATOR first,
                                          INPUT_ITERATOR last)
{
    privateAssign(first, last);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::assign(size_type         numElements,
                                          const VALUE_TYPE& value)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(numElements > max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                     "deque<...>::assign(n,v): deque too big");
    }
 
    // If an exception is thrown, clear the deque to provide standard behavior,
    // which is:
    //..
    //  erase(begin(), end());
    //  insert(begin(), first, last);
    //..
 
    ClearGuard guard(this);
 
    size_type origSize = this->size();
    size_type minSize;
 
    if (numElements < origSize) {
        minSize = numElements;
        erase(this->begin() + numElements, this->end());
    }
    else {
        minSize = origSize;
        privateAppendRaw(numElements - origSize, value);
    }
 
    IteratorImp to = this->d_start;
    for (size_type i = 0; i < minSize; ++i) {
        *to = value;
        ++to;
    }
 
    guard.release();
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE_TYPE, class ALLOCATOR>
inline
void deque<VALUE_TYPE, ALLOCATOR>::assign(
                                      std::initializer_list<value_type> values)
{
    assign(values.begin(), values.end());
}
#endif
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class t_RANGE>
BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
void deque<VALUE_TYPE, ALLOCATOR>::assign_range(
                              BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range)
{
    privateAssign(ranges::begin(range), ranges::end(range));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::reserve(size_type numElements)
{
    // Make sure 'numElements' isn't high enough to make the calculations of
    // 'num(Front|Back)Blocks' overflow.
 
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(numElements >
                                            max_size() - (BLOCK_LENGTH - 1))) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                      "deque<...>::reserve(n): deque too big");
    }
 
    // 'allocateBlockPtrs', which creates the 'd_blocks_p' array, does
    // not, in its contract, guarantee to initialize the array to 0.  Since we
    // read these values, we have to make sure they're initialized to avoid
    // purify 'read before write' errors.  Note that we initialize them to 0,
    // making them invalid pointers, but we never dereference them, and the
    // pointer arithmetic we do on them will still work.
 
    if (this->d_start.blockPtr() > this->d_blocks_p) {
        this->d_blocks_p[0] = 0;
    }
    if (this->d_finish.blockPtr() < this->d_blocks_p + this->d_blocksLength-1){
        this->d_blocks_p[this->d_blocksLength - 1] = 0;
    }
 
    const IteratorImp first(this->d_blocks_p);
    IteratorImp       last( this->d_blocks_p + this->d_blocksLength - 1);
    last += BLOCK_LENGTH - 1;
 
    const size_type frontRoom = this->d_start - first;
    const size_type backRoom  = last - this->d_finish;
 
    size_type numFrontBlocks = numElements > frontRoom
                             ? (numElements - frontRoom + BLOCK_LENGTH - 1) /
                                                                   BLOCK_LENGTH
                             : 0;
    size_type numBackBlocks  = numElements > backRoom
                             ? (numElements - backRoom  + BLOCK_LENGTH - 1) /
                                                                   BLOCK_LENGTH
                             : 0;
 
    if (0 == numFrontBlocks && 0 == numBackBlocks) {
        return;                                                       // RETURN
    }
 
    // Make sure that if we throw, it's before we modify the deque.
 
    size_type existingSpace = last - first;
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(numFrontBlocks >
                               (max_size() - existingSpace) / BLOCK_LENGTH
       || (existingSpace += numFrontBlocks * BLOCK_LENGTH,
                           numBackBlocks >
                               (max_size() - existingSpace) / BLOCK_LENGTH))) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                      "deque<...>::reserve(n): deque too big");
    }
 
    // When 'numFrontBlocks' or 'numBackBlocks' are 0, the respective calls
    // will be no-ops.
 
    BlockCreator newBlocks(this);
    newBlocks.reserveBlockSlots(numFrontBlocks, true);
    newBlocks.reserveBlockSlots(numBackBlocks,  false);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::resize(size_type newSize)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(newSize > max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                     "deque<...>::resize(n): deque too big");
    }
 
    size_type origSize = this->size();
 
    if (newSize <= origSize) {
        // Note that we do not use 'erase' here as 'erase' requires elements be
        // copy-insertable, while the standard does not require elements be
        // copy-insertable for this 'resize' overload.
 
        IteratorImp oldEnd = this->d_finish;
        IteratorImp newEnd = this->d_start + newSize;
        DequePrimitives::destruct(newEnd, oldEnd, this->allocatorRef());
        // Deallocate blocks no longer used
        for (; oldEnd.blockPtr() != newEnd.blockPtr();
               oldEnd.previousBlock()) {
            this->deallocateBlock(*oldEnd.blockPtr());
        }
        this->d_finish = newEnd;
    }
    else {
        privateAppendDefaultInsertable(newSize - origSize);
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::resize(size_type         newSize,
                                          const VALUE_TYPE& value)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(newSize > max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                     "deque<...>::resize(n,v): deque too big");
    }
 
    size_type origSize = this->size();
 
    if (newSize <= origSize) {
        erase(this->begin() + newSize, this->end());
    }
    else {
        privateAppendRaw(newSize - origSize, value);
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::shrink_to_fit()
{
    // Minimize the length of 'd_blocks_p' without moving any elements.  A more
    // complex algorithm is not justified.  At most 'BLOCK_LENGTH' bytes are
    // wasted.
 
    const size_type newBlocksLength =
                      this->d_finish.blockPtr() - this->d_start.blockPtr() + 1;
 
    if (newBlocksLength == this->d_blocksLength) {
        return;                                                       // RETURN
    }
 
    const size_type offsetStart  = this->d_start.offsetInBlock();
    const size_type offsetFinish = this->d_finish.offsetInBlock();
 
    BlockPtr *newBlocks = this->allocateBlockPtrs(newBlocksLength);
 
    std::memmove(newBlocks,
                 this->d_start.blockPtr(),
                 newBlocksLength * sizeof(BlockPtr));
 
    this->deallocateBlockPtrs(this->d_blocks_p, this->d_blocksLength);
 
    this->d_blocks_p     = newBlocks;
    this->d_blocksLength = newBlocksLength;
 
    this->d_start.setBlock(newBlocks);
    this->d_start += offsetStart;
 
    this->d_finish.setBlock(newBlocks + newBlocksLength - 1);
    this->d_finish += offsetFinish;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class t_RANGE>
BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
void deque<VALUE_TYPE, ALLOCATOR>::append_range(
                              BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range)
{
    privateAppend(ranges::begin(range), ranges::end(range));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class t_RANGE>
BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
void deque<VALUE_TYPE, ALLOCATOR>::prepend_range(
                              BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range)
{
    privatePrepend(ranges::begin(range), ranges::end(range));
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::push_front(const VALUE_TYPE& value)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(this->size() >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                   "deque<...>::push_front(v): deque too big");
    }
 
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                         0 == this->d_start.offsetInBlock())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BlockCreator newBlocks(this);
        newBlocks.insertAtFront(1);  // The deque's value is not modified.
 
        AllocatorTraits::construct(
            this->allocatorRef(), (this->d_start - 1).valuePtr(), value);
 
        --this->d_start;
    }
    else {
        // Since the offset is non-zero, it is safe to directly decrement the
        // pointer.  This is much quicker than calling 'operator--'.
 
        AllocatorTraits::construct(
            this->allocatorRef(), this->d_start.valuePtr() - 1, value);
        this->d_start.valuePtrDecrement();
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::push_front(
                              BloombergLP::bslmf::MovableRef<value_type> value)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(this->size() >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                   "deque<...>::push_front(v): deque too big");
    }
 
    VALUE_TYPE& lvalue = value;
 
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                         0 == this->d_start.offsetInBlock())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BlockCreator newBlocks(this);
        newBlocks.insertAtFront(1);  // The deque's value is not modified.
 
        AllocatorTraits::construct(this->allocatorRef(),
                                   (this->d_start - 1).valuePtr(),
                                   MoveUtil::move(lvalue));
        --this->d_start;
    }
    else {
        // Since the offset is non-zero, it is safe to directly decrement the
        // pointer.  This is much quicker than calling 'operator--'.
 
        AllocatorTraits::construct(this->allocatorRef(),
                                   this->d_start.valuePtr() - 1,
                                   MoveUtil::move(lvalue));
        this->d_start.valuePtrDecrement();
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::push_back(const VALUE_TYPE& value)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(this->size() >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                    "deque<...>::push_back(v): deque too big");
    }
 
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
                                      1 < this->d_finish.remainingInBlock())) {
        AllocatorTraits::construct(
                 this->allocatorRef(), this->d_finish.valuePtr(), value);
        this->d_finish.valuePtrIncrement();
    }
    else {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BlockCreator newBlocks(this);
        newBlocks.insertAtBack(1);  // The deque's value is not modified.
 
        AllocatorTraits::construct(
                 this->allocatorRef(), this->d_finish.valuePtr(), value);
        this->d_finish.nextBlock();
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::push_back(
                              BloombergLP::bslmf::MovableRef<value_type> value)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(this->size() >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                    "deque<...>::push_back(v): deque too big");
    }
 
    VALUE_TYPE& lvalue = value;
 
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
                                      1 < this->d_finish.remainingInBlock())) {
        AllocatorTraits::construct(this->allocatorRef(),
                                   this->d_finish.valuePtr(),
                                   MoveUtil::move(lvalue));
        this->d_finish.valuePtrIncrement();
    }
    else {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BlockCreator newBlocks(this);
        newBlocks.insertAtBack(1);  // The deque's value is not modified.
 
        AllocatorTraits::construct(this->allocatorRef(),
                                   this->d_finish.valuePtr(),
                                   MoveUtil::move(lvalue));
        this->d_finish.nextBlock();
    }
}
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class VALUE_TYPE, class ALLOCATOR>
template <class... Args>
typename deque<VALUE_TYPE, ALLOCATOR>::reference
deque<VALUE_TYPE, ALLOCATOR>::emplace_front(Args&&...arguments)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(this->size() >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                             "deque<...>::emplace_front(args): deque too big");
    }
 
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                         0 == this->d_start.offsetInBlock())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BlockCreator newBlocks(this);
        newBlocks.insertAtFront(1);  // The deque's value is not modified.
 
        AllocatorTraits::construct(
                            this->allocatorRef(),
                            (this->d_start - 1).valuePtr(),
                            BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        --this->d_start;
    }
    else {
        // Since the offset is non-zero, it is safe to directly decrement the
        // pointer.  This is much quicker than calling 'operator--'.
 
        AllocatorTraits::construct(
                            this->allocatorRef(),
                            this->d_start.valuePtr() - 1,
                            BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        this->d_start.valuePtrDecrement();
    }
    return *(this->d_start);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class... Args>
typename deque<VALUE_TYPE, ALLOCATOR>::reference
deque<VALUE_TYPE, ALLOCATOR>::emplace_back(Args&&...arguments)
{
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(this->size() >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                              "deque<...>::emplace_back(args): deque too big");
    }
 
    if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
                                      1 < this->d_finish.remainingInBlock())) {
        AllocatorTraits::construct(
                            this->allocatorRef(),
                            this->d_finish.valuePtr(),
                            BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        this->d_finish.valuePtrIncrement();
    }
    else {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BlockCreator newBlocks(this);
        newBlocks.insertAtBack(1);  // The deque's value is not modified.
 
        AllocatorTraits::construct(
                            this->allocatorRef(),
                            this->d_finish.valuePtr(),
                            BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        this->d_finish.nextBlock();
    }
    return *(this->d_finish - 1);
}
#endif
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class VALUE_TYPE, class ALLOCATOR>
template <class... Args>
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::emplace(const_iterator position,
                                      Args&&...      arguments)
{
    BSLS_ASSERT(position >= this->cbegin());
    BSLS_ASSERT(position <= this->cend());
 
    if (position == this->cbegin()) {
        emplace_front(BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        return this->begin();                                         // RETURN
    }
 
    if (position == this->cend()) {
        emplace_back(BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        return iterator(this->d_finish - 1);                          // RETURN
    }
 
    // The test is placed here because @ref emplace_front  and @ref emplace_back  do
    // the same check.
 
    const size_type currentSize = this->size();
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(currentSize >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                   "deque<...>::emplace(args): deque too big");
    }
 
    iterator pos(position.imp());
    const size_type posIdx = position - this->cbegin();
    if (posIdx <= currentSize / 2) {
        BlockCreator newBlocks(this);
        if (this->d_start.remainingInBlock() == BLOCK_LENGTH) {
            newBlocks.insertAtFront(1);
        }
 
        BlockProctor proctor(this, true);
        DequePrimitives::emplaceAndMoveToFront(
                            &this->d_start,
                            this->d_start,
                            this->d_start + posIdx,
                            this->allocatorRef(),
                            BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        proctor.release();
    }
    else {
        BlockCreator newBlocks(this);
        if (this->d_finish.offsetInBlock() == BLOCK_LENGTH - 1) {
            newBlocks.insertAtBack(1);
        }
 
        BlockProctor proctor(this, false);
        DequePrimitives::emplaceAndMoveToBack(
                            &this->d_finish,
                            this->d_finish,
                            this->d_start + posIdx,
                            this->allocatorRef(),
                            BSLS_COMPILERFEATURES_FORWARD(Args, arguments)...);
        proctor.release();
    }
    return this->begin() + posIdx;
}
#endif
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::pop_front()
{
    BSLS_ASSERT(!this->empty());
 
    BloombergLP::bslma::DestructionUtil::destroy(this->d_start.valuePtr());
 
    if (1 == this->d_start.remainingInBlock()) {
        this->deallocateBlock(*this->d_start.blockPtr());
        this->d_start.nextBlock();
        return;                                                       // RETURN
    }
 
    this->d_start.valuePtrIncrement();
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::pop_back()
{
    BSLS_ASSERT(!this->empty());
 
    if (0 == this->d_finish.offsetInBlock()) {
        --this->d_finish;
        BloombergLP::bslma::DestructionUtil::destroy(
                                                    this->d_finish.valuePtr());
        this->deallocateBlock(this->d_finish.blockPtr()[1]);
        return;                                                       // RETURN
    }
 
    this->d_finish.valuePtrDecrement();
    BloombergLP::bslma::DestructionUtil::destroy(this->d_finish.valuePtr());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::insert(const_iterator    position,
                                     const VALUE_TYPE& value)
{
    BSLS_ASSERT(position >= this->cbegin());
    BSLS_ASSERT(position <= this->cend());
 
    if (position == this->cbegin()) {
        push_front(value);
        return this->begin();                                         // RETURN
    }
 
    if (position == this->cend()) {
        push_back(value);
        return iterator(this->d_finish - 1);                          // RETURN
    }
 
    // The test is placed here because 'push_front' and 'push_back' do the same
    // check.
 
    const size_type currentSize = this->size();
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(currentSize >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
    }
 
    iterator pos(position.imp());
    const size_type posIdx = position - this->cbegin();
    if (posIdx <= currentSize / 2) {
        BlockCreator newBlocks(this);
        if (this->d_start.remainingInBlock() == BLOCK_LENGTH) {
            newBlocks.insertAtFront(1);
        }
        DequePrimitives::insertAndMoveToFront(&this->d_start,
                                              this->d_start,
                                              this->d_start + posIdx,
                                              1,
                                              value,
                                              this->allocatorRef());
    }
    else {
        BlockCreator newBlocks(this);
        if (this->d_finish.offsetInBlock() == BLOCK_LENGTH - 1) {
            newBlocks.insertAtBack(1);
        }
        DequePrimitives::insertAndMoveToBack(&this->d_finish,
                                             this->d_finish,
                                             this->d_start + posIdx,
                                             1,
                                             value,
                                             this->allocatorRef());
    }
    return this->begin() + posIdx;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::insert(
                           const_iterator                             position,
                           BloombergLP::bslmf::MovableRef<VALUE_TYPE> value)
{
    BSLS_ASSERT(position >= this->cbegin());
    BSLS_ASSERT(position <= this->cend());
 
    VALUE_TYPE& lvalue = value;
 
    if (position == this->cbegin()) {
        push_front(MoveUtil::move(lvalue));
        return this->begin();                                         // RETURN
    }
 
    if (position == this->cend()) {
        push_back(MoveUtil::move(lvalue));
        return iterator(this->d_finish - 1);                          // RETURN
    }
 
    // The test is placed here because 'push_front' and 'push_back' do the same
    // check.
 
    const size_type currentSize = this->size();
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(currentSize >= max_size())) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
    }
 
    iterator pos(position.imp());
    const size_type posIdx = position - this->cbegin();
    if (posIdx <= currentSize / 2) {
        BlockCreator newBlocks(this);
        if (this->d_start.remainingInBlock() == BLOCK_LENGTH) {
            newBlocks.insertAtFront(1);
        }
        DequePrimitives::moveInsertAndMoveToFront(&this->d_start,
                                                  this->d_start,
                                                  this->d_start + posIdx,
                                                  MoveUtil::move(lvalue),
                                                  this->allocatorRef());
    }
    else {
        BlockCreator newBlocks(this);
        if (this->d_finish.offsetInBlock() == BLOCK_LENGTH - 1) {
            newBlocks.insertAtBack(1);
        }
        DequePrimitives::moveInsertAndMoveToBack(&this->d_finish,
                                                 this->d_finish,
                                                 this->d_start + posIdx,
                                                 MoveUtil::move(lvalue),
                                                 this->allocatorRef());
    }
    return this->begin() + posIdx;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::insert(const_iterator    position,
                                     size_type         numElements,
                                     const VALUE_TYPE& value)
{
    BSLS_ASSERT(position >= this->cbegin());
    BSLS_ASSERT(position <= this->cend());
 
    const size_type posIdx = position - this->cbegin();
 
    if (0 == numElements) {
        return this->begin() + posIdx;                                // RETURN
    }
 
    const size_type currentSize = this->size();
    if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(
                                     numElements > max_size() - currentSize)) {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        BloombergLP::bslstl::StdExceptUtil::throwLengthError(
                                 "deque<...>::insert(pos,n,v): deque too big");
    }
 
    if (position == this->cbegin()) {
        privatePrependRaw(numElements, value);
 
        return this->begin();                                         // RETURN
    }
 
    if (position == this->cend()) {
        privateAppendRaw(numElements, value);
 
        return this->begin() + posIdx;                                // RETURN
    }
 
    if (posIdx <= currentSize / 2) {
        // Create new blocks at front.  In case an exception is thrown, any
        // unused blocks are returned to the allocator.
 
        size_type numNewBlocks = (this->d_start.remainingInBlock()
                                             + numElements - 1) / BLOCK_LENGTH;
        BlockCreator newBlocks(this);
        newBlocks.insertAtFront(numNewBlocks);
 
        DequePrimitives::insertAndMoveToFront(&this->d_start,
                                              this->d_start,
                                              this->d_start + posIdx,
                                              numElements,
                                              value,
                                              this->allocatorRef());
    }
    else {
        // Create new blocks at back.  In case an exception is thrown, any
        // unused blocks are returned to the allocator.
 
        size_type numNewBlocks = (this->d_finish.offsetInBlock() + numElements)
                                                                / BLOCK_LENGTH;
        BlockCreator newBlocks(this);
        newBlocks.insertAtBack(numNewBlocks);
 
        DequePrimitives::insertAndMoveToBack(&this->d_finish,
                                             this->d_finish,
                                             this->d_start + posIdx,
                                             numElements,
                                             value,
                                             this->allocatorRef());
    }
 
    return this->begin() + posIdx;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class INPUT_ITERATOR>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::insert(const_iterator position,
                                     INPUT_ITERATOR first,
                                     INPUT_ITERATOR last)
{
    BSLS_ASSERT_SAFE(position >= this->cbegin());
    BSLS_ASSERT_SAFE(position <= this->cend());
 
    const size_type posIdx = position - this->cbegin();
 
    privateInsertDispatch(position,
                          first,
                          last,
                          first,
                          BloombergLP::bslmf::Nil());
 
    return this->begin() + posIdx;
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE_TYPE, class ALLOCATOR>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::insert(
                                    const_iterator                    position,
                                    std::initializer_list<value_type> values)
{
    BSLS_ASSERT_SAFE(position >= this->cbegin());
    BSLS_ASSERT_SAFE(position <= this->cend());
 
    return insert(position, values.begin(), values.end());
}
#endif
 
template <class VALUE_TYPE, class ALLOCATOR>
template <class t_RANGE>
BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE(t_RANGE, VALUE_TYPE)
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::insert_range(
                           const_iterator                             position,
                           BSLS_COMPILERFEATURES_FORWARD_REF(t_RANGE) range)
{
    const size_type posIdx = position - this->cbegin();
    privateInsert(position, ranges::begin(range), ranges::end(range));
    return this->begin() + posIdx;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::erase(const_iterator position)
{
    BSLS_ASSERT(position >= this->cbegin());
    BSLS_ASSERT(position <  this->cend());
 
    if (position == const_iterator(this->d_start)) {
        pop_front();
        return this->begin();                                         // RETURN
    }
 
    if (position + 1 == const_iterator(this->d_finish)) {
        pop_back();
        return this->end();                                           // RETURN
    }
 
    return erase(position, position + 1);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
typename deque<VALUE_TYPE, ALLOCATOR>::iterator
deque<VALUE_TYPE, ALLOCATOR>::erase(const_iterator first, const_iterator last)
{
    BSLS_ASSERT(first >= this->cbegin());
    BSLS_ASSERT(first <= this->cend());
    BSLS_ASSERT(first <= last);
    BSLS_ASSERT(last  <= this->cend());
 
    iterator first_imp = this->begin() + (first - this->cbegin());
    iterator last_imp  = this->begin() + (last  - this->cbegin());
    iterator oldStart  = this->begin();
    iterator oldFinish = this->end();
    iterator result = iterator(DequePrimitives::erase(&this->d_start,
                                                      &this->d_finish,
                                                      this->d_start,
                                                      first_imp.imp(),
                                                      last_imp.imp(),
                                                      this->d_finish,
                                                      this->allocatorRef()));
 
    // Deallocate blocks no longer used.
 
    for ( ; oldStart.imp().blockPtr() != this->d_start.blockPtr();
                                                  oldStart.imp().nextBlock()) {
        this->deallocateBlock(oldStart.imp().blockPtr()[0]);
    }
    for ( ; oldFinish.imp().blockPtr() != this->d_finish.blockPtr();
                                             oldFinish.imp().previousBlock()) {
        this->deallocateBlock(oldFinish.imp().blockPtr()[0]);
    }
    return result;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::swap(deque<VALUE_TYPE, ALLOCATOR>& other)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
                                       AllocatorTraits::is_always_equal::value)
{
    typedef typename
        AllocatorTraits::propagate_on_container_swap Propagate;
    if (Propagate::value) {
        Deque_Util::swap(static_cast<Base *>(this),
                         static_cast<Base *>(&other));
        AllocatorUtil::swap(&this->allocatorRef(), &other.allocatorRef(),
                            Propagate());
    }
    else {
        if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
                             this->get_allocator() == other.get_allocator())) {
            Deque_Util::swap(static_cast<Base *>(this),
                             static_cast<Base *>(&other));
        }
        else {
            BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
            deque toOtherCopy(MoveUtil::move(*this), other.get_allocator());
            deque toThisCopy( MoveUtil::move(other), this->get_allocator());
 
            Deque_Util::swap(static_cast<Base *>(&toThisCopy),
                             static_cast<Base *>(this));
            Deque_Util::swap(static_cast<Base *>(&toOtherCopy),
                             static_cast<Base *>(&other));
        }
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void deque<VALUE_TYPE, ALLOCATOR>::clear() BSLS_KEYWORD_NOEXCEPT
{
    DequePrimitives::destruct(this->d_start,
                              this->d_finish,
                              this->allocatorRef());
 
    // Deallocate all blocks except 'finishBlock'.
 
    BlockPtr *startBlock  = this->d_start.blockPtr();
    BlockPtr *finishBlock = this->d_finish.blockPtr();
    for ( ; startBlock != finishBlock; ++startBlock) {
        this->deallocateBlock(*startBlock);
    }
 
    // Reposition in the middle.
 
    size_type  blockOffset = this->d_blocksLength / 2;
    int        offset      = BLOCK_LENGTH / 2;
    BlockPtr  *blockPtr    = this->d_blocks_p + blockOffset;
 
    *blockPtr = *finishBlock;
 
    this->d_start = this->d_finish = IteratorImp(blockPtr,
                                                 (*blockPtr)->d_data + offset);
}
 
// ACCESSORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::allocator_type
deque<VALUE_TYPE, ALLOCATOR>::get_allocator() const BSLS_KEYWORD_NOEXCEPT
{
    return this->allocatorRef();
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
typename deque<VALUE_TYPE, ALLOCATOR>::size_type
deque<VALUE_TYPE, ALLOCATOR>::max_size() const BSLS_KEYWORD_NOEXCEPT
{
    return AllocatorTraits::max_size(this->get_allocator());
}
 
// FREE OPERATORS
template <class VALUE_TYPE, class ALLOCATOR>
bool operator==(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs)
{
    if (lhs.size() != rhs.size()) {
        return false;                                                 // RETURN
    }
 
    enum {
        BLOCK_LENGTH = Deque_BlockLengthCalcUtil<VALUE_TYPE>::BLOCK_LENGTH
    };
 
    typedef BloombergLP::bslalg::DequeIterator<VALUE_TYPE,
                                               BLOCK_LENGTH> Iterator;
 
    Iterator lhsBegin = lhs.begin().imp();
    Iterator lhsEnd   = lhs.end().imp();
    Iterator rhsBegin = rhs.begin().imp();
 
    for (; !(lhsBegin == lhsEnd); ++lhsBegin, ++rhsBegin) {
        if (!(*lhsBegin == *rhsBegin)) {
            return false;                                             // RETURN
        }
    }
    return true;
}
 
#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
bool operator!=(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs)
{
    return !(lhs == rhs);
}
 
#endif
 
#ifdef BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
BloombergLP::bslalg::SynthThreeWayUtil::Result<VALUE_TYPE> operator<=>(
                                       const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                                       const deque<VALUE_TYPE, ALLOCATOR>& rhs)
{
    return bsl::lexicographical_compare_three_way(
                              lhs.begin(),
                              lhs.end(),
                              rhs.begin(),
                              rhs.end(),
                              BloombergLP::bslalg::SynthThreeWayUtil::compare);
}
 
#else
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
bool operator<(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
               const deque<VALUE_TYPE, ALLOCATOR>& rhs)
{
    return 0 > BloombergLP::bslalg::RangeCompare::lexicographical(lhs.begin(),
                                                                  lhs.end(),
                                                                  lhs.size(),
                                                                  rhs.begin(),
                                                                  rhs.end(),
                                                                  rhs.size());
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
bool operator>(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
               const deque<VALUE_TYPE, ALLOCATOR>& rhs)
{
    return rhs < lhs;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
bool operator<=(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs)
{
    return !(rhs < lhs);
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
bool operator>=(const deque<VALUE_TYPE, ALLOCATOR>& lhs,
                const deque<VALUE_TYPE, ALLOCATOR>& rhs)
{
    return !(lhs < rhs);
}
 
#endif  // BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
// FREE FUNCTIONS
template <class VALUE_TYPE, class ALLOCATOR, class BDE_OTHER_TYPE>
inline typename deque<VALUE_TYPE, ALLOCATOR>::size_type
erase(deque<VALUE_TYPE, ALLOCATOR>& deq, const BDE_OTHER_TYPE& value)
{
    typename deque<VALUE_TYPE, ALLOCATOR>::size_type oldSize = deq.size();
    deq.erase(bsl::remove(deq.begin(), deq.end(), value), deq.end());
    return oldSize - deq.size();
}
 
template <class VALUE_TYPE, class ALLOCATOR, class PREDICATE>
inline typename deque<VALUE_TYPE, ALLOCATOR>::size_type
erase_if(deque<VALUE_TYPE, ALLOCATOR>& deq, PREDICATE predicate)
{
    typename deque<VALUE_TYPE, ALLOCATOR>::size_type oldSize = deq.size();
    deq.erase(bsl::remove_if(deq.begin(), deq.end(), predicate), deq.end());
    return oldSize - deq.size();
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
void swap(deque<VALUE_TYPE, ALLOCATOR>& a, deque<VALUE_TYPE, ALLOCATOR>& b)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(BSLS_KEYWORD_NOEXCEPT_OPERATOR(
                                                                    a.swap(b)))
{
    a.swap(b);
}
 
                      // ------------------------
                      // class Deque_BlockCreator
                      // ------------------------
 
// CREATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>::Deque_BlockCreator(
                                           deque<VALUE_TYPE, ALLOCATOR> *deque)
: d_deque_p(deque)
, d_boundary_p(0)
{
}
 
template <class VALUE_TYPE, class ALLOCATOR>
Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>::~Deque_BlockCreator()
{
    if (0 != d_boundary_p) {
        BlockPtr *delFirst, *delLast;
        if (d_boundary_p <= d_deque_p->d_start.blockPtr()) {
            delFirst = d_boundary_p;
            delLast  = d_deque_p->d_start.blockPtr();
        }
        else {
            delFirst = d_deque_p->d_finish.blockPtr() + 1;
            delLast  = d_boundary_p;
        }
 
        for (; delFirst != delLast; ++delFirst) {
            // Deallocate the block that '*delFirst' points to.
            d_deque_p->deallocateBlock(*delFirst);
        }
    }
}
 
// MANIPULATORS
template <class VALUE_TYPE, class ALLOCATOR>
void Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>::insertAtFront(size_type n)
{
    d_boundary_p = reserveBlockSlots(n, true);
    for ( ; n > 0; --n) {
        d_boundary_p[-1] = d_deque_p->allocateBlock();
 
        --d_boundary_p;
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
void Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>::insertAtBack(size_type n)
{
    d_boundary_p = reserveBlockSlots(n, false);
    for ( ; n > 0; --n) {
        *d_boundary_p = d_deque_p->allocateBlock();
        ++d_boundary_p;
    }
}
 
template <class VALUE_TYPE, class ALLOCATOR>
typename Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>::BlockPtr *
Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>::reserveBlockSlots(
                                                        size_type numNewBlocks,
                                                        bool      atFront)
{
    BlockPtr  *blocks       = d_deque_p->d_blocks_p;
    size_type  blocksLength = d_deque_p->d_blocksLength;
 
    BlockPtr *firstSlot = d_deque_p->d_start.blockPtr();
    BlockPtr *lastSlot  = d_deque_p->d_finish.blockPtr() + 1;
 
    if (atFront) {
        if (d_boundary_p) {
            firstSlot = d_boundary_p;
        }
        if (size_type(firstSlot - blocks) >= numNewBlocks) {
            // Enough room to insert at the front.
 
            return firstSlot;                                         // RETURN
        }
    }
    else {
        if (d_boundary_p) {
            lastSlot = d_boundary_p;
        }
        if (size_type(blocks + blocksLength - lastSlot) >= numNewBlocks) {
            // Enough room to insert at the back.
 
            return lastSlot;                                          // RETURN
        }
    }
 
    BlockPtr  *newBlocks          = blocks;
    size_type  newBlocksLength    = blocksLength;
    size_type  numUsedBlocks      = lastSlot - firstSlot;
    size_type  blockOffsetStart   = d_deque_p->d_start.blockPtr() - firstSlot;
    size_type  numCommittedBlocks = (d_deque_p->d_finish.blockPtr() -
                                            d_deque_p->d_start.blockPtr() + 1);
    size_type  newNumUsedBlocks   = numUsedBlocks + numNewBlocks;
 
    if (newNumUsedBlocks > blocksLength) {
        const size_type newThreshold = newNumUsedBlocks +
                                                  2 * Imp::BLOCK_ARRAY_PADDING;
        while (newThreshold > newBlocksLength) {
            // Insufficient room.  Allocate new blocks array with geometric
            // growth.  Note that this should never overflow because there are
            // at least 16 elements in each block, thus the requested block
            // array pointer will never be close to 'max_size() / 2'.
 
            newBlocksLength *= 2;
        }
        newBlocks = d_deque_p->allocateBlockPtrs(newBlocksLength);
    }
 
    // Center block pointers within new blocks array.
 
    BlockPtr *newFirstSlot = newBlocks +
                                      (newBlocksLength - newNumUsedBlocks) / 2;
 
    if (atFront) {
        newFirstSlot += numNewBlocks;
    }
 
    // Calculate offset for start and finish.  Need to do this before moving
    // around blocks.
 
    const size_type offsetStart  = d_deque_p->d_start.offsetInBlock();
    const size_type offsetFinish = d_deque_p->d_finish.offsetInBlock();
 
    // Move old block pointers into new position.
 
    std::memmove(newFirstSlot, firstSlot, numUsedBlocks * sizeof(BlockPtr));
 
    if (newBlocks != blocks) {
        // Deallocate old blocks array and install the new one.
 
        if (blocks) {
            d_deque_p->deallocateBlockPtrs(blocks, d_deque_p->d_blocksLength);
        }
        d_deque_p->d_blocks_p     = newBlocks;
        d_deque_p->d_blocksLength = newBlocksLength;
    }
 
    // Adjust start and finish iterators.
 
    d_deque_p->d_start.setBlock(newFirstSlot + blockOffsetStart);
    d_deque_p->d_start += offsetStart;
    d_deque_p->d_finish.setBlock(newFirstSlot + blockOffsetStart +
                                                       numCommittedBlocks - 1);
    d_deque_p->d_finish += offsetFinish;
 
    BlockPtr *ret = newFirstSlot;
    if (!atFront) {
        ret += numUsedBlocks;
    }
 
    return ret;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
void Deque_BlockCreator<VALUE_TYPE, ALLOCATOR>::release()
{
    d_boundary_p = 0;
}
 
                      // ------------------------
                      // class Deque_BlockProctor
                      // ------------------------
 
// CREATORS
template <class VALUE_TYPE, class ALLOCATOR>
Deque_BlockProctor<VALUE_TYPE, ALLOCATOR>::Deque_BlockProctor(
                                         deque<VALUE_TYPE, ALLOCATOR> *deque,
                                         bool                          atFront)
: d_deque_p(deque)
, d_boundary_p(atFront
               ? d_deque_p->d_start.blockPtr()
               : d_deque_p->d_finish.blockPtr())
, d_atFront(atFront)
{
}
 
template <class VALUE_TYPE, class ALLOCATOR>
Deque_BlockProctor<VALUE_TYPE, ALLOCATOR>::~Deque_BlockProctor()
{
    if (0 != d_deque_p) {
        BlockPtr *delFirst, *delLast;
 
        if (d_atFront && d_boundary_p < d_deque_p->d_start.blockPtr()) {
            // Blocks at the front of the deque have been emptied since this
            // proctor was created.
 
            delFirst = d_boundary_p;
            delLast  = d_deque_p->d_start.blockPtr();
        }
        else if (!d_atFront && d_boundary_p > d_deque_p->d_finish.blockPtr()) {
            // Blocks at the back of the deque have been emptied since this
            // proctor was created.
 
            delFirst = d_deque_p->d_finish.blockPtr() + 1;
            delLast  = d_boundary_p + 1;
        }
        else {
            return;                                                   // RETURN
        }
 
        for (; delFirst != delLast; ++delFirst) {
            // Deallocate the block that '*delFirst' points to.
 
            d_deque_p->deallocateBlock(*delFirst);
        }
    }
}
 
// MANIPULATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
void Deque_BlockProctor<VALUE_TYPE, ALLOCATOR>::release()
{
    d_deque_p = 0;
}
 
                        // ----------------------
                        // class Deque_ClearGuard
                        // ----------------------
 
// CREATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
Deque_ClearGuard<VALUE_TYPE, ALLOCATOR>::Deque_ClearGuard(
                                           deque<VALUE_TYPE, ALLOCATOR> *deque)
: d_deque_p(deque)
{
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
Deque_ClearGuard<VALUE_TYPE, ALLOCATOR>::~Deque_ClearGuard()
{
    if (d_deque_p) {
        d_deque_p->clear();
    }
}
 
// MANIPULATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
void Deque_ClearGuard<VALUE_TYPE, ALLOCATOR>::release()
{
    d_deque_p = 0;
}
 
                        // -----------------
                        // class Deque_Guard
                        // -----------------
 
// CREATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
Deque_Guard<VALUE_TYPE, ALLOCATOR>::Deque_Guard(
                                          deque<VALUE_TYPE, ALLOCATOR> *deque,
                                          bool                          isTail)
: d_deque_p(deque)
, d_count(0)
, d_isTail(isTail)
{
}
 
template <class VALUE_TYPE, class ALLOCATOR>
Deque_Guard<VALUE_TYPE, ALLOCATOR>::~Deque_Guard()
{
    if (0 == d_count) {
        return;                                                       // RETURN
    }
 
    IteratorImp begin, end;
 
    if (d_isTail) {
        begin = d_deque_p->d_finish;
        end   = begin + d_count;
    }
    else {
        end   = d_deque_p->d_start;
        begin = end - d_count;
    }
 
    DequePrimitives::destruct(begin, end, d_deque_p->get_allocator());
}
 
// MANIPULATORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
std::size_t Deque_Guard<VALUE_TYPE, ALLOCATOR>::operator++()
{
    return ++d_count;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
std::size_t Deque_Guard<VALUE_TYPE, ALLOCATOR>::operator--()
{
    return --d_count;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
void Deque_Guard<VALUE_TYPE, ALLOCATOR>::release()
{
    d_count = 0;
}
 
// ACCESSORS
template <class VALUE_TYPE, class ALLOCATOR>
inline
std::size_t
Deque_Guard<VALUE_TYPE, ALLOCATOR>::count() const BSLS_KEYWORD_NOEXCEPT
{
    return d_count;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
typename Deque_Guard<VALUE_TYPE, ALLOCATOR>::IteratorImp
Deque_Guard<VALUE_TYPE, ALLOCATOR>::begin() const BSLS_KEYWORD_NOEXCEPT
{
    return d_deque_p->d_start - d_count;
}
 
template <class VALUE_TYPE, class ALLOCATOR>
inline
typename Deque_Guard<VALUE_TYPE, ALLOCATOR>::IteratorImp
Deque_Guard<VALUE_TYPE, ALLOCATOR>::end() const BSLS_KEYWORD_NOEXCEPT
{
    return d_deque_p->d_finish + d_count;
}
 
}  // close namespace bsl
 
// ============================================================================
//                                TYPE TRAITS
// ============================================================================
 
// Type traits for STL *sequence* containers:
//: o A sequence container defines STL iterators.
//: o A sequence container is bitwise-movable if its allocator is
//:   bitwise-movable.
//: o A sequence container uses 'bslma' allocators if the (template parameter)
//:   type 'ALLOCATOR' is convertible from 'bslma::Allocator *'.
 
 
 
namespace bslalg {
 
template <class VALUE_TYPE, class ALLOCATOR>
struct HasStlIterators<bsl::deque<VALUE_TYPE, ALLOCATOR> > : bsl::true_type
{
};
 
}  // close namespace bslalg
 
namespace bslmf {
 
template <class VALUE_TYPE, class ALLOCATOR>
struct IsBitwiseMoveable<bsl::deque<VALUE_TYPE, ALLOCATOR> >
    : IsBitwiseMoveable<ALLOCATOR>
{
};
 
}  // close namespace bslmf
 
namespace bslma {
 
template <class VALUE_TYPE, class ALLOCATOR>
struct UsesBslmaAllocator<bsl::deque<VALUE_TYPE, ALLOCATOR> >
    : bsl::is_convertible<Allocator *, ALLOCATOR>
{
};
 
}  // close namespace bslma
 
 
 
#endif // End C++11 code
 
#undef BSLSTL_DEQUE_REQUIRES_CONTAINER_COMPATIBLE_RANGE
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */