Learn C++ STL

Lesson 3 of 9 · vector: The Container You Reach for First

Module 2 · vector: The Container You Reach for First

Full Programs: From Five Lines to a Real Tool

FreeReading

In this lesson

  • Write six complete vector programs, from reading and printing a list to a marks report with a histogram.
  • Build a grid as vector<vector<int>>, both as a rectangle and with rows of different lengths.
  • Answer many range-sum questions in O(1) each with a prefix-sum vector, the first contest idea of this track.

In the C track's Module 9 you wrote a marks report with fixed arrays. It had #define MAX_S 100, a count variable beside every array, and it refused student 101. This lesson writes the same report again, with vectors and no size limit. Six programs get there, each one a little bigger, and each adds one new thing. Read the "new thing" line above each program first; it is what that program is for.

Program 1: read n values, print them back

The new thing: for (int& x : a) cin >> x; reads straight into the elements, and a separator that never leaves a trailing space.

Almost every contest input starts with n, then n values. Size the vector to n, then read into each element through a reference, Module 1's second name for a box.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) {
        cin >> x;
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

12 7 30 7 5

That output is for the input 5 and 12 7 30 7 5. Each element gets a space after it, except the last, which gets the newline. With int x instead of int& x, the loop would read into copies and the vector would stay all zeros. So int& is what makes the reading loop work.

Program 2: the running maximum and its index

The new thing: keeping two things at once while you walk, the best value and where it was.

Alice logs the top temperature each day of a week. She wants the hottest day and its index. When two days tie, she wants the first one.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> temps(n);
    for (int& t : temps) {
        cin >> t;
    }

    int best = 0;
    for (int i = 1; i < n; i++) {
        if (temps[i] > temps[best]) {
            best = i;
        }
    }
    cout << "hottest " << temps[best] << " on day index " << best << '\n';
    return 0;
}

hottest 23 on day index 1

That output is for the input 7 and 18 23 21 23 19 17 20. Keeping only the index is enough, because temps[best] gives the value back. The test is >, not >=, so a later 23 never replaces the first. Starting from index 0 instead of from 0 degrees means a week below freezing still works.

Program 3: a frequency table

The new thing: vector<int> count(k, 0), a vector whose index is a value and whose element is how often it appeared.

David rolls a die ten times and counts each face. Faces run from 1 to 6, so the vector needs indexes up to 6, which means 7 elements. Index 0 is never used, and that is fine.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> count(7, 0);
    for (int i = 0; i < n; i++) {
        int face;
        cin >> face;
        count[face]++;
    }

    for (int face = 1; face <= 6; face++) {
        cout << face << ": " << string(count[face], '*') << (count[face] > 0 ? " " : "") << count[face] << '\n';
    }
    return 0;
}

1: ** 2
2: * 1
3: **** 4
4: 0
5: * 1
6: ** 2

That output is for the input 10 and 3 6 1 3 3 5 6 2 3 1. string(k, '*') makes a row of k stars, a one-line histogram. The value itself is the index, so each roll costs one step, and no search is needed. A face of 7 would write past the end, so in real input you check the range first, as the C track's count arrays did.

Program 4: a grid, as a vector of vectors

The new thing: vector<vector<int>> g(r, vector<int>(c)), r rows of c zeros, read and printed lined up.

Maria's shop has r shelves and c slots on each, with a count of items in every slot. The outer vector holds the rows. Each row is itself a vector<int>, so g[i][j] is row i, column j, as in a C grid.

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, c;
    cin >> r >> c;
    vector<vector<int>> g(r, vector<int>(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> g[i][j];
        }
    }

    for (const vector<int>& row : g) {
        for (int x : row) {
            cout << setw(5) << x;
        }
        cout << '\n';
    }
    return 0;
}

    4   12    0
  150    7   33
    9    9 1000

That output is for the input 3 3, then 4 12 0, 150 7 33 and 9 9 1000. setw(5), from <iomanip>, prints the next number right-aligned in five characters, so the columns line up. The outer range-for takes each row by const&, so no row is copied.

