UPI Study › Courses › C++ Programming › Free lessons › Lesson 6.5 Free with a free account
Multi-Dimensional Arrays
C++ Programming · Chapter 6: ArraysSection 6.5 · lesson 41 of 84video coming soon
← Feeding Arrays Into FunctionsNext lesson: The Magic Square Puzzle →
In this lesson
Tables in code: declaring and navigating.
- Declare a two-dimensional array, row by row
- Index any cell, row first, then column
- Explain row-major layout and what it implies
- Traverse, total and transpose a table
Transcript
Everything said in the video, section by section (1,275 words). Read along, or search it.
Opening Idea
Data That Needs Two Answers
A single index answers which one. A great deal of real data needs two answers: which row, and which column. Sales by branch and by month. Seats by row and number. Pixels by position. All of it is a table. And a table is what a two-dimensional array is for.
Declaration
Declaring Rows and Columns
A two-dimensional array is declared with two sizes, in two sets of brackets: the number of rows first, then the number of columns. Int sales, 3, 4, reads as three rows of four: 12 values in all. Both numbers are counts. So the valid rows are 0, 1 and 2, and the valid columns are 0 through 3. Starting values are supplied row by row, with a set of braces for each row. Laying the code out like the table it describes is worth the extra lines. An 8 by 8 board has 64 cells. Seven days of twenty-four hours has 168.
Common Mistakes
Row First, Separate Brackets
A single cell is reached with both indexes, in separate brackets, and the first is always the row. Sales 1, 1 is row 1, column 1, which holds 11. Two mistakes to rule out immediately. First, swapped subscripts. Sales 2, 3 isn't the same cell as sales 3, 2. On a non-square table, one of the two is usually out of range, and nothing checks that while the program runs. Say, row, column, to yourself as you type. Second, one pair of brackets with a comma. Sales, bracket 1 comma 2, isn't a two-dimensional access. It's legal C plus plus that means something else entirely. Each index gets its own brackets.
Memory Layout
Row-Major Order in Memory
Memory is one long sequence, so a table has to be flattened into it somehow. C plus plus uses row-major order: the whole of row 0 first, then the whole of row 1, and so on. So the twelve values sit in positions 0 to 11. Sales 2, 1 sits at position 9: two complete rows of four come first, then one more cell. The general position is row times the number of columns, plus the column. That's why the number of columns must always be stated. The row count can sometimes be left to be worked out. The column count never can.
Traversal
Row-Wise Versus Column-Wise Loops
There are several ways to walk a table. All use the nesting you already know. What changes is which variable is on the outside. Row-wise puts the row loop outside, and the column loop inside. It prints 12, 15, 9, 20, then the next row. Column-wise puts the column loop outside. Both visit all 12 cells exactly once. Only the order differs. And notice that in the column-wise version, the subscripts stay in the same order. The subscripts describe the cell. The loops describe the route. Row by row moves through memory in order. Column by column jumps four cells at a time. Both are correct, but on a large table, row-wise is faster.
Diagonals
One Loop for Each Diagonal
A diagonal needs only one loop, because the two indexes move together. On a 4 by 4 grid, grid i, i visits 1, 6, 11, 16: the main diagonal. Grid i, 3 minus i visits 4, 7, 10, 13: the other diagonal, top right to bottom left. Row-wise suits printing, and anything done per row. Column-wise suits column totals. A diagonal visits only n cells, and works on square tables only.
Worked Example
Row and Column Totals Agree
A row total is a full sweep of the inner loop. So the accumulator is reset in the outer body, and reported there too. That's the same question as always: what does one outer pass accomplish? Here, one branch's total. The branches total 56, 38, and 45. Column totals swap the loops: reset in the outer column loop, and add down the rows. The quarters total 37, 30, 33, and 39. Both sets come to 139. That's a useful check: row totals and column totals of the same table must agree, because both add up the same twelve numbers.
Transposing
Swapping Rows and Columns
Transposing turns rows into columns. The result has its dimensions swapped. A 3 by 4 table transposes into a 4 by 3 one, so it needs a separate destination of the right shape. The loops are ordinary. The subscripts swap on the left: flipped c r equals sales r c. Only a square array can be transposed in place. And even then, visit each pair once. Swapping every cell with its partner swaps each pair twice, and leaves the array exactly as it started.
Extension
Adding a Third Dimension
Nothing stops you adding a third set of brackets. The declaration reads from the outside in. Readings 5, 12, 31 means 5 stores, each with 12 months, each with 31 days. The first subscript is which store, the outermost grouping. The second is which month. The third is which day. Store 2, month 6, day 14. The total is the product of all three: 1,860 cells, from a declaration one line long. Traversing it needs three nested loops. Both facts argue for restraint.
Flexible Tables
Vector of Vectors for Unknown Sizes
A fixed table needs both sizes written into the source. When the number of rows or columns isn't known until the program runs, the flexible equivalent is a vector of vectors. Here, grid is 3 rows, each a vector of 4 ints, all set to zero. And it's indexed exactly like an array. What differs is that the structure knows its own dimensions. Grid dot size gives the number of rows, and grid r dot size gives the length of one particular row.
Special Case
Jagged Rows and Row Sizes
That last phrase is deliberate. Because each row is a separate vector, the rows need not all be the same length. A table like that is called jagged. Code that assumes every row is as long as row 0, will read past the end of a shorter one. So ask for this row's size, not row 0's. It costs nothing, and it's always correct.
Comparison
Fixed Table or Vector of Vectors
So, a fixed table, or a vector of vectors? A fixed table's sizes are decided when the program is written. It doesn't know its shape, its rows are always equal, and it sits in one contiguous block. A vector of vectors decides its sizes while it runs, knows its shape at each level, and stores each row separately. Its rows aren't necessarily equal. Use a fixed table when the shape is fixed, like a chessboard. Use a vector of vectors when the shape depends on input. And whichever you use, check both bounds. A correct row with an out-of-range column is just as wrong, and nothing catches it at run time either.
Key Terms
Vocabulary of Tables
A few key terms. A two-dimensional array is a collection indexed by two subscripts, laid out as rows and columns. Row-major order is the storage arrangement in which each complete row is laid down before the next begins. Row-wise traversal puts the row index outside. Column-wise puts the column index there. A transpose exchanges rows and columns. And a jagged table is a vector of vectors whose rows differ in length.
Summary and Quiz
Recap and a 6 by 9 Check
To summarize. Declare rows first, then columns, and give starting values row by row. Index row first, then column, in separate brackets. Tables are stored in row-major order, at position row times columns plus column. Row and column totals must agree. And use a vector of vectors when the shape isn't fixed. Here's something to think about. For int t, 6 by 9, how many cells are there, and what are the valid index ranges? And where does row 2, column 1 sit in memory? Pause, and work it out. Six times nine: 54 cells. Rows run 0 to 5, columns 0 to 8. And row 2, column 1 sits at position 2 times 9, plus 1: position 19. That is how a two-dimensional array sits in memory.
About C++ Programming at UPI Study
C++ Programming (Computer Science 242) is a self-paced online course of 84 video lessons in 11 chapters, from your first program to decisions, loops, arrays, functions, classes, files, pointers and inheritance. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take C++ Programming with UPI Study
Where the credit goes
Universities that work with NCCRS
C++ Programming carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Multi-Dimensional Arrays
How do you declare and initialize a two-dimensional array in C++?
How do you access one element of a 2D array, and why does grid[1, 2] not work?
What is row-major order, and how do you find where a cell sits in memory?
How do you transpose a 2D array in C++?
About the C++ Programming course
How many college credits is C++ Programming?
How much does C++ Programming cost and what is included?
Which universities accept UPI Study credits?
How long does C++ Programming take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in C++ Programming.
84 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →