Cpp reference std vector

std:: vector

The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements. This means that a pointer to an element of a vector may be passed to any function that expects a pointer to an element of an array.

The storage of the vector is handled automatically, being expanded as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted. The total amount of allocated memory can be queried using capacity() function. Extra memory can be returned to the system via a call to shrink_to_fit() . (since C++11)

Reallocations are usually costly operations in terms of performance. The reserve() function can be used to eliminate reallocations if the number of elements is known beforehand.

The complexity (efficiency) of common operations on vectors is as follows:

• Random access — constant O(1)
• Insertion or removal of elements at the end — amortized constant O(1)
• Insertion or removal of elements — linear in the distance to the end of the vector O(n)

std::vector (for T other than bool ) meets the requirements of Container , AllocatorAwareContainer (since C++11) , SequenceContainer , ContiguousContainer (since C++17) and ReversibleContainer .

Member functions of std::vector are constexpr : it is possible to create and use std::vector objects in the evaluation of a constant expression.

However, std::vector objects generally cannot be constexpr , because any dynamically allocated storage must be released in the same evaluation of constant expression.

Contents

[edit] Template parameters

The requirements that are imposed on the elements depend on the actual operations performed on the container. Generally, it is required that element type meets the requirements of Erasable , but many member functions impose stricter requirements. This container (but not its members) can be instantiated with an incomplete element type if the allocator satisfies the allocator completeness requirements.

[edit] Specializations

The standard library provides a specialization of std::vector for the type bool , which may be optimized for space efficiency.

[edit] Iterator invalidation

Operations	Invalidated
All read only operations	Never
swap , std::swap	end()
clear , assign	Always
reserve , shrink_to_fit	If the vector changed capacity, all of them. If not, none.
erase	Erased elements and all elements after them (including end() )
push_back , emplace_back	If the vector changed capacity, all of them. If not, only end() .
insert , emplace	If the vector changed capacity, all of them. If not, only those at or after the insertion point (including end() ).
resize	If the vector changed capacity, all of them. If not, only end() and any elements erased.
pop_back	The element erased and end() .

Источник

std:: vector

Vectors are sequence containers representing arrays that can change in size.

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity (see push_back).

Therefore, compared to arrays, vectors consume more memory in exchange for the ability to manage storage and grow dynamically in an efficient way.

Compared to the other dynamic sequence containers (deques, lists and forward_lists), vectors are very efficient accessing its elements (just like arrays) and relatively efficient adding or removing elements from its end. For operations that involve inserting or removing elements at positions other than the end, they perform worse than the others, and have less consistent iterators and references than lists and forward_lists.

Container properties

Sequence Elements in sequence containers are ordered in a strict linear sequence. Individual elements are accessed by their position in this sequence. Dynamic array Allows direct access to any element in the sequence, even through pointer arithmetics, and provides relatively fast addition/removal of elements at the end of the sequence. Allocator-aware The container uses an allocator object to dynamically handle its storage needs.

Template parameters

T Type of the elements.
Only if T is guaranteed to not throw while moving, implementations can optimize to move elements instead of copying them during reallocations.
Aliased as member type vector::value_type. Alloc Type of the allocator object used to define the storage allocation model. By default, the allocator class template is used, which defines the simplest memory allocation model and is value-independent.
Aliased as member type vector::allocator_type.

Member types

member type	definition	notes
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)	defaults to: allocator
reference	allocator_type::reference	for the default allocator: value_type&
const_reference	allocator_type::const_reference	for the default allocator: const value_type&
pointer	allocator_type::pointer	for the default allocator: value_type*
const_pointer	allocator_type::const_pointer	for the default allocator: const value_type*
iterator	a random access iterator to value_type	convertible to const_iterator
const_iterator	a random access iterator to const value_type
reverse_iterator	reverse_iterator
const_reverse_iterator	reverse_iterator
difference_type	a signed integral type, identical to: iterator_traits::difference_type	usually the same as ptrdiff_t
size_type	an unsigned integral type that can represent any non-negative value of difference_type	usually the same as size_t

member type	definition	notes
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)	defaults to: allocator
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits::pointer	for the default allocator: value_type*
const_pointer	allocator_traits::const_pointer	for the default allocator: const value_type*
iterator	a random access iterator to value_type	convertible to const_iterator
const_iterator	a random access iterator to const value_type
reverse_iterator	reverse_iterator
const_reverse_iterator	reverse_iterator
difference_type	a signed integral type, identical to: iterator_traits::difference_type	usually the same as ptrdiff_t
size_type	an unsigned integral type that can represent any non-negative value of difference_type	usually the same as size_t

