Well, they aren't. A table-top is two dimensional and a block of ice is three dimensional. So, how can we model physical situations like heat flow in multiple dimensions, when all C++ seems capable of is 1D lists?!
Boy...you need to calm down. Cut back on the caffeine. Don't worry, we'll simply extend the vector mechanism to multiple dimensions...
Declaring a multi-dimensional vector is as easy as filling in a base type for any vector:
vector<char> line; // 1D vector — one row of char's
vector< vector<double> > tableTop; // 2D storage
// — rows each with columns
// (#rows * #cols items)
vector< vector< vector<bool> > > votes; // 3D storage
// — planes each with rows
// each with columns
// (#planes * #rows * #cols total)
Etc. Just keep adding the new dimension around the one(s) we had before. The spaces between the closing >'s is [currently] required, but the space after the opening <'s is optional.
Accessing a single element is done with a sequence of subscripts:
line[i] = 'c'; // set position i to a 'c'
// add neighborhood of 17th element on 5th row
tableTop[3][16] +
tableTop[4][15] + tableTop[4][16] + tableTop[4][17] +
tableTop[5][16]
// check vote from fourth district, tenth block, 23rd ballot item
if (votes[3][9][22])
Notice particularly how these subscripts align with the original declarations:
vector< vector<double> > tableTop; tableTop[4][16]
The outer vector is subscripted first — just as it was listed in the declaration. And the inner vector is subscripted second — just like it was mentioned second in the declaration.
We can in general manage this kind of thing more cleanly with loops:
// fill tableTop with information ...somehow...
// now print all elements:
for (vector< vector<double> >::size_type row = 0;
row != tableTop.size(); row++)
{
for (vector<double>::size_type col = 0;
col != tableTop[row].size()-1; col++)
{
cout << tableTop[row][col] << ' ';
}
cout << tableTop[row][tableTop[row].size()-1] << endl;
}
(There would be three loops for the votes processing and only one for the line processing. So one loop per dimension.)
Note how the inner loop's size_type is different from the outer loop's. That's because they traverse different dimensions of the structure — the outer one travels from row to row while the inner one travels from column to column — along each row.
To pass an entire n-dimensional (nD) 'structure' as an actual argument to a function, just list its name:
strip_spaces(line, ...);
updateTemps(tableTop, ...);
winner = check_item(votes, ...);
Of course, the '...' part may need more information when the storage is of a higher dimension (and we are processing a sub-portion of the data):
strip_spaces(line, between_here, and_here, ...);
updateTemps(tableTop, up_left_corner_row, up_left_corner_col,
low_right_corner_row, low_right_corner_col, ...);
winner = check_item(votes, district, block_start, block_end, item, ...);
(Now the '...' is just any other arguments you might need for the function to do its job.)
Formal arguments are only as different as the original declaration:
void strip_spaces(vector<char> & line,
vector<char>::size_type start,
vector<char>::size_type end_before,
EndType from_which_ends);
void updateTemps(vector< vector<double> > & tableTop,
vector< vector<double> >::size_type UL_row,
vector<double>::size_type UL_col,
vector< vector<double> >::size_type LR_row,
vector<double>::size_type LR_col,
const vector< vector<double> > & oldTop);
vector<bool>::size_type
check_item(const vector< vector< vector<bool> > > & votes,
vector< vector< vector<bool> > >::size_type which_dist,
vector< vector<bool> >::size_type from_block,
vector< vector<bool> >::size_type to_block,
vector<bool>::size_type which_item);
Note again the required space between the >'s on the 2D and 3D structures.
We can hide much of this complexity with typedef's! When you are going to be making a 2D structure for double's, you would probably make typedef's similar to these:
// row and 2D structure
typedef vector<double> DBL_Row;
typedef vector< DBL_Row > DBL_2D;
// row size
typedef DBL_2D::size_type D2_row_sz;
// column/element size
typedef DBL_Row::size_type D2_col_sz;
With these in place, the above prototype would have been much simpler:
void updateTemps(DBL_2D & tableTop,
D2_row_sz UL_row, D2_col_sz UL_col,
D2_row_sz LR_row, D2_col_sz LR_col,
const DBL_2D & oldTop);
Also note that, as with simple 1D vectors, nD vector storage can use fewer elements along each dimension than are present. (Hence the extra arguments in the above functions to show how many items are in use along each dimension.) And, naturally extending from 1D vectors, each dimension of an nD vector structure needs its own loop during processing. (So a 2D structure needs 2 loops. A 3D structure needs 3 loops. Etc.) Although we saw an example above, there'll be more on this soon...
Multiple dimensions does help us to see a growing pattern, however. When we access a vector structure with a full set of positions (one for each dimension), we retrieve a single element. When we use no positions to access such a structure, we are using the entire structure (note the function calls above). With a 1D vector structure, these were the only two possibilities: one or no 'index'. But with 2 and higher dimensions, we have other possibilities:
line[i] | tableTop[r][c] | votes[d][b][i] | single element line | tableTop[r] | votes[d][b] | a row (1D result) -NA- | tableTop | votes[d] | a plane (2D result) line | tableTop | votes | whole vector
Weird! By using fewer positions than indicated by the vector structure's dimension, you can access entire sub-structures of fewer dimensions than the original!
What exactly are the data types of the resulting vector structures?
line vector<char>
line[i] char
-------------------------------------------------------------
tableTop vector< vector<double> >
tableTop[r] vector<double>
tableTop[r][c] double
-------------------------------------------------------------
votes vector< vector< vector<bool> > >
votes[d] vector< vector<bool> >
votes[d][b] vector<bool>
votes[d][b][i] bool
Wow! By subscripting, you remove a dimension off the outside. Just the reverse of when we extended our vector's dimensions: we added the new dimensions to the outside.
NOTE: More to come...
Given an n-dimensional vector, how do you process its elements? Well, for each dimension you have, you'll require at least one (1) loop to move an index along that dimension. Also note that each dimension will need its own 'index'. We saw an example of how to print the elements in a 2D vector earlier. Let's examine it in more detail:
vector< vector<double> > tableTop; // 2D storage
// — rows each with columns
// (#rows * #cols items)
// fill in data as desired/needed
// now print all elements:
for (vector< vector<double> >::size_type row = 0;
row != tableTop.size(); row++)
{
for (vector<double>::size_type col = 0;
col != tableTop[row].size()-1; col++)
{
cout << tableTop[row][col] << ' ';
}
cout << tableTop[row][tableTop[row].size()-1] << endl;
}
First let's clean it up with our typedef's:
// after <vector> has been #include'd
typedef vector<double> DBL_Row;
typedef vector< DBL_Row > DBL_2D;
typedef DBL_2D::size_type D2_row_sz;
typedef DBL_Row::size_type D2_col_sz;
// in some function's code:
DBL_2D tableTop; // 2D storage — rows each with columns
// (#rows * #cols items)
// fill in data as desired/needed
// now print all elements:
for (D2_row_sz row = 0; row != tableTop.size(); row++)
{
for (D2_col_sz col = 0; col != tableTop[row].size()-1; col++)
{
cout << tableTop[row][col] << ' ';
}
cout << tableTop[row][tableTop[row].size()-1] << endl;
}
Note how we print all the columns on each row in turn. Each row ends in a new-line. (The last data item is actually printed after the columns loop so that we don't print a space AND a new-line after the last item in the row.)
Here's another example where we multiply all elements of a 2D vector by a scalar (that's what matrix mathematicians call a number):
DBL_2D land_profile;
double erosion_factor;
// fill in land_profile
// determine erosion_factor
for (D2_row_sz wid = 0; wid != land_profile.size(); wid++)
{
for (D2_col_sz len = 0; len != land_profile[wid].size(); len++)
{
land_profile[wid][len] *= erosion_factor;
}
}
Notice how you can even use the short-cut assignment operators with the elements of the vector. When you use two levels of subscripts (here via the nested loops) on a 2D vector structure, you have an individual element which is an individual memory location of the overall base type. You can do anything to this memory location that you could do to a regular variable of that type.
Perhaps, though, you've noticed that the above examples have shown declarations and processing loops but not the input of the information. How is this accomplished? Well, first let's recall our 1D input forms. We had flagged termination:
vector<string> data;
string t;
cout << "Enter data (~quit~ to end): ";
cin >> t;
while (data.size()+1 != data.max_size() // still room for another
&& t != "~quit~") // and haven't terminated
{
data.push_back(t);
cin >> t;
}
Here we pick a special value that won't be part of the data and stopped when we detected that value had been entered. (This can work for numeric data where certain values are not allowed: time cannot be negative, grades should not be negative, etc.)
But there was also fail() and eof() detection (you can only use fail() with numeric data — neither char's nor string's can cause failure!):
vector<double> data;
double t;
cout << "Enter your values (q to end): ";
cin >> t;
while (data.size()+1 != data.max_size() // still room for another
&& !cin.fail() // and still numeric
&& !cin.eof()) // and not end-of-'file'
{
data.push_back(t);
cin >> t;
}
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
Again, if the data were string like in the first example (or char), we could not have used the fail() check (effectively; we could check it, but it would never be true...). We can, however, combine the last two conditions under one test. If cin hasn't failed and isn't at the end of the 'file', it is good:
vector<double> data;
double t;
cout << "Enter your values (q to end): ";
cin >> t;
while (data.size()+1 != data.max_size() // still room for another
&& cin.good()) // and all's well
{
data.push_back(t);
cin >> t;
}
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
We also had end-of-line termination and pre-counted entry forms. (Remember to make sure the pre-counted count is sensible before you try to resize() the vector to that size — if you are displaying a line on the screen, it had better fit, for instance.)
So, how do we extend these to 2D (or higher) input forms? Well, the pre-counted form should be self-explanatory. I'll just caution you to sanity check each dimension separately.
The sentinel forms can be extended in one of two ways (typically). In the first you use a sentinel on the first row of input to find out how many columns. Then you simply read further rows — knowing how long each will be — until you find a second sentinel — which will signal the end of the rows. For example:
1 2 3 4 x
3 2 4 1
6 7 3 2
2 2 3 5
4 4 4 1 x
After the first fail() with the 'x' we know the number of columns is 4 and so we proceed to read all rows after that as having 4 elements. When we fail() again, we know that was the last row and we are done!
The second way involves every line ending in a sentinel. This means the rows will end when two sentinels in a row (pardon the pun) are detected. For example:
1 2 3 4 x
3 2 4 1 x
6 7 3 2 x
2 2 3 5 x
4 4 4 1 x x
Here we are looking for a sentinel to end each row and two to end the vector structure overall. What possible advantage does this have? Well, it is simpler to code for one. For another it allows flexibility such as this ragged data:
1 2 3 4 x
3 2 x
6 7 3 2 5 5 x
2 2 3 5 x
4 4 4 1 2 x x
Here the user has rows which have differing amounts of data in them. Since during processing we know each row begins at 0 and we ask each row for its size() individually, this will cause no problems later in the code. Just remember that many standard 2D algorithms assume a rectangular structure for 2D processing!
This is by no means a complete discussion of the topic, but it should suffice you for a semester or two until you are comfortable enough with multiple dimensions to get creative with it.
Here is the sample code from lecture that implements the first of these techniques.
...simulation, time, virtual dims...
...row-major, column-major, diagonal, surrounding sub-structure...
...max/min, search, sum...
...col extr...
For bits on all those '...' notes above, see these notes from lecture.
...matrix multiply, cross-product...