| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
There are two non-STL containers in the standard library: bitset and valarray. We
say non-STL because neither of these containers fulfills all the requirements
of STL containers. The bitset container, which we covered earlier in
this chapter, packs bits into integers and does not allow direct addressing of
its members. The valarray template class is a vector-like
container that is optimized for efficient numeric computation. Neither
container provides iterators. Although you can instantiate a valarray
with nonnumeric types, it has mathematical functions that are intended to
operate with numeric data, such as sin, cos, tan, and so
on.
Here s a tool to print elements in a valarray:
//: C07:PrintValarray.h
#ifndef PRINTVALARRAY_H
#define PRINTVALARRAY_H
#include <valarray>
#include <iostream>
#include <cstddef>
template<class T>
void print(const char* lbl, const
std::valarray<T>& a) {
std::cout << lbl << ": ";
for(std::size_t i = 0; i < a.size(); ++i)
std::cout << a[i] << ' ';
std::cout << std::endl;
}
#endif // PRINTVALARRAY_H ///:~
Most of valarray s functions and operators operate on
a valarray as a whole, as the following example illustrates:
//: C07:Valarray1.cpp {-bor}
// Illustrates basic valarray functionality.
#include "PrintValarray.h"
using namespace std;
double f(double x) { return 2.0 * x - 1.0; }
int main() {
double n[] = { 1.0, 2.0, 3.0, 4.0 };
valarray<double> v(n, sizeof n / sizeof n[0]);
print("v", v);
valarray<double> sh(v.shift(1));
print("shift 1", sh);
valarray<double> acc(v + sh);
print("sum", acc);
valarray<double> trig(sin(v) + cos(acc));
print("trig", trig);
valarray<double> p(pow(v, 3.0));
print("3rd power", p);
valarray<double> app(v.apply(f));
print("f(v)", app);
valarray<bool> eq(v == app);
print("v == app?", eq);
double x = v.min();
double y = v.max();
double z = v.sum();
cout << "x = " << x <<
", y = " << y
<< ", z = " << z <<
endl;
} ///:~
The valarray class provides a constructor that takes
an array of the target type and the count of elements in the array to
initialize the new valarray. The shift( ) member function
shifts each valarray element one position to the left (or to the right,
if its argument is negative) and fills in holes with the default value for the
type (zero in this case). There is also a cshift( ) member function
that does a circular shift (or rotate ). All mathematical operators and
functions are overloaded to operate on valarrays, and binary operators
require valarray arguments of the same type and size. The apply( )
member function, like the transform( ) algorithm, applies a
function to each element, but the result is collected into a result valarray.
The relational operators return suitably-sized instances of valarray<bool>
that indicate the result of element-by-element comparisons, such as with eq
above. Most operations return a new result array, but a few, such as min( ),
max( ), and sum( ), return a single scalar value, for
obvious reasons.
The most interesting thing you can do with valarrays
is reference subsets of their elements, not only for extracting information,
but also for updating it. A subset of a valarray is called a slice, and certain operators use slices to do their work. The following sample program
uses slices:
//: C07:Valarray2.cpp {-bor}{-dmc}
// Illustrates slices and masks.
#include "PrintValarray.h"
using namespace std;
int main() {
int data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
};
valarray<int> v(data, 12);
valarray<int> r1(v[slice(0, 4, 3)]);
print("slice(0,4,3)", r1);
// Extract conditionally
valarray<int> r2(v[v > 6]);
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 means you can 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
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 expected
to be equal. 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, you can not only pass any size matrix,
but you can also easily process matrices of any type, and return the result by
value. Here s how:
//: C07:MatrixMultiply.cpp
// Uses valarray to multiply matrices
#include <cassert>
#include <cstddef>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <valarray>
using namespace std;
// Prints a valarray as a square matrix
template<class T>
void printMatrix(const valarray<T>& a, size_t
n) {
size_t siz = n*n;
assert(siz <= a.size());
for(size_t i = 0; i < siz; ++i) {
cout << setw(5) << a[i];
cout << ((i+1)%n ? ' ' : '\n');
}
cout << endl;
}
// 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;
}
int main() {
const int n = 3;
int adata[n*n] = {1,0,-1,2,2,-3,3,4,0};
int bdata[n*n] = {3,4,-1,1,-3,0,-1,1,2};
valarray<int> a(adata, n*n);
valarray<int> b(bdata, n*n);
valarray<int> c(matmult(a, n, n, b, n, n));
printMatrix(c, n);
} ///:~
Each entry in the result matrix c 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.
| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