A C array's rows all have the same length. A vector's rows do not have to. Here each row is built with push_back, and row i gets i + 1 seats, like the rows of a small theatre that widen towards the back.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> seats;
    int number = 1;
    for (int row = 0; row < 4; row++) {
        vector<int> this_row;
        for (int k = 0; k <= row; k++) {
            this_row.push_back(number++);
        }
        seats.push_back(this_row);
    }

    for (size_t i = 0; i < seats.size(); i++) {
        cout << "row " << i << " (" << seats[i].size() << " seats):";
        for (int s : seats[i]) {
            cout << ' ' << s;
        }
        cout << '\n';
    }
    return 0;
}

row 0 (1 seats): 1
row 1 (2 seats): 2 3
row 2 (3 seats): 4 5 6
row 3 (4 seats): 7 8 9 10

A shape like this is called ragged, or jagged. A graph's list of neighbours, Module 16's adjacency list, is the same shape: one row per node, each as long as that node's neighbour count. The picture shows what the program built.

vector<vector<int>> seats: an outer vector of handles, each pointing at its own row seats: one outer vector, four rows, four separate blocks outer vector (4 handles) each row's own block, somewhere in memory seats[0]: size 1 seats[1]: size 2 seats[2]: size 3 seats[3]: size 4 1 2 3 4 5 6 7 8 9 10 Inside one row the boxes sit side by side. The rows themselves can be anywhere.

So g[i] is a whole vector, and g[i].size() is the length of that one row.

Program 5: prefix sums answer range questions

The new thing: a vector of running totals, built once in O(n), that answers any "sum from l to r" in O(1).

Kenji's game logs points per round. Players keep asking how many points rounds l to r scored. Adding up each range again costs up to n steps per question. Instead, build prefix, where prefix[k] is the total of the first k rounds. It has n + 1 elements, and prefix[0] is 0.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> points{4, -2, 7, 1, 3};
    int n = points.size();

    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + points[i];
    }

    cout << "prefix:";
    for (long long p : prefix) {
        cout << ' ' << p;
    }
    cout << '\n';

    // rounds counted from 1: the sum of rounds l..r is prefix[r] - prefix[l - 1]
    int questions[3][2] = {{1, 3}, {2, 5}, {4, 4}};
    for (auto& q : questions) {
        int l = q[0], r = q[1];
        cout << "rounds " << l << " to " << r << ": " << prefix[r] - prefix[l - 1] << '\n';
    }
    return 0;
}

prefix: 0 4 2 9 10 13
rounds 1 to 3: 9
rounds 2 to 5: 9
rounds 4 to 4: 1

Rounds 2 to 5 are all the rounds up to 5, minus the rounds up to 1: 13 - 4 = 9. The extra element at the front is what makes l = 1 safe: prefix[l - 1] is prefix[0], which is 0, never prefix[-1]. The totals are long long, because many large values overflow an int.

The cost is O(n) once, then O(1) per question. For n = q = 200,000 that is about 400,000 steps instead of up to forty billion. So prefix sums trade one pass of preparation for instant answers, the first idea on this track that a contest really tests.

Program 6: the marks reportIntermediate

The new thing: a vector of pairs, each pair holding a name and that student's own vector of marks, with no limit anywhere.

Each input line is a name, then that student's marks, ended by -1, because students sat different numbers of tests. The report prints each student's average, the class best, and a histogram of average bands. left, right, fixed and setprecision(1) come from <iomanip>: alignment, and one digit after the point.

