[#bsl-deque-0c]
= xref:bsl.adoc[bsl]::deque
:relfileprefix: ../
:mrdocs:

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 `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`.

== Synopsis

Declared in `<bslstl_deque.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<
    class VALUE_TYPE,
    class ALLOCATOR = xref:bsl/allocator-0df.adoc[allocator<VALUE_TYPE>]>
class deque
    : public xref:bsl/Deque_Base.adoc[Deque_Base<VALUE_TYPE>]
----

== Description

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 {`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.

== Base Classes

[cols="1,4"]
|===
| Name| Description
| `xref:bsl/Deque_Base.adoc[Deque_Base<VALUE_TYPE>]`
| 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 that this class must have the same layout as `Deque_Imp` (see implementation file).
|===

== Type Aliases

[cols="1,4"]
|===
| Name| Description
| xref:bsl/deque-0c/allocator_type.adoc[`allocator_type`] 
| This `typedef` is an alias to the (template parameter) `ALLOCATOR`.
| xref:bsl/deque-0c/const_iterator.adoc[`const_iterator`] 
| This `typedef` is an alias for `const_iterator`.
| xref:bsl/deque-0c/const_pointer.adoc[`const_pointer`] 
| This `typedef` is an alias for `const_pointer`.
| xref:bsl/deque-0c/const_reference.adoc[`const_reference`] 
| This `typedef` is an alias for `const_reference`.
| xref:bsl/deque-0c/const_reverse_iterator.adoc[`const_reverse_iterator`] 
| This `typedef` is an alias to `bsl::reverse_iterator<const_iterator>`.
| xref:bsl/deque-0c/difference_type.adoc[`difference_type`] 
| This `typedef` is an alias for `difference_type`.
| xref:bsl/deque-0c/iterator-02.adoc[`iterator`] 
| This `typedef` is an alias to `Iterator`.
| xref:bsl/deque-0c/pointer.adoc[`pointer`] 
| This `typedef` is an alias to `AllocatorTraits::pointer`.
| xref:bsl/deque-0c/reference.adoc[`reference`] 
| This `typedef` is an alias for `reference`.
| xref:bsl/deque-0c/reverse_iterator.adoc[`reverse_iterator`] 
| This `typedef` is an alias to `bsl::reverse_iterator<iterator>`.
| xref:bsl/deque-0c/size_type.adoc[`size_type`] 
| This `typedef` is an alias for `size_type`.
| xref:bsl/deque-0c/value_type.adoc[`value_type`] 
| This `typedef` is an alias for `value_type`.
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:bsl/deque-0c/2constructor-0f62.adoc[`deque`]         [.small]#[constructor]#
| Constructors
| xref:bsl/deque-0c/2destructor.adoc[`~deque`] [.small]#[destructor]#
| Destroy this object.
| xref:bsl/deque-0c/operator_assign-05f.adoc[`operator=`] 
| Assignment operators
| xref:bsl/deque-0c/append_range.adoc[`append_range`] 
| Append to the end of this object the elements of the specified `range`. 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`.
| xref:bsl/deque-0c/assign-0e.adoc[`assign`] 
| `assign` overloads
| xref:bsl/deque-0c/assign_range.adoc[`assign_range`] 
| Assign to this object the elements of the specified `range`. 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`.
| xref:bsl/Deque_Base/at-04.adoc[`at`] 
| `at` overloads
| xref:bsl/Deque_Base/back-06.adoc[`back`] 
| `back` overloads
| xref:bsl/Deque_Base/begin-0fd.adoc[`begin`] 
| `begin` overloads
| xref:bsl/Deque_Base/capacity.adoc[`capacity`] 
| 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 that this method is not part of the C++ standard.
| xref:bsl/Deque_Base/cbegin.adoc[`cbegin`] 
| 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.
| xref:bsl/Deque_Base/cend.adoc[`cend`] 
| Return the past‐the‐end (forward) iterator providing non‐modifiable access to this deque.
| xref:bsl/deque-0c/clear.adoc[`clear`] 
| Remove all elements from this deque making its size 0. Note that although this deque is empty after this method returns, it preserves the same capacity it had before the method was called.
| xref:bsl/Deque_Base/crbegin.adoc[`crbegin`] 
| 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.
| xref:bsl/Deque_Base/crend.adoc[`crend`] 
| Return the past‐the‐end reverse iterator providing non‐modifiable access to this deque.
| xref:bsl/deque-0c/emplace.adoc[`emplace`] 
| 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`}). The behavior is undefined unless `position` is an iterator in the range `[cbegin() .. cend()]` (both endpoints included).
| xref:bsl/deque-0c/emplace_back.adoc[`emplace_back`] 
| 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`}).
| xref:bsl/deque-0c/emplace_front.adoc[`emplace_front`] 
| 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`}).
| xref:bsl/Deque_Base/empty.adoc[`empty`] 
| Return `true` if this deque contains no elements, and `false` otherwise.
| xref:bsl/Deque_Base/end-01.adoc[`end`] 
| `end` overloads
| xref:bsl/deque-0c/erase-0f.adoc[`erase`] 
| `erase` overloads
| xref:bsl/Deque_Base/front-04.adoc[`front`] 
| `front` overloads
| xref:bsl/deque-0c/get_allocator.adoc[`get_allocator`] 
| Return the allocator used by this deque to supply memory.
| xref:bsl/deque-0c/insert-07.adoc[`insert`] 
| `insert` overloads
| xref:bsl/deque-0c/insert_range.adoc[`insert_range`] 
| Insert at the specified `position` in this object the elements of the specified `range`. 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`.
| xref:bsl/deque-0c/max_size.adoc[`max_size`] 
| Return the maximum possible size of this deque. 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.
| xref:bsl/Deque_Base/operator_subs-09.adoc[`operator[]`] 
| Subscript operators
| xref:bsl/deque-0c/pop_back.adoc[`pop_back`] 
| Erase the last element from this deque. The behavior is undefined if this deque is empty.
| xref:bsl/deque-0c/pop_front.adoc[`pop_front`] 
| Erase the first element from this deque. The behavior is undefined if this deque is empty.
| xref:bsl/deque-0c/prepend_range.adoc[`prepend_range`] 
| Prepend to the front of this object the elements of the specified `range`. 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`.
| xref:bsl/deque-0c/push_back-0f.adoc[`push_back`] 
| `push_back` overloads
| xref:bsl/deque-0c/push_front-0e.adoc[`push_front`] 
| `push_front` overloads
| xref:bsl/Deque_Base/rbegin-09.adoc[`rbegin`] 
| `rbegin` overloads
| xref:bsl/Deque_Base/rend-02.adoc[`rend`] 
| `rend` overloads
| xref:bsl/deque-0c/reserve.adoc[`reserve`] 
| 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 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.
| xref:bsl/deque-0c/resize-04.adoc[`resize`] 
| `resize` overloads
| xref:bsl/deque-0c/shrink_to_fit.adoc[`shrink_to_fit`] 
| 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 that this method has no effect on the memory used by individual elements of the (template parameter) `VALUE_TYPE`.
| xref:bsl/Deque_Base/size.adoc[`size`] 
| Return the number of elements contained by this deque.
| xref:bsl/deque-0c/swap.adoc[`swap`] 
| 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 `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 `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 that this method`s support for swapping objects created with different allocators when `ALLOCATOR` does not have the `propagate_on_container_swap` trait is a departure from the C++ Standard.
|===


