[vector] (original) (raw)
22 Containers library [containers]
22.3 Sequence containers [sequences]
22.3.11 Class template vector [vector]
22.3.11.1 Overview [vector.overview]
Avectoris 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 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 thepush_front, pop_front, and emplace_front member functions, which are not provided.
Descriptions are provided here only for operations on vectorthat 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> class vector { public:
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;
using difference_type = implementation-defined;
using iterator = implementation-defined;
using const_iterator = implementation-defined;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
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;
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;
[[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();
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;
constexpr T* data() noexcept;
constexpr const T* data() const noexcept;
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>> vector(InputIterator, InputIterator, Allocator = Allocator()) -> vector<iter-value-type, Allocator>;
template<class T, class Allocator> constexpr void swap(vector<T, Allocator>& x, vector<T, Allocator>& y) noexcept(noexcept(x.swap(y))); }
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;
Effects:Constructs an empty vector, using the specified allocator.
constexpr explicit vector(size_type n, const Allocator& = Allocator());
Preconditions: T is Cpp17DefaultInsertable into *this.
Effects:Constructs a vector with ndefault-inserted elements using the specified allocator.
constexpr vector(size_type n, const T& value,const Allocator& = Allocator());
Preconditions: T isCpp17CopyInsertable into *this.
Effects:Constructs a vector with ncopies of value, using the specified allocator.
template<class InputIterator> constexpr 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 Ncalls to the copy constructor ofT(where Nis the distance betweenfirstandlast) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories.
It makes orderNcalls to the copy constructor ofTand orderlogNreallocations if they are just input iterators.
22.3.11.3 Capacity [vector.capacity]
constexpr size_type capacity() const noexcept;
Returns:The total number of elements that the vector can hold without requiring reallocation.
Complexity:Constant time.
constexpr void reserve(size_type n);
Preconditions: T is Cpp17MoveInsertable into *this.
Effects:A directive that informs avectorof a planned change in size, so that it can manage the storage allocation accordingly.
Afterreserve(),capacity()is greater or equal to the argument ofreserveif reallocation happens; and equal to the previous value ofcapacity()otherwise.
Reallocation happens at this point if and only if the current capacity is less than the argument ofreserve().
If an exception is thrown other than by the move constructor of a non-Cpp17CopyInsertable 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().227
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();
Preconditions: T is Cpp17MoveInsertable into *this.
Effects: shrink_to_fit is a non-binding request to reducecapacity() 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.
Complexity:If reallocation happens, 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.
[ 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);
Effects:Exchanges the contents andcapacity()of*thiswith that of x.
Complexity:Constant time.
constexpr void resize(size_type sz);
Preconditions: T isCpp17MoveInsertable 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.
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);
Preconditions: T isCpp17CopyInsertable 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.
Remarks:If an exception is thrown there are no effects.
22.3.11.4 Data [vector.data]
constexpr T* data() noexcept;constexpr 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.
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);
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 ofT or by any InputIterator operation there are no effects.
If an exception is thrown while inserting a single element at the end andT 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.
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();
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 ofT.
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);
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);
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;