#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Each line: a name, then that student's marks, ended by -1.
    vector<pair<string, vector<int>>> students;
    string name;
    while (cin >> name) {
        vector<int> marks;
        int m;
        while (cin >> m && m != -1) {
            marks.push_back(m);
        }
        students.push_back({name, marks});
    }

    const vector<string> band_name{"90+", "80-89", "70-79", "60-69", "below 60"};
    vector<int> band_count(band_name.size(), 0);
    string best_name;
    double best_avg = -1;

    cout << fixed << setprecision(1);
    for (const auto& [who, marks] : students) {
        int total = 0;
        for (int m : marks) {
            total += m;
        }
        double avg = marks.empty() ? 0.0 : (double)total / marks.size();
        cout << left << setw(8) << who << right << setw(3) << marks.size()
             << " marks, average " << setw(5) << avg << '\n';

        int band = avg >= 90 ? 0 : avg >= 80 ? 1 : avg >= 70 ? 2 : avg >= 60 ? 3 : 4;
        band_count[band]++;
        if (avg > best_avg) {
            best_avg = avg;
            best_name = who;
        }
    }

    cout << "best: " << best_name << " (" << best_avg << ")\n";
    for (size_t b = 0; b < band_name.size(); b++) {
        int k = band_count[b];
        cout << setw(8) << band_name[b] << " | " << string(k, '#') << (k > 0 ? " " : "") << k << '\n';
    }
    return 0;
}

Alice     3 marks, average  85.0
Bob       4 marks, average  58.5
Maria     3 marks, average  90.7
Zara      2 marks, average  69.5
Kenji     4 marks, average  80.5
Amara     3 marks, average  94.7
David     2 marks, average  60.5
best: Amara (94.7)
     90+ | ## 2
   80-89 | ## 2
   70-79 | 0
   60-69 | ## 2
below 60 | # 1

That output is for these seven input lines: Alice 78 85 92 -1, Bob 55 61 48 70 -1, Maria 90 94 88 -1, Zara 67 72 -1, Kenji 81 79 85 77 -1, Amara 95 91 98 -1 and David 58 63 -1.

const auto& [who, marks] is Module 1's structured binding: it names the pair's two halves without copying them. Three vectors of three different types work together here, and none has a size limit. Student 101, or student 100,001, is just one more push_back.

Example 1: second chances, a vector filled from a vector

Zara gives a retake to every student who scored under 50. She builds a second vector from the first, holding only the indexes that need one. An empty result is a real answer, so it gets its own line.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> marks{72, 45, 90, 38, 66, 49};
    vector<int> retake;
    for (size_t i = 0; i < marks.size(); i++) {
        if (marks[i] < 50) {
            retake.push_back(i);
        }
    }

    if (retake.empty()) {
        cout << "nobody needs a retake\n";
    } else {
        cout << retake.size() << " retakes, at indexes:";
        for (int i : retake) {
            cout << ' ' << i << " (" << marks[i] << ")";
        }
        cout << '\n';
    }
    return 0;
}

3 retakes, at indexes: 1 (45) 3 (38) 5 (49)

Storing indexes, not values, keeps the link back to the original list, so each retake can still print its mark.

Run in Compiler
Example 2: a moving average over a week

Maria smooths daily sales with a 3-day average. With the prefix vector from Program 5, every window's sum is one subtraction, however wide the window is.

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> sales{12, 15, 9, 20, 18, 25, 30};
    int n = sales.size();
    int w = 3;

    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + sales[i];
    }

    cout << fixed << setprecision(2);
    for (int end = w; end <= n; end++) {
        double avg = (double)(prefix[end] - prefix[end - w]) / w;
        cout << "days " << end - w + 1 << "-" << end << ": " << avg << '\n';
    }
    return 0;
}

days 1-3: 12.00
days 2-4: 14.67
days 3-5: 15.67
days 4-6: 21.00
days 5-7: 24.33

The days are counted from 1, so the window ending at day end covers prefix[end] - prefix[end - w]. A window of 30 days would cost exactly the same per line.

Run in Compiler
Example 3: a grid's neighbours

