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 **valarray**s, 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 **valarray**s
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 **valarray**s 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 |