Member functions

(constructor) Construct vector (public member function) (destructor) Vector destructor (public member function) operator= Assign content (public member function)
Iterators:
begin Return iterator to beginning (public member function) end Return iterator to end (public member function) rbegin Return reverse iterator to reverse beginning (public member function) rend Return reverse iterator to reverse end (public member function) cbegin Return const_iterator to beginning (public member function) cend Return const_iterator to end (public member function) crbegin Return const_reverse_iterator to reverse beginning (public member function) crend Return const_reverse_iterator to reverse end (public member function)
Capacity:
size Return size (public member function) max_size Return maximum size (public member function) resize Change size (public member function) capacity Return size of allocated storage capacity (public member function) empty Test whether vector is empty (public member function) reserve Request a change in capacity (public member function) shrink_to_fit Shrink to fit (public member function)
Element access:
operator[] Access element (public member function) at Access element (public member function) front Access first element (public member function) back Access last element (public member function) data Access data (public member function)
Modifiers:
assign Assign vector content (public member function) push_back Add element at the end (public member function) pop_back Delete last element (public member function) insert Insert elements (public member function) erase Erase elements (public member function) swap Swap content (public member function) clear Clear content (public member function) emplace Construct and insert element (public member function) emplace_back Construct and insert element at the end (public member function)
Allocator:
get_allocator Get allocator (public member function)

Non-member function overloads

relational operators Relational operators for vector (function template) swap Exchange contents of vectors (function template)

Источник

vector

The vector container, declared in , allows for keeping a variable sequence of elements of arbitrary data type. These are its essential properties:

std::vectorint> v1; // a vector of integers std::vectorint*> v2; // a vector of pointers to integer(s) std::vectorstd::string> v3; // a vector of strings std::vectorstd::vectorint> > v3; // a vector of vectors of int's

• Vectors have a variable number of elements, which can be inserted, removed and accessed in runtime:

using namespace std; vectorint> vec = {1,2,3}; // you can initialize vectors with an initializer list since C++11 cout  size()  ; // will print 3 vec.push_back(5); // insert 5 at the end of the vector cout  [3]  ; // will print 5 vec[1] = 10; // change the second element to 10 cout  front()  ; // first element, will print 1 cout  size()  ; // will print 4

• Elements in a vector are contiguous like in an array, so it provides fast read/write operations on any element. Internally, these are kept in a dynamically allocated array of larger (or equal) size, so that it can grow larger. If this array is full before inserting another element, the vector will relocate every single element currently in it into a larger array. This means two things: there is no theoretical limit on the number of elements of a vector, but inserting many elements at a time will force a capacity increase of the vector, which can become a heavy operation. You can use the capacity() member function in order to find to what size can the vector grow to without an expansion.

vectorint> vec = {0, 3, 4, 6}; cout  capacity()  ; // will print a number greater or equal to 4 vec.reserve(10); // you can also force an expansion of the vector cout  capacity()  ; // will print 10 vec.shrink_to_fit(); // since C++11, you can contract the vector to the minimum capacity needed cout  capacity()  ; // will print 4

• Access to an element out of the vector's range (using a bad index for example) will not necessarily cause an error with the array suffix operator[]. On the other hand, the at() function includes bounds checking.

vectorfloat> vec (3, 2.0f); // initialize a vector with 3 elements set to 2.0f float myfloat1 = vec[2]; // OK float myfloat2 = vec[3]; // undefined behavior! vec[6] = myfloat1; // undefined behavior! float myfloat3 = vec.at(1); // OK vec.at(6) = 1.0f; // will throw std::out_of_range exception!

• Like any other container, they can be iterated using a standard iterator or a for-each statement:

vectorint> vec = {5, 3, 1}; for (auto it = begin(vec) ; it != end(vec) ; it++) { cout  <*it  ; // print each element } for (int& e : vec) { e++; // increment each element by one }

Vectors are preferred when keeping a sequence of elements for random access due to its O(1) complexity. Once created, it can be accessed in a similar fashion to an array. If the needed capacity for the vector is unknown, it can still be used without major issues, thanks to the various element insertion and removal functions available.

Источник