Vectors

The sequence that grows

Creating and filling a vector

The lesson Arrays presented the indexed sequence: elements of the same type, one after another, numbered from zero. Its modern fixed-size form, std::array<int, 7>, carries the size in the type, and the compiler must know it. Now, whoever writes a program that averages the grades of a course does not know how many students it will have. From this follows the need for a sequence whose size is one more piece of data, which changes during execution: it is the vector, std::vector<T>, from the header <vector>, where T is the type of the elements.

#include <print>#include <vector>​int main(){    std::vector<int> squares{};    std::println("At the start: size {}, empty: {}", squares.size(), squares.empty());    for (int k{1}; k <= 5; ++k) {        squares.push_back(k * k);    }    std::println("{}", squares);    std::println("Size {}, first {}, last {}", squares.size(), squares[0], squares.back());    squares[1] = 0;    squares.pop_back();    std::println("{}", squares);}

At the start: size 0, empty: true[1, 4, 9, 16, 25]Size 5, first 1, last 25[1, 0, 9, 16]

Line 6 creates an empty vector of integers: unlike the array, there is no need to announce how many elements it will have. size() returns how many it has, and empty() says whether it has none. The loop of lines 8 to 10 adds five squares with push_back, which places its argument at the end and increases the size by one. Line 11 writes the whole vector with the range formatting that the previous lesson used with arrays. Access by index is the usual one, and squares.back() abbreviates squares[squares.size() - 1]. Line 13 assigns to an existing element, and line 14 removes the last one with pop_back. The operations of this lesson are, in summary, the following.

• v.push_back(x) adds x at the end; v.pop_back() removes the last one (with the vector empty, it is undefined behavior).
• v.size() is the size, of type std::size_t, the unsigned integer for sizes that the lesson Arrays presented; v.empty() is equivalent to v.size() == 0.
• v[i] and v.at(i) give the element of index i, which must satisfy i < v.size(); v.front() and v.back() give the first and the last, and require the vector not to be empty.
• v.resize(n) leaves the vector with n elements: it removes those left over at the end or adds at the end elements initialized as with empty braces (zeros, for numbers).

As with arrays, v[i] guarantees no check, and v.at(i) does: with an index 7 and five elements, it stops the program with the message vector::_M_range_check: __n (which is 7) >= this->size() (which is 5), which names the index and the size. The mechanism that produces that stop, an exception, is studied in Programming in C++ II.

Braces and parentheses

The course initializes everything with braces, and the vector is the first type in the course in which changing the braces for parentheses changes the result. With braces, the values written are the elements; with parentheses, the first number is the number of elements and the second, if there is one, the value of each.

#include <print>#include <vector>​int main(){    const std::vector<int> a{5};    const std::vector<int> b(5);    const std::vector<int> c{3, 7};    const std::vector<int> d(3, 7);    std::println("{} {} {} {}", a, b, c, d);}

[5] [0, 0, 0, 0, 0] [3, 7] [7, 7, 7]

a has one element, the 5; b, five zeros; c, the 3 and the 7; d, three sevens. The list between braces therefore says “these are the elements”, and parentheses are reserved for asking for n copies of the same value, such as a vector of counters at zero.

The last element of an empty vector

An empty vector is a legitimate case (the input with no data, the filter that nobody passes), and every formula with its size must be checked in that case; the most treacherous is v.size() - 1. Since v.size() is an unsigned integer, subtracting 1 from it when it is 0 does not give $-1$, but wraps around, as was seen in the lesson Integers and their representation, to the largest value of std::size_t.

#include <cstddef>#include <print>#include <vector>​int main(){    const std::vector<int> values{};    std::println("values.size() - 1 = {}", values.size() - 1);    // Wrong bound: with the empty vector, the condition is true.    for (std::size_t i{0}; i <= values.size() - 1; ++i) {        std::println("{}", values[i]);    }}

values.size() - 1 = 18446744073709551615/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::const_reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The first line of the output is $18\,446\,744\,073\,709\,551\,615$, that is, $2^{64} - 1$, the largest std::size_t on this platform. From this it follows that the loop condition, 0 <= 18446744073709551615, is true, and that the first iteration reads values[0] from a vector that has no element 0: undefined behavior. What is observed depends on the options, as with arrays: compiled without optimization, the GCC 15 library checks the index of operator[] and stops the program with an assertion that says __n < this->size(); with optimization that check disappears, and the loop, which does not stop in time, tries to read where there is no element at all (checked on Linux with -O2: since the empty vector has no block, the program ends with a segmentation fault, with no message explaining the cause). The fix is to write the bound without a subtraction, i < values.size(), which with the empty vector is false from the start; and, where the subtraction seems necessary, to ask values.empty() first.