23 Containers library [containers]

23.3 Sequence containers [sequences]

23.3.5 Class template deque [deque]

23.3.5.1 Overview [deque.overview]

A deque is a sequence container that supports random access iterators .

In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time.

That is, a deque is especially optimized for pushing and popping elements at the beginning and end.

Storage management is handled automatically.

A deque meets all of the requirements of a container ([container.reqmts]), of a reversible container ([container.rev.reqmts]), of an allocator-aware container ([container.alloc.reqmts]), and of a sequence container, including the optional sequence container requirements ([sequence.reqmts]).

Descriptions are provided here only for operations on deque that are not described in one of these tables or for operations where there is additional semantic information.

The types iterator and const_iterator meet the constexpr iterator requirements ([iterator.requirements.general]).

namespace std { template<class T, class Allocator = allocator<T>> class deque { public: // types using value_type = T; using allocator_type = Allocator; using pointer = typename allocator_traits<Allocator>::pointer; using const_pointer = typename allocator_traits<Allocator>::const_pointer; using reference = value_type&; using const_reference = const value_type&; using size_type = implementation-defined; // see [container.requirements] using difference_type = implementation-defined; // see [container.requirements] using iterator = implementation-defined; // see [container.requirements] using const_iterator = implementation-defined; // see [container.requirements] using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; // [deque.cons], construct/copy/destroy constexpr deque() : deque(Allocator()) { } constexpr explicit deque(const Allocator&); constexpr explicit deque(size_type n, const Allocator& = Allocator()); constexpr deque(size_type n, const T& value, const Allocator& = Allocator()); template<class InputIterator> constexpr deque(InputIterator first, InputIterator last, const Allocator& = Allocator()); template<container-compatible-range<T> R> constexpr deque(from_range_t, R&& rg, const Allocator& = Allocator()); constexpr deque(const deque& x); constexpr deque(deque&&); constexpr deque(const deque&, const type_identity_t<Allocator>&); constexpr deque(deque&&, const type_identity_t<Allocator>&); constexpr deque(initializer_list<T>, const Allocator& = Allocator()); constexpr ~deque(); constexpr deque& operator=(const deque& x); constexpr deque& operator=(deque&& x) noexcept(allocator_traits<Allocator>::is_always_equal::value); constexpr deque& operator=(initializer_list<T>); template<class InputIterator> constexpr void assign(InputIterator first, InputIterator last); template<container-compatible-range<T> R> constexpr void assign_range(R&& rg); constexpr void assign(size_type n, const T& t); constexpr void assign(initializer_list<T>); constexpr allocator_type get_allocator() const noexcept; // iterators constexpr iterator begin() noexcept; constexpr const_iterator begin() const noexcept; constexpr iterator end() noexcept; constexpr const_iterator end() const noexcept; constexpr reverse_iterator rbegin() noexcept; constexpr const_reverse_iterator rbegin() const noexcept; constexpr reverse_iterator rend() noexcept; constexpr const_reverse_iterator rend() const noexcept; constexpr const_iterator cbegin() const noexcept; constexpr const_iterator cend() const noexcept; constexpr const_reverse_iterator crbegin() const noexcept; constexpr const_reverse_iterator crend() const noexcept; // [deque.capacity], capacity constexpr bool empty() const noexcept; constexpr size_type size() const noexcept; constexpr size_type max_size() const noexcept; constexpr void resize(size_type sz); constexpr void resize(size_type sz, const T& c); constexpr void shrink_to_fit(); // element access constexpr reference operator[](size_type n); constexpr const_reference operator[](size_type n) const; constexpr reference at(size_type n); constexpr const_reference at(size_type n) const; constexpr reference front(); constexpr const_reference front() const; constexpr reference back(); constexpr const_reference back() const; // [deque.modifiers], modifiers template<class... Args> constexpr reference emplace_front(Args&&... args); template<class... Args> constexpr reference emplace_back(Args&&... args); template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args); constexpr void push_front(const T& x); constexpr void push_front(T&& x); template<container-compatible-range<T> R> constexpr void prepend_range(R&& rg); constexpr void push_back(const T& x); constexpr void push_back(T&& x); template<container-compatible-range<T> R> constexpr void append_range(R&& rg); constexpr iterator insert(const_iterator position, const T& x); constexpr iterator insert(const_iterator position, T&& x); constexpr iterator insert(const_iterator position, size_type n, const T& x); template<class InputIterator> constexpr iterator insert(const_iterator position, InputIterator first, InputIterator last); template<container-compatible-range<T> R> constexpr iterator insert_range(const_iterator position, R&& rg); constexpr iterator insert(const_iterator position, initializer_list<T>); constexpr void pop_front(); constexpr void pop_back(); constexpr iterator erase(const_iterator position); constexpr iterator erase(const_iterator first, const_iterator last); constexpr void swap(deque&) noexcept(allocator_traits<Allocator>::is_always_equal::value); constexpr void clear() noexcept; }; template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>> deque(InputIterator, InputIterator, Allocator = Allocator()) -> deque<iter-value-type<InputIterator>, Allocator>; template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> deque(from_range_t, R&&, Allocator = Allocator()) -> deque<ranges::range_value_t<R>, Allocator>; }

23.3.5.2 Constructors, copy, and assignment [deque.cons]

🔗

constexpr explicit deque(const Allocator&);

Effects: Constructs an empty deque, using the specified allocator.

Complexity: Constant.

🔗

constexpr explicit deque(size_type n, const Allocator& = Allocator());

Preconditions: T is Cpp17DefaultInsertable into deque.

Effects: Constructs a deque with n default-inserted elements using the specified allocator.

Complexity: Linear in n.

🔗

constexpr deque(size_type n, const T& value, const Allocator& = Allocator());

Preconditions: T is Cpp17CopyInsertable into deque.

Effects: Constructs a deque with n copies of value, using the specified allocator.

Complexity: Linear in n.

🔗

template<class InputIterator>
  constexpr deque(InputIterator first, InputIterator last, const Allocator& = Allocator());

Effects: Constructs a deque equal to the range [first, last), using the specified allocator.

Complexity: Linear in distance(first, last).

🔗

template<container-compatible-range<T> R>
  constexpr deque(from_range_t, R&& rg, const Allocator& = Allocator());

Effects: Constructs a deque with the elements of the range rg, using the specified allocator.

Complexity: Linear in ranges::distance(rg).

23.3.5.3 Capacity [deque.capacity]

🔗

constexpr void resize(size_type sz);

Preconditions: T is Cpp17MoveInsertable and Cpp17DefaultInsertable into deque.

Effects: If sz < size(), erases the last size() - sz elements from the sequence.

Otherwise, appends sz - size() default-inserted elements to the sequence.

🔗

constexpr void resize(size_type sz, const T& c);

Preconditions: T is Cpp17CopyInsertable into deque.

Effects: If sz < size(), erases the last size() - sz elements from the sequence.

Otherwise, appends sz - size() copies of c to the sequence.

🔗

constexpr void shrink_to_fit();

Preconditions: T is Cpp17MoveInsertable into deque.

Effects: shrink_to_fit is a non-binding request to reduce memory use but does not change the size of the sequence.

[Note 1:

The request is non-binding to allow latitude for implementation-specific optimizations.

— end note]

If the size is equal to the old capacity, or if an exception is thrown other than by the move constructor of a non-Cpp17CopyInsertable T, then there are no effects.

Complexity: If the size is not equal to the old capacity, linear in the size of the sequence; otherwise constant.

Remarks: If the size is not equal to the old capacity, then invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator.

23.3.5.4 Modifiers [deque.modifiers]

🔗

constexpr iterator insert(const_iterator position, const T& x);
constexpr iterator insert(const_iterator position, T&& x);
constexpr iterator insert(const_iterator position, size_type n, const T& x);
template<class InputIterator>
  constexpr iterator insert(const_iterator position,
                            InputIterator first, InputIterator last);
template<container-compatible-range<T> R>
  constexpr iterator insert_range(const_iterator position, R&& rg);
constexpr iterator insert(const_iterator position, initializer_list<T>);

template<class... Args> constexpr reference emplace_front(Args&&... args);
template<class... Args> constexpr reference emplace_back(Args&&... args);
template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
constexpr void push_front(const T& x);
constexpr void push_front(T&& x);
template<container-compatible-range<T> R>
  constexpr void prepend_range(R&& rg);
constexpr void push_back(const T& x);
constexpr void push_back(T&& x);
template<container-compatible-range<T> R>
  constexpr void append_range(R&& rg);

Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque.

An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

Complexity: The complexity is linear in the number of elements inserted plus the lesser of the distances to the beginning and end of the deque.

Inserting a single element at either the beginning or end of a deque always takes constant time and causes a single call to a constructor of T.

Remarks: If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T, there are no effects.

If an exception is thrown while inserting a single element at either end, there are no effects.

Otherwise, if an exception is thrown by the move constructor of a non-Cpp17CopyInsertable T, the effects are unspecified.

🔗

constexpr iterator erase(const_iterator position);
constexpr iterator erase(const_iterator first, const_iterator last);
constexpr void pop_front();
constexpr void pop_back();

Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements.

An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements.

An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.

[Note 1:

pop_front and pop_back are erase operations.

— end note]

Throws: Nothing unless an exception is thrown by the assignment operator of T.

Complexity: The number of calls to the destructor of T is the same as the number of elements erased, but the number of calls to the assignment operator of T is no more than the lesser of the number of elements before the erased elements and the number of elements after the erased elements.

23.3.5.5 Erasure [deque.erasure]

🔗

template<class T, class Allocator, class U = T>
  constexpr typename deque<T, Allocator>::size_type
    erase(deque<T, Allocator>& c, const U& value);

Effects: Equivalent to: auto it = remove(c.begin(), c.end(), value); auto r = distance(it, c.end()); c.erase(it, c.end()); return r;

🔗

template<class T, class Allocator, class Predicate>
  constexpr typename deque<T, Allocator>::size_type
    erase_if(deque<T, Allocator>& c, Predicate pred);

Effects: Equivalent to: auto it = remove_if(c.begin(), c.end(), pred); auto r = distance(it, c.end()); c.erase(it, c.end()); return r;