Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

Non STL containers

There are two non-STL containers in the standard library: bitset and valarray.[116] 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
#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

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 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>
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

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire