Jagged arrays and copying

Why this matters

Real data is often not a neat rectangle. A class register has a different number of students in each class. A bus timetable has a different number of stops on each route. A tree of folders has a different number of files in each folder. Each row of the table has its own length, and the lengths do not match. Programmers call this shape a jagged array, because its outline has uneven edges.

Two things go wrong with jagged data more often than with neat grids. The first is the loop bounds. A loop that uses the length of the first row for every row reads too far, or too little, on the other rows. The second is copying. When you copy a structure that holds other structures, you need to know whether the copy shares the stored numbers with the original or has its own. A copy that shares the numbers can change the original by accident, and that kind of bug is hard to find because the original looks like it was never touched.

This lesson builds on the two-dimensional arrays lesson, where a grid had the same number of columns in every row. It uses the same vector<vector<int>> type. The spiral traversal lesson before this one showed how to walk a rectangle, and this lesson shows what changes when the rectangle is not one.

The idea: rows that have their own lengths

Think of a school with three classes. Class A has 3 students, class B has 1 student, and class C has 2 students. If you write the names in a table with one row per class, the rows have different lengths. A rectangle cannot hold this data without wasting space, because a rectangle needs every row to have the same number of columns. A jagged array does not need that. Each row is its own list, and the outer list holds the rows.

In C++, a C-style two-dimensional array such as int g[3][4] is always a rectangle. Its row length is fixed by the type, so every row has four values. A vector<vector<int>> is different. The outer vector holds one vector per row, and each inner vector has its own size. The outer vector stores three vectors, and their sizes can be 3, 1 and 2. The lengths are not part of the type, so they can be different at run time.

To read a row, you use the row index first, then the column index. classes[1][0] is the first value in row 1. To ask how long a row is, you call size() on that row, as in classes[1].size(). The outer vector's size() gives the number of rows, and each row's size() gives the number of values in that row. Keeping these two questions apart is the key to reading jagged data.

Building a jagged array

The first program builds a jagged array from a list, prints each row with its length, and computes the total of all the values. The braces in the declaration list the rows, and each row has the values it needs. The last row is empty, which is allowed, because a vector can hold zero values.

No input is needed. The program prints:

row 0 length 3: 1 2 3
row 1 length 1: 4
row 2 length 2: 5 6
row 3 length 0:
total 21

The outer loop goes from 0 to jagged.size(), which is 4, so it visits all four rows, including the empty one. The inner range-based loop, for (int x : jagged[r]), uses the length of that row automatically. It never reads past the end of the row, because the range loop stops when it reaches the row's last value. The total is computed by a second pair of loops, and the range-based form is used again. The total is 1 plus 2 plus 3 plus 4 plus 5 plus 6, which is 21.

The range-based for loop is the safest way to visit every value of a jagged array, because it uses each row's own length. The index form r and c is needed when you also need the position. When you use indexes, the inner bound must come from the row, not from another row.

Reading each row with its own length

The most common bug with a jagged array is to use one row's length for every row. Take the example above and imagine the inner loop goes up to the length of row 0, which is 3. On row 1, which has only one value, the index 1 is past the end. With vector's square-bracket operator, the program does not check the index. It reads memory that does not belong to the row. The result is undefined behaviour, which means the program can print a wrong number, crash, or appear to work on one run and fail on the next.

The safe rule is simple. Inside a loop over row r, the inner bound is jagged[r].size(). The bound comes from the row that the loop is reading. The worked examples below follow this rule, and the mistakes section shows what happens when it is broken.

Worked example 1: a triangle of counts

The next example builds a jagged array with a shape that grows by one value per row. The shape is a triangle, and the values come from a well-known pattern called Pascal's triangle. You do not need to know the pattern for this lesson. The only rule that matters here is that row i starts with i + 1 values, and each value in the middle of a row is the sum of two values from the row above.

The function below builds the triangle one row at a time. For row i, it creates a vector of i + 1 ones. Then, for each middle position j, it replaces the one with the sum of the two values above it. The first and last values of each row stay at 1, which is why the function starts the middle loop at 1 and ends it before i.

The program prints:

row 0 length 1: 1
row 1 length 2: 1 1
row 2 length 3: 1 2 1
row 3 length 4: 1 3 3 1
row 4 length 5: 1 4 6 4 1

Each row is one longer than the row before it, so the outline is a triangle. The middle loop in pascal reads tri[i - 1], which is the row above, and that row has i values. Its indexes j - 1 and j go from 0 up to i - 1, which are all valid positions in the row above. This is the same rule as before: the row being read decides the bound. The loop never reads tri[i - 1][i], which would be past the end.

Check the row lengths by hand. Row 0 has one value, row 1 has two, and row 4 has five. The row for index i has i + 1 values, and the output shows that pattern. The middle values are sums of the two values above: row 2 has a 2 in the middle because 1 plus 1 is 2, and row 4 has a 6 in the middle because 3 plus 3 is 6.

The triangle is a good way to see that a jagged array can be built one row at a time with push_back. Each row is complete before it is added, and the next row can read the rows that already exist.

Worked example 2: a jagged table with a longest row

A second example reads a jagged table and finds the longest row. The table holds scores for students in different classes, and the number of scores in each class differs. The program reads the number of classes, then reads each class's count and its scores. It then finds the class with the most scores and prints its number.

Type this into the Input box:

3
2 70 80
1 95
4 60 61 62 63

The program prints:

longest row 2 with 4 scores
total 491

The class counts are read from the input. Row 0 has two scores, 70 and 80. Row 1 has one score, 95. Row 2 has four scores, 60, 61, 62 and 63. The longest row is row 2, which has four values. The total is 70 plus 80 plus 95 plus 60 plus 61 plus 62 plus 63. Adding in pairs gives 150, then 245, then 305, 366, 428 and 491, which matches the program.

The example has two details. The first is resize(count), which sets the size of each row after the count is known. The outer vector starts with classes empty rows, and resize gives each row its count of zeros before the scores are read into it. The second is the loop that finds the longest row. It starts at row 1 and compares each row's size() with the size of the current longest row. A loop that compares two rows always uses the sizes of both rows, not a fixed size.

Copying a structure

A copy makes a second set of values from the first. In a program, a copy is made by an assignment such as b = a, by passing a value to a function, or by returning a value from a function. Copies matter because each variable name is a separate label, and a change through one label can be seen through another label only when the two labels share the same stored data.

Two words describe how much is shared.

• A deep copy makes new storage for every value. The new copy owns its own numbers. A change to one copy does not change the other.
• A shallow copy copies only the outer part of the structure. The two copies share the stored data beneath it. A change through one copy can be seen through the other.

Think of a shared folder and a photocopy. A deep copy is a photocopy of every page. You can write on the photocopy and the original stays the same. A shallow copy is a second note that says "look in drawer 3". Both notes point to the same papers, so a change to the papers is seen through both notes.

In C++, the standard vector makes deep copies by default. Copying vector<vector<int>> copies each inner vector and all of its values, so a jagged array copied with = is fully independent. The next program shows this, and it also shows two things that look like copies and are not.

The program prints:

deep copy: a[0][0] = 1, b[0][0] = 100
view: a[1][0] = 300
wrong copy row 1 length = 2, first value = 1

The first line shows the deep copy. b is a full copy of a. Setting b[0][0] to 100 changes only b, and a[0][0] is still 1. This is the behaviour most programs need when they say "make a copy".

The second line uses span, which is a C++20 type that gives a view of a range of values without owning them. span<int> view = a[1]; creates a view of the values in row 1 of a. The view does not copy anything. Setting view[0] to 300 changes the value in a[1], and the output shows the change. A view is like a second note that points at the same papers. It is useful for passing part of an array to a function, but it must not outlive the array it points at. If the vector a[1] grows, the view can point to memory that no longer holds the row.

The third line shows a copy that is wrong. The constructor wrong(a.size(), a[0]) makes as many rows as a has, and it fills every row with a copy of row 0. Row 1 becomes a copy of {1, 2}, not {3, 4, 5}. The row lengths in a jagged array come from the rows, so a copy that uses one row for all the rows throws away the shape of the data. The fix is to copy the outer vector with =, or to build each row from its own source row.

What a shallow copy does in C-style code

The deep copy above is automatic for vectors. It is not automatic for every type. A class that holds a raw pointer to memory it allocated with new gets a shallow copy when it is copied with the default rules. The default copy copies the pointer, which is only an address. Two objects then hold the same address, and both try to free it when they are destroyed.

The next program shows the problem. The class Row allocates an array with new, and frees it in its destructor. It does not write a copy function, so C++ copies the pointer.

The program prints:

copied
free(): double free detected in tcache 2

and exits with code 134 on this system; the wording can differ elsewhere. The message copied shows that the copy was made. The error comes at the end of main, when b and then a are destroyed. Each destructor calls delete[] on the same address. The first call frees the memory. The second call tries to free memory that was already freed, and the C++ runtime stops the program with the message shown. The text double free is the name of this bug. The copy was shallow, because a and b share one array.

The fix is to store the numbers in a vector, which makes the copy deep. The class below does that. It has no new and no destructor, because the vector cleans up its own memory. The copy then gets its own array.

The program prints:

a = 1, b = 100

The copy is deep, because the default copy of Row copies its vector member, and the vector copies its values. Setting b's first value leaves a alone. The general rule is to hold data in standard containers, such as vector, and let them manage the memory. A class written this way needs no copy functions and no destructor, and copies behave the way a learner expects.

