print("elements > 6", r2);
// Square first column
v[slice(0, 4, 3)] *= valarray<int>(v[slice(0, 4, 3)]);
print("after squaring first column", v);
// Restore it
int idx[] = {1,4,7,10};
valarray<int> save(idx, 4);
v[slice(0, 4, 3)] = save;
print("v restored", v);
// Extract a 2-d subset: {{1, 3, 5}, {7, 9, 11}}
valarray<size_t> siz(2);
siz[0] = 2;
siz[1] = 3;
valarray<size_t> gap(2);
gap[0] = 6;
gap[1] = 2;
valarray<int> r3(v[gslice(0, siz, gap)]);
print("2-d slice", r3);
// Extract a subset via a boolean mask (bool elements)
valarray<bool> mask(false, 5);
mask[1] = mask[2] = mask[4] = true;
valarray<int> r4(v[mask]);
print("v[mask]", r4);
// Extract a subset via an index mask (size_t elements)
size_t idx2[] = {2,2,3,6};
valarray<size_t> mask2(idx2, 4);
valarray<int> r5(v[mask2]);
print("v[mask2]", r5);
// Use an index mask in assignment
valarray<char> text("now is the time", 15);
valarray<char> caps("NITT", 4);
valarray<size_t> idx3(4);
idx3[0] = 0;
idx3[1] = 4;
idx3[2] = 7;
idx3[3] = 11;
text[idx3] = caps;
print("capitalized", text);
} ///:~
A slice object takes three arguments: the starting index, the number of elements to extract, and the "stride," which is the gap between elements of interest. Slices can be used as indexes into an existing valarray, and a new valarray containing the extracted elements is returned. A valarray of bool, such as is returned by the expression v > 6, can be used as an index into another valarray; the elements corresponding to the true slots are extracted. As you can see, you can also use slices and masks as indexes on the left side of an assignment. A gslice object (for "generalized slice") is like a slice, except that the counts and strides are themselves arrays, which allows you to interpret a valarray as a multidimensional array. The example above extracts a 2 by 3 array from v, where the numbers start at zero and the numbers for the first dimension are found six slots apart in v, and the others two apart, which effectively extracts the matrix
1 3 5
7 9 11
Here is the complete output for this program:
slice(0,4,3): 1 4 7 10
elements > 6: 7 8 9 10
after squaring v: 1 2 3 16 5 6 49 8 9 100 11 12
v restored: 1 2 3 4 5 6 7 8 9 10 11 12
2-d slice: 1 3 5 7 9 11
v[mask]: 2 3 5
v[mask2]: 3 3 4 7
capitalized: N o w I s T h e T i m e
A practical example of slices is found in matrix multiplication. Consider how you would write a function to multiply two matrices of integers with arrays.
void matmult(const int a[][MAXCOLS], size_t m, size_t n,
const int b[][MAXCOLS], size_t p, size_t q,
int result[][MAXCOLS);
This function multiplies the m-by-n matrix a by the p-by-q matrix b, where n and p are equal, of course. As you can see, without something like valarray, you need to fix the maximum value for the second dimension of each matrix, since locations in arrays are statically determined. It is also difficult to return a result array by value, so the caller usually passes the result array as an argument.
Using valarray not only allows you to pass any size matrix, but you can also easily process matrices of any type, and return the result by value. Here’s how:
// Multiplies compatible matrices in valarrays
template<class T>
valarray<T> matmult(const valarray<T>& a, size_t arows,
size_t acols, const valarray<T>& b,
size_t brows, size_t bcols) {
assert(acols == brows);
valarray<T> result(arows * bcols);
for(size_t i = 0; i < arows; ++i)
for(size_t j = 0; j < bcols; ++j) {
// Take dot product of row a[i] and col b[j]
valarray<T> row = a[slice(acols*i, acols, 1)];
valarray<T> col = b[slice(j, brows, bcols)];
result[i*bcols + j] = (row * col).sum();
}
return result;
}
Each entry in the result matrix is the dot product of a row in a with a column in b. By taking slices, you can extract these rows and columns as valarrays and use the global * operator and sum( ) function provided by valarray to do the work succinctly. The result valarray is computed at runtime; there’s no need to worry about the static limitations of array dimensions. You do have to compute linear offsets of the position [i][j] yourself (see the formula i*bcols + j above), but the size and type freedom is worth it.
Summary
The goal of this chapter was not just to introduce the STL containers in some considerable depth. (Of course, not every detail could be covered here, but you have enough now that you can look up further information in the other resources.) Our higher hope is that this chapter has made you grasp the incredible power available in the STL and shown you how much faster and more efficient your programming activities can be by using and understanding the STL.
Exercises
1. Create a set<char>, open a file (whose name is provided on the command line), and read that file in a char at a time, placing each char in the set. Print the results, and observe the organization. Are there any letters in the alphabet that are not used in that particular file?
39. Create three sequences of Noisy objects, a vector, deque, and list. Sort them. Now write a function template to receive the vector and deque sequences as a parameter to sort them and record the sorting time. Write a specialized template function to do the same for list (ensure to call its member sort( ) instead of the generic algorithm). Compare the performance of the different sequence types.
40. Write a program to compare the speed of sorting a list using list::sort( ) vs. using std::sort( ) (the STL algorithm version of sort( )).
41. Create a generator that produces random int values between 0 and 20 inclusive, and use it to fill a multiset<int>. Count the occurrences of each value, following the example given in MultiSetWordCount.cpp.