23 Containers library [containers]

23.3 Sequence containers [sequences]

23.3.6 Class template vector [vector]

23.3.6.1 Class template vector overview [vector.overview]

A vector is a sequence container that supports random access iterators. In addition, it 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. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

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]), and of an allocator-aware container (Table [tab:containers.allocatoraware]). 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:
    typedef value_type&                           reference;
    typedef const value_type&                     const_reference;
    typedef implementation-defined                iterator;       // see [container.requirements]
    typedef implementation-defined                const_iterator; // see [container.requirements]
    typedef implementation-defined                size_type;      // see [container.requirements]
    typedef implementation-defined                difference_type;// see [container.requirements]
    typedef T                                     value_type;
    typedef Allocator                             allocator_type;
    typedef typename allocator_traits<Allocator>::pointer           pointer;
    typedef typename allocator_traits<Allocator>::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    // [vector.cons], construct/copy/destroy:
    explicit vector(const Allocator& = Allocator());
    explicit vector(size_type n);
    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&&);
    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);
    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:
    size_type size() const noexcept;
    size_type max_size() const noexcept;
    void      resize(size_type sz);
    void      resize(size_type sz, const T& c);
    size_type capacity() const noexcept;
    bool      empty() const noexcept;
    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> void 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&);
    void     clear() noexcept;
  };

  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);
}

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

explicit vector(const Allocator& = Allocator());

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

Complexity: Constant.

explicit vector(size_type n);

Effects: Constructs a vector with n value-initialized elements.

Requires: T shall be DefaultConstructible.

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 log(N) reallocations if they are just input iterators.

template <class InputIterator> void assign(InputIterator first, InputIterator last);

Effects:

erase(begin(), end());
insert(begin(), first, last);

void assign(size_type n, const T& t);

Effects:

erase(begin(), end());
insert(begin(), n, t);

23.3.6.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);

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().267

Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes 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();

Remarks: 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 ]

void swap(vector& x);

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

Complexity: Constant time.

void resize(size_type sz);

Effects: If sz <= size(), equivalent to erase(begin() + sz, end());. If size() < sz, appends sz - size() value-initialized elements to the sequence.

Requires: T shall be CopyInsertable into *this.

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

Effects:

if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size())
  erase(begin()+sz, end());
else
  ;                 // do nothing

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

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

23.3.6.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() == &front().

Complexity: Constant time.

23.3.6.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> void 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. 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 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);

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 move 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 copy constructor, move constructor, assignment operator, or move assignment operator of T.

23.3.6.6 vector specialized algorithms [vector.special]

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

Effects:

x.swap(y);