Bob's minesweeper board marks mines with 1. For each empty cell he prints how many of its four neighbours, up, down, left and right, hold a mine. The bounds check is what keeps the edge cells from reading outside the grid.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> mine{
        {0, 1, 0, 0},
        {0, 0, 0, 1},
        {1, 0, 0, 0},
    };
    int r = mine.size();
    int c = mine[0].size();
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (mine[i][j] == 1) {
                cout << '*';
                continue;
            }
            int near = 0;
            for (int d = 0; d < 4; d++) {
                int ni = i + dr[d], nj = j + dc[d];
                if (ni >= 0 && ni < r && nj >= 0 && nj < c) {
                    near += mine[ni][nj];
                }
            }
            cout << near;
        }
        cout << '\n';
    }
    return 0;
}

1*11
111*
*101

The two small arrays dr and dc list the four steps, so one loop replaces four copied if blocks. The vector of vectors is written in braces, row by row, the way you would draw it.

Run in Compiler

Where this is used

  • OpenCV. cv::findContours returns the outlines it finds in an image as std::vector<std::vector<cv::Point>>: one row per outline, each as long as its own number of points. It is Program 4's ragged shape, in one of the most used vision libraries.
  • LLVM. The compiler project wrote SmallVector, a vector that keeps its first few elements inside the handle itself. Most of its lists are short, so most never touch the heap. Lesson 05 measures why that matters.
  • Godot. The game engine has its own Vector<T> template, which shares one block between copies until one of them is changed. Engines write their own containers to control exactly when memory is copied.
  • SQLite, the C contrast. SQLite is written in C, so it grows its arrays by hand. Its helper sqlite3ArrayAllocate doubles an array's room when it is full, the job push_back does for you.

Common mistakes

1. Making the rows but not their columns.

vector<vector<int>> g(r);
g[0][0] = 5;

No message at any command line. On the Playground it ended with Runtime error and no output. g(r) makes r rows, and every one of them is an empty vector, so g[0][0] does not exist. Write g(r, vector<int>(c)). You will forget the inner part because a C grid's declaration gave both sizes at once.

2. A prefix vector of size n, and prefix[l - 1] at l = 0.

vector<int> p(a.size());
p[0] = a[0];
for (size_t i = 1; i < a.size(); i++) {
    p[i] = p[i - 1] + a[i];
}
int l = 0, r = 2;
cout << p[r] - p[l - 1] << '\n';

No message. With a = {4, -2, 7, 1, 3} the Playground printed 9 and said Success. The answer is right by luck: p[-1] read a box before the vector that happened to hold 0. Use the n + 1 layout of Program 5, where prefix[0] is a real 0. You will write size n because "one total per element" sounds like n totals.

3. Adding into an int.

vector<int> sales(3, 1000000000);
int total = 0;
for (int s : sales) {
    total += s;
}

No message at any command line, and GCC 12 at -O2 printed -1294967296. Three billion does not fit an int, whose largest value is 2147483647, so the sum overflowed. Make every sum a long long, and every prefix vector vector<long long>. You will use int because each value fits; only their total does not.

4. Changing a copy of a row.

for (vector<int> row : g) {
    row[0] = 0;
}

No message, and no change: g is exactly as before. vector<int> row copies each row, and the loop changes the copy. Write vector<int>& row to change it, or const vector<int>& row to read it without the copy. You will write the copy because with int elements the copy never mattered.

Brain teaser

Lesson 01 said a vector's elements sit side by side in one block. This program prints where three elements of a 3 by 3 grid live, as a distance in int boxes from g[0][0].

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> g(3, vector<int>(3, 0));
    const int* start = &g[0][0];
    cout << "g[0][2] is " << &g[0][2] - start << " boxes along\n";
    cout << "g[1][0] is " << &g[1][0] - start << " boxes along\n";
    return 0;
}

In a C array int g[3][3], g[1][0] comes right after g[0][2], at 3. Will this vector of vectors print 3 for g[1][0]? What does the picture of Program 4 say, and what might it cost when a program walks a big grid?

Look again at the picture of seats. How many blocks did push_back and the constructor ask for, and who decides where each one goes?

Exercise 1Easy

A quiz gives every student a whole-number score from 0 to 100. The teacher wants to know how many students got each score.

Input. A line with n, then n integers between 0 and 100.

