26 Containers library [containers]

26.3 Sequence containers [sequences]

26.3.11 Class template vector [vector]

26.3.11.1 Class template vector overview [vector.overview]

A vector is a sequence container that supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.

Storage management is handled automatically, though hints can be given to improve efficiency.

A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in [container.requirements]), of a sequence container, including most of the optional sequence container requirements ([sequence.reqmts]), of an allocator-aware container (Table 81), and, for an element type other than bool, of a contiguous container ([container.requirements.general]).

The exceptions are the push_front, pop_front, and emplace_front member functions, which are not provided.

Descriptions are provided here only for operations on vector 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 vector {
  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>;

    // [vector.cons], construct/copy/destroy
    vector() noexcept(noexcept(Allocator())) : vector(Allocator()) { }
    explicit vector(const Allocator&) noexcept;
    explicit vector(size_type n, const Allocator& = Allocator());
    vector(size_type n, const T& value, const Allocator& = Allocator());
    template <class InputIterator>
      vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
    vector(const vector& x);
    vector(vector&&) noexcept;
    vector(const vector&, const Allocator&);
    vector(vector&&, const Allocator&);
    vector(initializer_list<T>, const Allocator& = Allocator());
    ~vector();
    vector& operator=(const vector& x);
    vector& operator=(vector&& x)
      noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
               allocator_traits<Allocator>::is_always_equal::value);
    vector& operator=(initializer_list<T>);
    template <class InputIterator>
      void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const T& u);
    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;

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

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

    // [vector.data], data access
    T*       data() noexcept;
    const T* data() const noexcept;

    // [vector.modifiers], modifiers
    template <class... Args> reference emplace_back(Args&&... args);
    void push_back(const T& x);
    void push_back(T&& x);
    void pop_back();

    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
    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> il);
    iterator erase(const_iterator position);
    iterator erase(const_iterator first, const_iterator last);
    void     swap(vector&)
      noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
               allocator_traits<Allocator>::is_always_equal::value);
    void     clear() noexcept;
  };

  template<class InputIterator,
           class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
    vector(InputIterator, InputIterator, Allocator = Allocator())
      -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>;

  template <class T, class Allocator>
    bool operator==(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator< (const vector<T, Allocator>& x, const vector<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator!=(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator> (const vector<T, Allocator>& x, const vector<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator>=(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator<=(const vector<T, Allocator>& x, const vector<T, Allocator>& y);

  // [vector.special], specialized algorithms
  template <class T, class Allocator>
    void swap(vector<T, Allocator>& x, vector<T, Allocator>& y)
      noexcept(noexcept(x.swap(y)));
}

An incomplete type T may be used when instantiating vector if the allocator satisfies the allocator completeness requirements ([allocator.requirements.completeness]).

T shall be complete before any member of the resulting specialization of vector is referenced.

26.3.11.2 vector constructors, copy, and assignment [vector.cons]

explicit vector(const Allocator&);

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

Complexity: Constant.

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

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

Requires: T shall be DefaultInsertable into *this.

Complexity: Linear in n.

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

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

Requires: T shall be CopyInsertable into *this.

Complexity: Linear in n.

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

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

Complexity: Makes only N calls to the copy constructor of T (where N is the distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories.

It makes order N calls to the copy constructor of T and order logN reallocations if they are just input iterators.

26.3.11.3 vector capacity [vector.capacity]

size_type capacity() const noexcept;

Returns: The total number of elements that the vector can hold without requiring reallocation.

void reserve(size_type n);

Requires: T shall be MoveInsertable into *this.

Effects: A directive that informs a vector of a planned change in size, so that it can manage the storage allocation accordingly.

After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise.

Reallocation happens at this point if and only if the current capacity is less than the argument of reserve().

If an exception is thrown other than by the move constructor of a non-CopyInsertable type, there are no effects.

Complexity: It does not change the size of the sequence and takes at most linear time in the size of the sequence.

Throws: length_error if n > max_size().260

Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity().

void shrink_to_fit();

Requires: T shall be MoveInsertable into *this.

Effects: shrink_to_fit is a non-binding request to reduce capacity() to size().

[ Note

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

— end note

]

It does not increase capacity(), but may reduce capacity() by causing reallocation.

If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.

Complexity: Linear in the size of the sequence.

Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence as well as the past-the-end iterator.

If no reallocation happens, they remain valid.

void swap(vector& x)
  noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
           allocator_traits<Allocator>::is_always_equal::value);

Effects: Exchanges the contents and capacity() of *this with that of x.

Complexity: Constant time.

void resize(size_type sz);

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

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

Requires: T shall be MoveInsertable and DefaultInsertable into *this.

Remarks: If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.

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

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

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

Requires: T shall be CopyInsertable into *this.

Remarks: If an exception is thrown there are no effects.

260)

reserve() uses Allocator::allocate() which may throw an appropriate exception.

26.3.11.4 vector data [vector.data]

T*         data() noexcept;
const T*   data() const noexcept;

Returns: A pointer such that [data(), data() + size()) is a valid range.

For a non-empty vector, data() == addressof(front()).

Complexity: Constant time.

26.3.11.5 vector modifiers [vector.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_back(Args&&... args);
template <class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_back(const T& x);
void push_back(T&& x);

Remarks: Causes reallocation if the new size is greater than the old capacity.

Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

If no reallocation happens, all the iterators and references before the insertion point remain valid.

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

If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible_v<T> is true, there are no effects.

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

Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

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

Effects: Invalidates iterators and references at or after the point of the erase.

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

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

26.3.11.6 vector specialized algorithms [vector.special]

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

Effects: As if by x.swap(y).