22 Containers library [containers]

22.3 Sequence containers [sequences]

22.3.11 Class template vector [vector]

22.3.11.1 Overview [vector.overview]

1
#
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.
2
#
A vector meets 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 76), and, for an element type other than bool, of a contiguous container.
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.
3
#
The types iterator and const_­iterator meet the constexpr iterator requirements ([iterator.requirements.general]).
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
    constexpr vector() noexcept(noexcept(Allocator())) : vector(Allocator()) { }
    constexpr explicit vector(const Allocator&) noexcept;
    constexpr explicit vector(size_type n, const Allocator& = Allocator());
    constexpr vector(size_type n, const T& value, const Allocator& = Allocator());
    template<class InputIterator>
      constexpr vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
    constexpr vector(const vector& x);
    constexpr vector(vector&&) noexcept;
    constexpr vector(const vector&, const Allocator&);
    constexpr vector(vector&&, const Allocator&);
    constexpr vector(initializer_list<T>, const Allocator& = Allocator());
    constexpr ~vector();
    constexpr vector& operator=(const vector& x);
    constexpr vector& operator=(vector&& x)
      noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
               allocator_traits<Allocator>::is_always_equal::value);
    constexpr vector& operator=(initializer_list<T>);
    template<class InputIterator>
      constexpr void assign(InputIterator first, InputIterator last);
    constexpr void assign(size_type n, const T& u);
    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;

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

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

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

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

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

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

  // swap
  template<class T, class Allocator>
    constexpr void swap(vector<T, Allocator>& x, vector<T, Allocator>& y)
      noexcept(noexcept(x.swap(y)));
}
4
#
An incomplete type T may be used when instantiating vector if the allocator meets the allocator completeness requirements.
T shall be complete before any member of the resulting specialization of vector is referenced.

22.3.11.2 Constructors, copy, and assignment [vector.cons]

🔗
constexpr explicit vector(const Allocator&) noexcept;
1
#
Effects: Constructs an empty vector, using the specified allocator.
2
#
Complexity: Constant.
🔗
constexpr explicit vector(size_type n, const Allocator& = Allocator());
3
#
Preconditions: T is Cpp17DefaultInsertable into *this.
4
#
Effects: Constructs a vector with n default-inserted elements using the specified allocator.
5
#
Complexity: Linear in n.
🔗
constexpr vector(size_type n, const T& value, const Allocator& = Allocator());
6
#
Preconditions: T is Cpp17CopyInsertable into *this.
7
#
Effects: Constructs a vector with n copies of value, using the specified allocator.
8
#
Complexity: Linear in n.
🔗
template<class InputIterator> constexpr vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
9
#
Effects: Constructs a vector equal to the range [first, last), using the specified allocator.
10
#
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 reallocations if they are just input iterators.

22.3.11.3 Capacity [vector.capacity]

🔗
constexpr size_type capacity() const noexcept;
1
#
Returns: The total number of elements that the vector can hold without requiring reallocation.
2
#
Complexity: Constant time.
🔗
constexpr void reserve(size_type n);
3
#
Preconditions: T is Cpp17MoveInsertable into *this.
4
#
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-Cpp17CopyInsertable type, there are no effects.
5
#
Complexity: It does not change the size of the sequence and takes at most linear time in the size of the sequence.
6
#
Throws: length_­error if n > max_­size().227
7
#
Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator.
[Note
:
If no reallocation happens, they remain valid.
— end note
]
No reallocation shall take place during insertions that happen after a call to reserve() until an insertion would make the size of the vector greater than the value of capacity().
🔗
constexpr void shrink_to_fit();
8
#
Preconditions: T is Cpp17MoveInsertable into *this.
9
#
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-Cpp17CopyInsertable T there are no effects.
10
#
Complexity: If reallocation happens, linear in the size of the sequence.
11
#
Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence as well as the past-the-end iterator.
[Note
:
If no reallocation happens, they remain valid.
— end note
]
🔗
constexpr void swap(vector& x) noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value || allocator_traits<Allocator>::is_always_equal::value);
12
#
Effects: Exchanges the contents and capacity() of *this with that of x.
13
#
Complexity: Constant time.
🔗
constexpr void resize(size_type sz);
14
#
Preconditions: T is Cpp17MoveInsertable and Cpp17DefaultInsertable into *this.
15
#
Effects: If sz < size(), erases the last size() - sz elements from the sequence.
Otherwise, appends sz - size() default-inserted elements to the sequence.
16
#
Remarks: If an exception is thrown other than by the move constructor of a non-Cpp17CopyInsertable T there are no effects.
🔗
constexpr void resize(size_type sz, const T& c);
17
#
Preconditions: T is Cpp17CopyInsertable into *this.
18
#
Effects: If sz < size(), erases the last size() - sz elements from the sequence.
Otherwise, appends sz - size() copies of c to the sequence.
19
#
Remarks: If an exception is thrown there are no effects.
227)
reserve() uses Allocator​::​allocate() which may throw an appropriate exception.
⮥

22.3.11.4 Data [vector.data]

🔗
constexpr T* data() noexcept; constexpr const T* data() const noexcept;
1
#
Returns: A pointer such that [data(), data() + size()) is a valid range.
For a non-empty vector, data() == addressof(front()).
2
#
Complexity: Constant time.

22.3.11.5 Modifiers [vector.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); constexpr iterator insert(const_iterator position, initializer_list<T>); template<class... Args> constexpr reference emplace_back(Args&&... args); template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args); constexpr void push_back(const T& x); constexpr void push_back(T&& x);
1
#
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, as well as the past-the-end iterator.
If no reallocation happens, then references, pointers, and iterators before the insertion point remain valid but those at or after the insertion point, including the past-the-end iterator, are invalidated.
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 Cpp17CopyInsertable 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-Cpp17CopyInsertable T, the effects are unspecified.
2
#
Complexity: If reallocation happens, linear in the number of elements of the resulting vector; otherwise, linear in the number of elements inserted plus the distance to the end of the vector.
🔗
constexpr iterator erase(const_iterator position); constexpr iterator erase(const_iterator first, const_iterator last); constexpr void pop_back();
3
#
Effects: Invalidates iterators and references at or after the point of the erase.
4
#
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.
5
#
Throws: Nothing unless an exception is thrown by the assignment operator or move assignment operator of T.

22.3.11.6 Erasure [vector.erasure]

🔗
template<class T, class Allocator, class U> constexpr typename vector<T, Allocator>::size_type erase(vector<T, Allocator>& c, const U& value);
1
#
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 vector<T, Allocator>::size_type erase_if(vector<T, Allocator>& c, Predicate pred);
2
#
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;