22 Containers library [containers]

22.3 Sequence containers [sequences]

22.3.8 Class template deque [deque]

22.3.8.1 Overview [deque.overview]

A deque is a sequence container that supports random access iterators ([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, of a reversible container (given in tables in [container.requirements]), of a sequence container, including the optional sequence container requirements ([sequence.reqmts]), and of an allocator-aware container (Table 76).

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.

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
    deque() : deque(Allocator()) { }
    explicit deque(const Allocator&);
    explicit deque(size_type n, const Allocator& = Allocator());
    deque(size_type n, const T& value, const Allocator& = Allocator());
    template<class InputIterator>
      deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
    deque(const deque& x);
    deque(deque&&);
    deque(const deque&, const Allocator&);
    deque(deque&&, const Allocator&);
    deque(initializer_list<T>, const Allocator& = Allocator());

    ~deque();
    deque& operator=(const deque& x);
    deque& operator=(deque&& x)
      noexcept(allocator_traits<Allocator>::is_always_equal::value);
    deque& operator=(initializer_list<T>);
    template<class InputIterator>
      void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const T& t);
    void assign(initializer_list<T>);
    allocator_type get_allocator() const noexcept;

    // iterators
    iterator               begin() noexcept;
    const_iterator         begin() const noexcept;
    iterator               end() noexcept;
    const_iterator         end() const noexcept;
    reverse_iterator       rbegin() noexcept;
    const_reverse_iterator rbegin() const noexcept;
    reverse_iterator       rend() noexcept;
    const_reverse_iterator rend() const noexcept;

    const_iterator         cbegin() const noexcept;
    const_iterator         cend() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    const_reverse_iterator crend() const noexcept;

    // [deque.capacity], capacity
    [[nodiscard]] bool empty() const noexcept;
    size_type size() const noexcept;
    size_type max_size() const noexcept;
    void      resize(size_type sz);
    void      resize(size_type sz, const T& c);
    void      shrink_to_fit();

    // element access
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference       at(size_type n);
    const_reference at(size_type n) const;
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;

    // [deque.modifiers], modifiers
    template<class... Args> reference emplace_front(Args&&... args);
    template<class... Args> reference emplace_back(Args&&... args);
    template<class... Args> iterator emplace(const_iterator position, Args&&... args);

    void push_front(const T& x);
    void push_front(T&& x);
    void push_back(const T& x);
    void push_back(T&& x);

    iterator insert(const_iterator position, const T& x);
    iterator insert(const_iterator position, T&& x);
    iterator insert(const_iterator position, size_type n, const T& x);
    template<class InputIterator>
      iterator insert(const_iterator position, InputIterator first, InputIterator last);
    iterator insert(const_iterator position, initializer_list<T>);

    void pop_front();
    void pop_back();

    iterator erase(const_iterator position);
    iterator erase(const_iterator first, const_iterator last);
    void     swap(deque&)
      noexcept(allocator_traits<Allocator>::is_always_equal::value);
    void     clear() noexcept;
  };

  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
    deque(InputIterator, InputIterator, Allocator = Allocator())
      -> deque<iter-value-type<InputIterator>, Allocator>;

  // swap
  template<class T, class Allocator>
    void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
      noexcept(noexcept(x.swap(y)));
}

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

🔗

explicit deque(const Allocator&);

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

Complexity: Constant.

🔗

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

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

Preconditions: T is Cpp17DefaultInsertable into *this.

Complexity: Linear in n.

🔗

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

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

Preconditions: T is Cpp17CopyInsertable into *this.

Complexity: Linear in n.

🔗

template<class InputIterator>
  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).

22.3.8.3 Capacity [deque.capacity]

🔗

void resize(size_type sz);

Preconditions: T is Cpp17MoveInsertable and Cpp17DefaultInsertable into *this.

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

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

🔗

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

Preconditions: T is Cpp17CopyInsertable into *this.

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

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

🔗

void shrink_to_fit();

Preconditions: T is Cpp17MoveInsertable into *this.

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

[ Note

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.

22.3.8.4 Modifiers [deque.modifiers]

🔗

iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template<class InputIterator>
  iterator insert(const_iterator position,
                  InputIterator first, InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);

template<class... Args> reference emplace_front(Args&&... args);
template<class... Args> reference emplace_back(Args&&... args);
template<class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_front(const T& x);
void push_front(T&& x);
void push_back(const T& x);
void push_back(T&& x);

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.

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.

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.

🔗

iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void pop_front();
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

pop_front and pop_back are erase operations.

— end note

]

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.

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

22.3.8.5 Erasure [deque.erasure]

🔗

template<class T, class Allocator, class U>
  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>
  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;