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() . |
11.16 — An introduction to std::vector
In the previous lesson, we introduced std::array , which provides the functionality of C++’s built-in fixed arrays in a safer and more usable form.
Analogously, the C++ standard library provides functionality that makes working with dynamic arrays safer and easier. This functionality is named std::vector .
Unlike std::array , which closely follows the basic functionality of fixed arrays, std::vector comes with some additional tricks up its sleeves. These help make std::vector one of the most useful and versatile tools to have in your C++ toolkit.
An introduction to std::vector
Introduced in C++03, std::vector provides dynamic array functionality that handles its own memory management. This means you can create arrays that have their length set at run-time, without having to explicitly allocate and deallocate memory using new and delete . std::vector lives in the header.
Declaring a std::vector is simple:
#include // no need to specify length at the declaration std::vector v; std::vector v2 = < 9, 7, 5, 3, 1 >; // use initializer list to initialize vector (before C++11) std::vector v3 < 9, 7, 5, 3, 1 >; // use uniform initialization to initialize vector // as with std::array, the type can be omitted since C++17 std::vector v4 < 9, 7, 5, 3, 1 >; // deduced to std::vector
Note that in both the uninitialized and initialized case, you do not need to include the array length at compile time. This is because std::vector will dynamically allocate memory for its contents as requested.
Just like std::array , accessing array elements can be done via the [] operator (which does no bounds checking) or the at() function (which does bounds checking):
v[6] = 2; // no bounds checking v.at(7) = 3; // does bounds checkingIn either case, if you request an element that is off the end of the array, the vector will not automatically resize.
As of C++11, you can also assign values to a std::vector using an initializer-list:
v = < 0, 1, 2, 3, 4 >; // okay, vector length is now 5 v = < 9, 8, 7 >; // okay, vector length is now 3In this case, the vector will self-resize to match the number of elements provided.
Self-cleanup prevents memory leaks
When a vector variable goes out of scope, it automatically deallocates the memory it controls (if necessary). This is not only handy (as you don’t have to do it yourself), it also helps prevent memory leaks. Consider the following snippet:
void doSomething(bool earlyExit) < int* array< new int[5] < 9, 7, 5, 3, 1 >>; // allocated memory using new if (earlyExit) return; // exits the function without deallocating the memory allocated above // do stuff here delete[] array; // never called >If earlyExit is set to true, array will never be deallocated, and the memory will be leaked.
However, if array is a std::vector , this won’t happen, because the memory will be deallocated as soon as array goes out of scope (regardless of whether the function exits early or not). This makes std::vector much safer to use than doing your own memory allocation.
Vectors remember their length
Unlike built-in dynamic arrays, which don’t know the length of the array they are pointing to, std::vector keeps track of its length. We can ask for the vector’s length via the size() function:
#include #include void printLength(const std::vector& v) < std::cout int main() < std::vector v< 9, 7, 5, 3, 1 >; printLength(v); std::vector empty <>; printLength(empty); return 0; >The length is: 5 The length is: 0
Just like with std::array , size() returns a value of nested type size_type (full type in the above example would be std::vector::size_type ), which is an unsigned integer.
Resizing a built-in dynamically allocated array is complicated. Resizing a std::vector is as simple as calling the resize() function:
#include #include int main() < std::vector v< 0, 1, 2 >; v.resize(5); // set size to 5 std::cout
The length is: 5 0 1 2 0 0
There are two things to note here. First, when we resized the vector, the existing element values were preserved! Second, new elements are initialized to the default value for the type (which is 0 for integers).
Vectors may be resized to be smaller:
#include #include int main() < std::vector v< 0, 1, 2, 3, 4 >; v.resize(3); // set length to 3 std::cout
Initializing a vector to a specific size
Resizing a vector is computationally expensive, so you should strive to minimize the number of times you do so. If you need a vector with a specific number of elements, you can use parenthesis initialization to do so:
#include #include int main() < // Using direct initialization, we can create a vector with 5 elements, // each element has value 0. If we use brace initialization, the vector would // have 1 element with value 5. std::vectorv(5); std::cout
The length is: 5 0 0 0 0 0
When initializing a vector:
- Use brace initialization when you want to initialize the vector with specific values.
- Use parenthesis initialization when you want to initialize the vector to a specific size (the values will be value initialized).
std::vector a < 1, 2, 3 >; // allocate 3 elements with values 1, 2, and 3 std::vector b < 3 >; // allocate 1 element with value 3 std::vector c ( 3 ); // allocate 3 elements with values 0, 0, and 0 std::vector d ( 3, 4 ); // allocate 3 elements with values 4, 4, and 4We’ll talk about why direct and brace-initialization are treated differently in lesson 16.7 -- std::initializer_list. As a rule of thumb, if a type is some kind of list, and you don’t want to initialize the object with a list of values, use direct initialization.
std::vector has another cool trick up its sleeves. There is a special implementation for std::vector of type bool that will compact 8 booleans into a byte! This happens behind the scenes, and doesn’t change how you use the std::vector.
#include #include int main() < std::vectorv< true, false, false, true, true >; std::cout
The length is: 5 1 0 0 1 1
Note that this is an introduction article intended to introduce the basics of std::vector . In lesson 12.3 -- std::vector capacity and stack behavior, we’ll cover some additional capabilities of std::vector , including the difference between a vector’s length and capacity, and take a deeper look into how std::vector handles memory allocation.
Because variables of type std::vector handle their own memory management (which helps prevent memory leaks), remember their length, and can be easily resized, we recommend using std::vector in most cases where dynamic arrays are needed.