The container vector

Containers

Containers are structures used to handle the storage and access of elements. A static array is a kind of container. There is, however, many more types of containers. They differ in how they store their elements and how they provide access to them.

The advantage of static arrays is that they provide fast and direct access to their elements and they never get reallocated. However, their downside is that their size can not change once they are created and there is a (very small) limit to the size they can take in memory.

The C++ Standard Library provides a set of classes implementing containers. We will start by seeing one of the simplest and useful: std::vector<T>.

The container std::vector<T>

The class std::vector<T> is templated. We must give it the type of variable we want it to store as template argument. It contains 3 member variables: A pointer to a dynamically allocated memory space, a pointer to the end of the array and a pointer to the end of the allocated memory space. We can add/remove elements to/from it and it will change the size of the array accordingly. When the size of the array grows too big for the memory space to hold, it automatically reallocates it. The reason that it contains a pointer to the end of the array and one at the end of the memory space is that the size of the array is not necessarily the same as the size of the memory space, because each time an object of type std::vector<T> needs to reallocate the memory space it points to, it allocates more memory than required, in order to reduce the number of reallocation.

Unlike a static array, which is the memory space, an object of type std::vector<T> only points to and manage a memory space. The object does not take too much space in the memory. It usually weights only the size of 3 pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
namespace std{ template<class T> class vector { public: /* Many methods. */ private: // The member variables may look like that. T *_memLoc; T *_memLocEnd; T *_arrayEnd; }; }

As we will see, using the class std::vector<T> is very convenient, as it handles dynamic memory allocation for us.

Defining an object of type std::vector<T>

We define an object of type std::vector<T> as we would define any other object, except that we must give it, as template argument, the type of elements it must store. Note that it is declared in the header <vector>.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <vector> int main() { // Vector storing variables of type 'int'. std::vector<int> vectorInt; // Vector storing elements of type 'float'. std::vector<float> vectorFloat; // Vector storing variables of type 'char'. std::vector<char> vectorChar; return 0; }

Adding a value at the end of a vector

We can add a value to the end of a container of type std::vector<T>, therefore increasing its size by one element, using the method void std::vector<T>::push_back(const T &value).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector> int main() { std::vector<int> vectorInt; /* Adds the value 35 to the vector. It now contains 1 element, which value is 35. */ vectorInt.push_back(35); /* Adds the value 732 to the vector. It now contains 2 element2, which are 35 and 32. */ vectorInt.push_back(732); return 0; }

Accessing the elements of a vector

We can access the elements of a vector using the method T & std::vector<T>::at(size_type index) or simply with the [] operator. Without much surprise, in both cases, elements are accessed using their indexes, starting at 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector> #include <iostream> int main() { std::vector<float> vec; vec.push_back(93.58); vec.push_back(21.82); std::cout << vec.at(0) << " " << vec[1] << std::endl; return 0; }

We can also access, respectively, the first and last element of the vector, using the methods T & std::vector<T>::front() and T & std::vector<T>::back().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector> #include <iostream> int main() { std::vector<char> vec; vec.push_back('A'); vec.push_back('B'); vec.push_back('C'); vec.push_back('D'); std::cout << vec.front() << " " << vec.back() << std::endl; return 0; }

We can directly change the value of the elements by assigning a value to the reference the [] operator and the methods presented above return.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector> #include <iostream> int main() { std::vector<int> vec; vec.push_back(999); vec.push_back(999); vec.push_back(999); vec.push_back(999); vec.front() = 1; vec[1] = 2; vec.at(2) = 3; vec.back() = 4; for(unsigned c = 0; c < 4; c++) std::cout << vec[c] << std::endl; return 0; }

Note that the [] operator and four methods presented above exist in a constant overload which return a constant reference. Those overloads are used when called from a constant object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <vector> #include <iostream> int main() { std::vector<int> vec; vec.push_back(100); vec.push_back(200); vec.push_back(300); vec.push_back(400); const std::vector<int> *ptr = &vec; std::cout << ptr->front() << std::endl; std::cout << ptr->operator[](1) << std::endl; std::cout << ptr->at(2) << std::endl; std::cout << ptr->back() << std::endl; return 0; }

Retrieving the size of the vector

The number of elements inside a vector is retrieved using the method size_type std::vector::size() const.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector> #include <iostream> int main() { std::vector<int> vec; for(unsigned c =0; c < 7; c++) vec.push_back(c); std::cout << "Number of elements inside 'vec': "; std::cout << vec.size() << "\n\n"; for(unsigned c =0; c < 7; c++) std::cout << vec[c] << std::endl; return 0; }

Setting the size of a vector

We can set the size of an object of type std::vector<T>, with the method void std::vector<T>::resize(size_type size, T value=T()). The first argument is the size of the array and the second one is the value to assign the new elements with, if the size of the vector is increased. If the size given in argument is smaller than the size of the vector, elements, at the end, are removed from the it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream> #include <vector> int main() { std::vector<int> vec; std::cout << "Size of the vector: " << vec.size() << std::endl; // Resizes the vector to 6 elements and assign them with the value 0. vec.resize(6, 0); std::cout << "Size of the vector: " << vec.size() << std::endl; // Adds an element at the end of the vector, increasing its size to 7. vec.push_back(9); std::cout << "Size of the vector: " << vec.size() << "\n\n"; // Prints the value of the elements of the vector. for(unsigned c=0; c < vec.size(); c++) std::cout << vec[c] << std::endl; std::cout << "\n"; // Resizes the vector to 3 elements. vec.resize(3); // Prints the value of the elements of the vector. for(unsigned c=0; c < vec.size(); c++) std::cout << vec[c] << std::endl; return 0; }

The class std::vector<T> possesses the constructor overload std::vector<T>::vector(size_type size, const T & value = T()), which sets the size of the vector to the value given as first argument and assigns the created elements with the value given as second argument. It also has the overload std::vector<T>::vector(const std::vector<T>& vec) which copies the vector given as argument.

The method void std::vector<T>::clear() sets the size of the vector it is called from, to 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream> #include <vector> int main() { // Creates a vector of 5 elements with the value 100. std::vector<int> vec(5, 100); // Creates a copy of the vector 'vec'. std::vector<int> vec2(vec); std::cout << "Size of 'vec': " << vec.size() << "\n"; std::cout << "Size of 'vec2': " << vec2.size() << "\n\n"; std::cout << "Values of the elements of 'vec2':\n"; for(unsigned c = 0; c < vec2.size(); c++) std::cout << vec2[c] << std::endl; std::cout << "\n"; // Clears the two vectors. vec.clear(); vec2.clear(); std::cout << "Size of 'vec': " << vec.size() << "\n"; std::cout << "Size of 'vec2': " << vec2.size() << "\n\n"; return 0; }

We can also copy of a vector using the assignment operator overload std::vector<T> & std::vector<T>::operator=(const std::vector<T> & vec).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream> #include <vector> int main() { // Creates a vector of 63 elements with the value 0. std::vector<int> vec(63, 0); std::vector<int> vec2; // Copies the vector 'vec' to the vector 'vec2'. vec2 = vec; std::cout << "Size of 'vec': " << vec.size() << "\n"; std::cout << "Size of 'vec2': " << vec2.size() << "\n\n"; return 0; }

Retrieving/setting the size of the memory space of a vector

The method size_type std::vector<T>::capacity() const returns the size (In number of elements, not in bytes) of the memory space of the vector it is called from. The method void std::vector<T>::reserve(size_type n) is used to increase the size (In number of elements) of the memory space of the vector it is called from, to the size given in argument. Note that it can not be used to reduce it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream> #include <vector> int main() { std::vector<int> vec; std::cout << "Size of the vector: " << vec.size() << std::endl; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; for(unsigned c=0; c < 20; c++) vec.push_back(c); std::cout << "Size of the vector: " << vec.size() << std::endl; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; /* Increases the size of the memory space of the vector so it can hold 100 elements before having to reallocate it. */ vec.reserve(100); std::cout << "Size of the vector: " << vec.size() << std::endl; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; // It can not be used to reduce the size of its memory space. vec.reserve(50); std::cout << "Size of the vector: " << vec.size() << std::endl; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; /* As long as the number of elements do no reach over the size of the memory space, there is no reallocation. */ for(unsigned c=0; c < 80; c++) vec.push_back(c+20); std::cout << "Size of the vector: " << vec.size() << std::endl; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; /* One more element than the memory space can hold, so it is reallocated to increase its size. */ vec.push_back(101); std::cout << "Size of the vector: " << vec.size() << std::endl; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; return 0; }

It is possible, in the C++11 version of C++, to reduce the size of the memory space of a vector to its size, using the method void std::vector::shrink_to_fit(). Note that depending on the compiler used, it may have no effect: There is no guarantee that the size of the memory space will be reduced to fit the size of the vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream> #include <vector> int main() { std::vector<int> vec; for(unsigned c=0; c < 100; c++) vec.push_back(c); std::cout << "Size of the vector: " << vec.size() << "\n"; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; // Reduces the size of the memory space of 'vec' to fit its size. vec.shrink_to_fit(); std::cout << "Size of the vector: " << vec.size() << "\n"; std::cout << "Size of its memory space: " << vec.capacity() << "\n\n"; return 0; }

Note on the performance of vectors

Adding values to vectors using the method std::vector<T>::push_back alone is far from optimal as it causes many reallocations. Look at the example above, each time the size of the memory space of a vector changes, that means there has been a reallocation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream> #include <vector> int main() { std::vector<int> vec; unsigned nbReallocs = 0; unsigned lastCapacity = vec.capacity(); for(unsigned c=0; c < 150; c++) { vec.push_back(c); if(vec.capacity() != lastCapacity) { std::cout << "Reallocation at size " << vec.size() << ".\n"; nbReallocs++; lastCapacity = vec.capacity(); } } std::cout << "Number of reallocations: " << nbReallocs << ".\n\n"; return 0; }

It is better, when possible, to use the method std::vector<T>::resize and set the value of the elements using the [] operator, or to use the method std::vector<T>::reserve with the method std::vector<T>::push_back.

Here is the example from above, but using the method std::vector<T>::resize and the [] operator. It causes no reallocation (Only the initial memory allocation).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream> #include <vector> int main() { std::vector<int> vec; vec.resize(150); for(unsigned c=0; c < 150; c++) vec[c] = c; return 0; }

The first example, using the method std::vector<T>::reserve:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream> #include <vector> int main() { std::vector<int> vec; vec.reserve(150); unsigned nbReallocs = 0; unsigned lastCapacity = vec.capacity(); for(unsigned c=0; c < 150; c++) { vec.push_back(c); if(vec.capacity() != lastCapacity) { std::cout << "Reallocation at size " << vec.size() << ".\n"; nbReallocs++; lastCapacity = vec.capacity(); } } std::cout << "Number of reallocations: " << nbReallocs << ".\n\n"; return 0; }