Output. For every score that appears, in increasing order, one line with the score and how many times it appears, separated by a space.

Constraints. 1 <= n <= 200000.

Sample. Input 8 and 3 7 3 0 100 7 3 5 gives five lines: 0 1, 3 3, 5 1, 7 2 and 100 1.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> scores(n);
    for (int& s : scores) {
        cin >> s;
    }

    // Count each score from 0 to 100 in a vector,
    // then print "score count" for every score that appears.

    return 0;
}

Graded as frequency-table, a free problem in this module's set. The hidden tests include the scores 0 and 100, and a list where every score is the same.

Run in Compiler
Exercise 2Medium

Kenji's game has n rounds and q questions. Each question asks for the total points of rounds l to r, counted from 1.

Input. A line with n and q, a line with n integers, then q lines with l and r.

Output. q lines, each the sum of rounds l to r, both included.

Constraints. 1 <= n, q <= 200000, 1 <= l <= r <= n. Each value is between -1000000000 and 1000000000.

Sample. Input 5 3, 4 -2 7 1 3, then 1 3, 2 5 and 4 4 gives 9, 9 and 1.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> points(n);
    for (int& p : points) {
        cin >> p;
    }

    // Build the prefix sums once, then answer each question with one subtraction.

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        // print the sum of rounds l..r
    }
    return 0;
}

Graded as prefix-range-sums. The hidden tests include l = 1, l = r, and totals an int cannot hold. One holds 200000 days and 61527 questions over all of them, where adding each range again is too slow.

Run in Compiler
Exercise 3Medium

Maria's shop grid from Program 4 has r shelves and c slots. She wants the total on each shelf and in each column of slots.

Input. A line with r and c, then r lines of c integers.

Output. Two lines: the r row sums, then the c column sums, each separated by single spaces.

Constraints. 1 <= r, c <= 500. Each value is between -1000000000 and 1000000000.

Sample. Input 2 3, 1 2 3 and 4 5 6 gives 6 15 and 5 7 9.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, c;
    cin >> r >> c;
    vector<vector<int>> g(r, vector<int>(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> g[i][j];
        }
    }

    // Print the r row sums on one line, then the c column sums on the next.

    return 0;
}

Graded as grid-row-col-sums. The hidden tests include a 1 by 1 grid, a single row, a single column, and 500 values of 109 in one row.

Run in Compiler

Common doubts

  • Why is the prefix vector one longer than the data?

    So that "the total of the first 0 elements" has a box, prefix[0] = 0. Then every range, the one starting at the first element included, uses the same formula, with no special case.

  • Should I use vector<vector<int>> or a C array int g[500][500] for a grid?

    The vector sizes itself from the input and can be ragged. The C array is one block and needs its size before the program runs. In a contest both are common; this track uses the vector, and lesson 05 measures the difference.

  • Program 6 uses a pair. Should a student be a struct instead?

    Module 1's rule: a pair for a moment, a struct for a thing. A report that grows, with an id, a class and an email, deserves a struct with named fields. For two halves read once and printed, the pair is fine.

  • Is setw needed in a judged problem?

    No. Judged output is single spaces, exactly as the statement says. setw is for output a person reads, like Program 4's grid and the report.

Key takeaways

  • Read n values with vector<int> a(n) and for (int& x : a) cin >> x;, and print with a separator that leaves no trailing space.
  • A running maximum keeps the best index; > keeps the first of a tie.
  • vector<int> count(k, 0) turns a value into an index: one step per input, after checking the range.
  • vector<vector<int>> g(r, vector<int>(c)) is a grid; built with push_back, its rows can have different lengths.
  • A prefix vector of n + 1 long long totals answers every range sum with one subtraction.
  • Go deeper: Under the Hood, how a vector grows and what that breaks (Pro).

Next, lesson 04 asks when a vector is the wrong tool, and draws the chart and the flowchart that pick its neighbour instead.

End of lesson 3

Mark it done, and your progress moves with you.

Next: When to Use vector and When Not To

Next lesson