== Protected Data Members

[cols="1,4"]
|===
| Name| Description
| xref:bsl/Deque_Base/d_blocksLength.adoc[`d_blocksLength`] 
| Length of the `d_blocks_p` array.
| xref:bsl/Deque_Base/d_blocks_p.adoc[`d_blocks_p`] 
| Array of pointers to blocks (owned).
| xref:bsl/Deque_Base/d_finish.adoc[`d_finish`] 
| The `d_finish` data member.
| xref:bsl/Deque_Base/d_start.adoc[`d_start`] 
| The `d_start` data member.
|===


== Deduction Guides

[cols="1,4"]
|===
| Name| Description
| xref:bsl/deque-017.adoc[`deque<VALUE>`] 
| Deduce the template parameter `VALUE` from the `value_type` of the iterators supplied to the constructor of `deque`.
| xref:bsl/deque-01a.adoc[`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>`.
| xref:bsl/deque-05f.adoc[`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 is convertible to `bsl::allocator<VALUE>`.
| xref:bsl/deque-04.adoc[`deque<VALUE>`] 
| 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>`.
| xref:bsl/deque-00.adoc[`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 meets the requirements of a standard allocator.
| xref:bsl/deque-05e.adoc[`deque<ranges::range_value_t<t_RANGE>, t_ALLOCATOR>`] 
| Deduce the template parameters `VALUE_TYPE` and `ALLOCATOR` from the parameters supplied to the constructor of `deque`.
|===


== Friends

[cols="1,4"]
|===
| Name| Description
| `xref:bsl/Deque_Guard.adoc[bsl::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.
| `xref:bsl/Deque_BlockProctor.adoc[bsl::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.
| `xref:bsl/Deque_BlockCreator.adoc[bsl::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).
|===

== Non-Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:bsl/erase-082.adoc[`erase`]
| Erase all the elements in the specified deque `deq` that compare equal to the specified `value`. Return the number of elements erased.
| xref:bsl/erase_if-0b.adoc[`erase_if`]
| Erase all the elements in the specified deque `deq` that satisfy the specified predicate `predicate`. Return the number of elements erased.
| xref:bsl/operator_3way-07cc.adoc[`operator<=>`]
| 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.
| xref:bsl/operator_eq-0ce.adoc[`operator==`]
| 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`}).
| xref:bsl/swap-096.adoc[`swap`]
| 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 `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 `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 that this function`s support for swapping objects created with different allocators when `ALLOCATOR` does not have the `propagate_on_container_swap` trait is a departure from the C++ Standard.
|===


[.small]#Created with https://www.mrdocs.com[MrDocs]#