Common mistakes

The first mistake is the one from the earlier section: using the first row's length for every row. The program below does this on purpose. It loops over the columns with the length of row 0, which is 3, and reads row 1, which has only one value. The at function checks each index, so the error is reported instead of hidden.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<vector<int>> jagged = {{1, 2, 3}, {4}};
    for (size_t r = 0; r < jagged.size(); r++) {
        for (size_t c = 0; c < jagged[0].size(); c++) {
            cout << jagged.at(r).at(c) << ' ';
        }
        cout << endl;
    }
    return 0;
}

The output is:

1 2 3 
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 1) >= this->size() (which is 1)

Row 0 prints correctly. On row 1, the program asks for index 1 of a row that has only one value, at index 0. The message says __n is 1, the index asked for, and this->size() is 1, the size of the row. The fix is to use jagged[r].size() as the bound of the inner loop. The square-bracket form jagged[r][c] would not stop with an error here. It would read memory past the row, which is harder to find, so use at while you are learning to see these bugs.

The second mistake is the shallow copy with a raw pointer, shown in the previous section. Its symptom is the double free detected message, followed by exit code 134. The fix is to store the data in a vector. A quick check for this problem is to search a class for new without a matching copy function. If a class has a raw pointer and no copy constructor or copy assignment, the default copy is shallow, and that is a bug.

The third mistake is to think that a copy with = makes the inner rows independent when the rows are pointers or views. A span or a pointer copies only the address. The span example above changed a through view, and that was intended. The risk is when the program expects two independent copies and gets a shared one. Use vector values in a jagged structure, and the copies are deep.

Practice

Exercise 1

Given this jagged array, how many values are there in total? Count by hand, then write the loop that computes the count for any jagged array.

vector<vector<int>> c = {{7}, {8, 9}, {}};

Show the answer.

There are 3 values in total: 7, 8 and 9. The row with no values adds 0. The loop is:

int count = 0;
for (const auto& row : c) {
    count += static_cast<int>(row.size());
}

The loop adds the length of each row. It uses size() on each row, so the empty row adds nothing and no index is read.

Exercise 2

Predict the output of this program, then check your answer.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<vector<int>> a = {{1}, {2}};
    vector<vector<int>> b = a;
    b[1].push_back(5);
    cout << "a[1] size = " << a[1].size() << ", b[1] size = " << b[1].size() << endl;
    return 0;
}

Show the answer.

The output is:

a[1] size = 1, b[1] size = 2

The copy with = is deep, so the push_back on b[1] adds a value only to b. The original row keeps its size of 1.

Exercise 3

Write a function named copyJagged that takes a jagged array by constant reference and returns an independent copy of it. Then state why the function is short.

Show the answer.

The function can return its input, because the return value is a new vector:

vector<vector<int>> copyJagged(const vector<vector<int>>& jagged) {
    return jagged;
}

The copy is deep, because the vector copy operation copies each inner vector and its values. The function is short because the standard library does the work. Changing the result leaves the input unchanged, the same as the = copy in exercise 2.

Exercise 4

Build Pascal's triangle with six rows, using the function from worked example 1. Predict the last row before running the program.

Show the answer.

The last row is 1 5 10 10 5 1. Printing each row on its own line gives:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Each row has one more value than the row above. The sixth row is the sum of pairs from the fifth row: 1 plus 4 is 5, 4 plus 6 is 10, 6 plus 4 is 10, and 4 plus 1 is 5.

Exercise 5

The function below is meant to sum each row of a jagged array and return the sums. It has one bug. Find the bug, and write the fix.

vector<int> rowSums(const vector<vector<int>>& jagged) {
    vector<int> sums;
    for (size_t r = 0; r < jagged.size(); r++) {
        int total = 0;
        for (size_t c = 0; c < jagged[0].size(); c++) {
            total += jagged[r][c];
        }
        sums.push_back(total);
    }
    return sums;
}

Show the answer.

The bug is the inner bound, jagged[0].size(). It uses the length of row 0 for every row. A row that is shorter than row 0 is read past its end, which is undefined behaviour. A row that is longer than row 0 is only partly summed. The fix is to use the length of the row being read:

for (size_t c = 0; c < jagged[r].size(); c++) {
    total += jagged[r][c];
}

The corrected loop reads only the values that belong to row r.

Summary

• A jagged array is a vector of vectors whose rows have different lengths.
• Use jagged[r].size() as the inner bound, or a range-based for loop, so every row is read with its own length.
• A deep copy makes new storage, and a shallow copy shares the stored data. A vector copy is deep.
• A span or a raw pointer is a view or an address, not a copy, so changes through it are seen by the original.
• A class that owns memory with new needs a copy function or a vector member, or its copies share memory and fail with a double free.
• Use at while learning, so an out-of-range index stops the program with a message.