Dec 24, 2013 (last update: Jul 25, 2014)
std::vectors, not dynamic arrays!
Score: 4.4/5 (67 votes)
Yo.
This forum often sees questions about programs in which programmers would like to store a series of elements at runtime, but don't know how large the series will be ahead of time.
The classic C solution to this problem involves dynamically allocating an array and "resizing" it as needed by allocating a new array and copying elements over from the previous one. However, such strategies can not only be cumbersome for newer programmers to implement but also require manual memory management which can open up risks of memory leaks.
To this end, this article will introduce the Standard Template Library (STL) class template std::vector as a potential solution to the problem of resizable arrays. std::vectors offer member functions for most common tasks that involve array resizing, can serve in many cases as a drop-in replacement for arrays, and a handy size optimization for storing boolean values.
This article may be easier to understand if you (the reader) are familiar with the following:
A misconception that many beginners have is that std::vectors are like n-dimensional vectors from mathematics or physics. While this is an understandable misunderstanding, it's better to think of std::vector as a bit of code (a wrapper) that manages an array that can change its size.
Let's begin with the creation of a vector. Like any element of the standard library, one needs to include a header to use vectors. The header in question is quite intuitively named: it's "vector".
To instantiate a vector, all one needs to do is this:
This creates an empty vector. To have the vector start at a certain size, this will work as well:
Each element in that vector will be initialized to its default value. If the programmer wishes to initialize them all to some value other than the default, then there is yet another option:
The full list of ways to initialize a vector can be found here.
Vectors can be used much like arrays can. They support the [] operator for element access much like arrays do (and their indices are the same, remember that the range of indices is [0,size-1]), and can therefore serve, in many cases, as drop-in replacements for arrays. One notation that doesn't work, however, is this:
Just as a warning.
Vectors offer a member function to get the number of elements they contain, namely std::vector::size. Its return type, size_t, is an unsigned integer that is large enough to represent the size of any object in bytes. On 32-bit systems, it's at least 32 bits large. On 64-bit systems, it's at least 64.
Alternatively, if you simply wish to test to see if the vector is empty, the std::vector::empty function returns a bool that is true if the vector has no elements in it, and false otherwise.
In addition to the [] operator, vectors also provide the std::vector::at member function. It takes the same arguments as the operator and returns a reference just like the operator does. The difference, however, is that it checks to make sure that the provided index is less than the size of the vector. If it's not, it throws an exception, whereas the [] operator could literally do anything. Usually, it will either access memory that the program hasn't reserved, or cause a segmentation fault which will likely crash the program. at() is very slightly slower as a result, but easier to debug if something does go wrong.
For convenience, vectors also provide functions to get the element at index 0 (the front of the vector) and the element at index size-1 (the back of the vector). They're intuitively named.
Adding a new element to the end of a vector is quite easy. Vectors offer the std::vector::push_back function, which takes a single element that gets copied (or moved) onto the back (remember: back = largest index) of the vector, expanding it by one.
.
Similarly, vectors also have a std::vector::pop_back function which takes no arguments and removes the last element of the vector, shrinking it by one. This destroys the removed element, if applicable.
.
Clearing the vector of all its elements is also easy. One call to std::vector::clear removes and destroys all the elements of a vector, setting its size to 0.
To easily resize a vector, one can use std::vector::resize. It takes two arguments, though the second has a default value. The first is the number of elements to resize the vector to. If this is smaller than the current size, then the extra elements at the end (greater indices) get destroyed. The second parameter is what to initialize the new elements to if the first argument is larger than the current size.
If there is ever a need to exchange the contents of vectors, there's another simple function in the form of std::vector::swap. It takes a vector as an argument which is passed by reference, and the vectors have their contents exchanged. The vector passed in shouldn't, therefore, be const.
These are not all the member functions of vectors. There are others that may be of interest some of those require some prerequisite knowledge about iterators. And that... is a topic for another article.
Vectors behave slightly differently when they're storing bools.
Normally, a bool gets stored in one byte of memory. This is generally quite wasteful (8 bits used to store 1 bit), and implementations of the C++ standard library are allowed to internally change things to reduce wastefulness. This may have a trivial impact on performance.
More importantly, this means that operator [], at(), front(), and back() do not actually return references to booleans (unless the vector is const). Instead, they return an instance of a member class that behaves in the same way as a bool reference would, namely std::vector<bool>:reference. While they can cast implicitly to bool, it is important to note that they are not bools. If you are doing anything with the <type_traits> header, this is critical.
The reference class additionally provides the flip() member function to flip the value of the bool an instance refers to.
Although iterators were not discussed in this document, for those who know about them, the iterators for this specialization are also different internally. Non-const iterators will return an instance of that reference class. Otherwise their behavior in normal use should be the same.
Additionally, std::vector<bool>::swap gets an extra static version of itself with different functionality. This static version can be used to switch the values of two bits in std::vector<bool>s. Note that as arguments it takes the aforementioned bool references that std::vector uses, meaning that this is only really practical for swapping bit values within the same vector or between different vectors.
Finally, one extra member function is added: std::vector<bool>::flip. Its only purpose is to flip all the values in the vector.
If for any reason you don't want to use this specialization, consider using std::vector<char> instead and simply assign boolean values to its elements.
Vectors are not a one-size fits all solution to sequential data storage, however they are quite capable as convenient resizable arrays.
-Albatross
Technical fine print: This article is meant as a non-technical article suitable for beginning programmers, and to that end, may make assumptions about the template parameters used and may use technically imprecise language.
This forum often sees questions about programs in which programmers would like to store a series of elements at runtime, but don't know how large the series will be ahead of time.
The classic C solution to this problem involves dynamically allocating an array and "resizing" it as needed by allocating a new array and copying elements over from the previous one. However, such strategies can not only be cumbersome for newer programmers to implement but also require manual memory management which can open up risks of memory leaks.
To this end, this article will introduce the Standard Template Library (STL) class template std::vector as a potential solution to the problem of resizable arrays. std::vectors offer member functions for most common tasks that involve array resizing, can serve in many cases as a drop-in replacement for arrays, and a handy size optimization for storing boolean values.
This article may be easier to understand if you (the reader) are familiar with the following:
- The use of arrays (C or C++ style).
- The use of functions.
- The instantiation of classes and use of their members.
- The instantiation of class templates (optional).
The Absolute Basics
A misconception that many beginners have is that std::vectors are like n-dimensional vectors from mathematics or physics. While this is an understandable misunderstanding, it's better to think of std::vector as a bit of code (a wrapper) that manages an array that can change its size.
Let's begin with the creation of a vector. Like any element of the standard library, one needs to include a header to use vectors. The header in question is quite intuitively named: it's "vector".
#include <vector>
To instantiate a vector, all one needs to do is this:
std::vector<value_type> variable_name;
This creates an empty vector. To have the vector start at a certain size, this will work as well:
std::vector<value_type> variable_name(number_of_elements);
Each element in that vector will be initialized to its default value. If the programmer wishes to initialize them all to some value other than the default, then there is yet another option:
std::vector<value_type> variable_name(number_of_elements, value);
The full list of ways to initialize a vector can be found here.
Vectors can be used much like arrays can. They support the [] operator for element access much like arrays do (and their indices are the same, remember that the range of indices is [0,size-1]), and can therefore serve, in many cases, as drop-in replacements for arrays. One notation that doesn't work, however, is this:
*(ptr_to_first_element_of_array_this_name_is_really_long+offset)
Just as a warning.
A Selection of Member Functions
Vectors offer a member function to get the number of elements they contain, namely std::vector::size. Its return type, size_t, is an unsigned integer that is large enough to represent the size of any object in bytes. On 32-bit systems, it's at least 32 bits large. On 64-bit systems, it's at least 64.
|
|
Alternatively, if you simply wish to test to see if the vector is empty, the std::vector::empty function returns a bool that is true if the vector has no elements in it, and false otherwise.
|
|
In addition to the [] operator, vectors also provide the std::vector::at member function. It takes the same arguments as the operator and returns a reference just like the operator does. The difference, however, is that it checks to make sure that the provided index is less than the size of the vector. If it's not, it throws an exception, whereas the [] operator could literally do anything. Usually, it will either access memory that the program hasn't reserved, or cause a segmentation fault which will likely crash the program. at() is very slightly slower as a result, but easier to debug if something does go wrong.
|
|
For convenience, vectors also provide functions to get the element at index 0 (the front of the vector) and the element at index size-1 (the back of the vector). They're intuitively named.
|
|
Adding a new element to the end of a vector is quite easy. Vectors offer the std::vector::push_back function, which takes a single element that gets copied (or moved) onto the back (remember: back = largest index) of the vector, expanding it by one.
|
|
Similarly, vectors also have a std::vector::pop_back function which takes no arguments and removes the last element of the vector, shrinking it by one. This destroys the removed element, if applicable.
|
|
Clearing the vector of all its elements is also easy. One call to std::vector::clear removes and destroys all the elements of a vector, setting its size to 0.
|
|
To easily resize a vector, one can use std::vector::resize. It takes two arguments, though the second has a default value. The first is the number of elements to resize the vector to. If this is smaller than the current size, then the extra elements at the end (greater indices) get destroyed. The second parameter is what to initialize the new elements to if the first argument is larger than the current size.
|
|
If there is ever a need to exchange the contents of vectors, there's another simple function in the form of std::vector::swap. It takes a vector as an argument which is passed by reference, and the vectors have their contents exchanged. The vector passed in shouldn't, therefore, be const.
|
|
These are not all the member functions of vectors. There are others that may be of interest some of those require some prerequisite knowledge about iterators. And that... is a topic for another article.
vector<bool>
Vectors behave slightly differently when they're storing bools.
Normally, a bool gets stored in one byte of memory. This is generally quite wasteful (8 bits used to store 1 bit), and implementations of the C++ standard library are allowed to internally change things to reduce wastefulness. This may have a trivial impact on performance.
More importantly, this means that operator [], at(), front(), and back() do not actually return references to booleans (unless the vector is const). Instead, they return an instance of a member class that behaves in the same way as a bool reference would, namely std::vector<bool>:reference. While they can cast implicitly to bool, it is important to note that they are not bools. If you are doing anything with the <type_traits> header, this is critical.
The reference class additionally provides the flip() member function to flip the value of the bool an instance refers to.
bool_vec.at(3).flip();
Although iterators were not discussed in this document, for those who know about them, the iterators for this specialization are also different internally. Non-const iterators will return an instance of that reference class. Otherwise their behavior in normal use should be the same.
Additionally, std::vector<bool>::swap gets an extra static version of itself with different functionality. This static version can be used to switch the values of two bits in std::vector<bool>s. Note that as arguments it takes the aforementioned bool references that std::vector uses, meaning that this is only really practical for swapping bit values within the same vector or between different vectors.
vector_1::flip(vector_1.front(),vector_2.back()); //Switcheroo!
Finally, one extra member function is added: std::vector<bool>::flip. Its only purpose is to flip all the values in the vector.
a_vector_of_false_values.flip(); //Now a misnomer!
If for any reason you don't want to use this specialization, consider using std::vector<char> instead and simply assign boolean values to its elements.
In conclusion
Vectors are not a one-size fits all solution to sequential data storage, however they are quite capable as convenient resizable arrays.
-Albatross
Technical fine print: This article is meant as a non-technical article suitable for beginning programmers, and to that end, may make assumptions about the template parameters used and may use technically imprecise language.