August 1997/Standard C/C++

Columns

Standard C/C++

P. J. Plauger

The Header <valarray>

C++ has arrays and strings, much like C. STL adds vectors, lists, deques, and trees. But template class valarray supplies yet another way to implement a sequence of elements.

Introduction

I continue my wrapup of the draft Standard C++ library with a peek into one of its darker corners. The header <valarray> defines the template class valarray, and a host of supporting templates and classes. As the name loosely implies, a valarray object stores an array of "value" elements — specific numeric values.

Even more specifically, the values are assumed to be of some floating-point type, or at least a type that behaves very much like floating point. For example, the type complex<float>, which specializes the template class complex defined in the header of the same name, meets the requirements for the valarray type parameter. If you want to specialize valarray for a class of your own devising, however, be careful to define all the operators you're likely to use, inadvertently or otherwise.

The C++ language inherits arrays from C, of course. The draft Standard C++ library also has the template classes basic_string and vector, not to mention several other ways to represent sequences. So why does the library also need valarray?

One easy answer is that it doesn't. valarray was proposed before the Standard Template Library was voted into the draft, way back in 1993. It was tabled at the time on the (proper) grounds that it was a major addition to the library, with only limited field experience, rather late in the standardization process. Then in July 1994 STL was voted in — a substantially larger and later addition to the draft. At the same meeting, the Library Subcommittee voted to untable the valarray proposal and toss it in as well, almost as an afterthought and with hardly any discussion.

The people who care about valarray are the numerical programming types. In its current form, the template class is largely based on experience at Sandia Labs. The idea is to provide a generic numeric array that is easily resized and that predefines all the common mathematical operators on corresponding pairs of elements. Thus:
valarray<float> x1, x2;
.....
x1 += x2;
would add each element x2[i] into x1, assuming the two arrays have the same number of elements.

What's more, a valarray object can be easily sliced and diced in the various ways numerical programmers are wont to do. And operations on such objects should be easily "vectorized" — C++ compilers extended to support parallel-processing architectures should be able to take advantage of vector arithmetic units when implementing valarray operations.

The draft C++ Standard explicitly relaxes the usual sequencing and aliasing rules for accesses to elements of a valarray object. You as programmer have to assume that operations on multiple elements of such an object can occur in arbitrary order.

Some people believe that valarray is in the Standard for the sole purpose of permitting compilers to generate special code. They see no use for a "vanilla" implementation of this template class, other than to satisfy some abstract conformance requirement, perhaps.

I disagree. I believe that valarray offers indexing (slicing) operations that are of interest even without any compiler or hardware performance boost. It was a real challenge to write this template class. I've stressed several compilers to the breaking point in the process of proving it in and making it portable.

It is a very difficult template class to understand. Don't worry if you can't understand much of it on the first few readings. I know I couldn't. It also involves a lot of repetitious code, most of which I've omitted from the presentation here. And I've made heavy use of macros to keep the repetition to a minimum. See the header shipped with Microsoft VC++ V4.2 or V5.0 for the whole story.

Template Class valarray

Listing 1 shows the definition of template class valarray. The template class describes an object that controls a varying-length sequence of elements of type T. The sequence is stored as an array of T. It differs from template class vector in two important ways:

It defines numerous arithmetic operations between corresponding elements of valarray<T> objects of the same type and length, such as x = cos(y) + sin(z).

It defines a variety of interesting ways to subscript a valarray<T> object, by overloading operator[].

In many ways, valarray resembles template class vector. (See "Standard C/C+: The Header <vector>," CUJ, January 1997.) The most distinctive addition is the appearance of four auxiliary template classes: slice_array, gslice_array, mask_array, and indirect_array. They provide various ways of slicing a valarray object, through the magic of constructors, the assignment operator, and the subscript operator. We'll examine each of these funny creatures in turn.

Note the use of several macros as shorthand for various kinds of loops over the elements of a valarray object. You see a few examples of their use within the template class definition proper. They occur many times in the header <valarray>, at least the way I've implemented it.

Listing 2 provides a small sample. It shows all the template function definitions required just for multiplication. And it shows one math function overloaded for valarray. You can imagine the real estate consumed in the header <valarray> defining all the other operators and math functions this way.

Not all the member functions for valarray are defined within the template class definition. Some really nasty forward referencing problems make it essentially impossible to define all of valarray in one lump. We will revisit the more interesting assignment and subscripting operators later.

Simple Slicing

The simplest way to slice an array follows the pattern of a Fortran DO loop. You specify

a starting index

a total length

a stride, or distance between subsequent indices

Listing 3 shows the class slice, which stores these three items. There's not much to it.

If you use a slice object as a subscript to a valarray object, the result is an object of template class slice_array. Listing 4 shows the definition of this template class. The class describes an object that stores a reference to an object x of class valarray<T>, along with an object sl of class slice which describes the sequence of elements to select from the valarray<T> object.

You construct a slice_array<T> object only by writing an expression of the form x[sl]. The member functions of class slice_array then behave like the corresponding function signatures defined for valarray<T>, except that only the sequence of selected elements is affected.

The sequence consists of sl.size() elements, where element i becomes the index sl.start() + i * sl.stride() within x. For example:
// x[slice(2, 5, 3)] selects elements with
//   indices 2, 5, 8, 11, 14
You can also make a more general slice, consisting of multiple triples of the slice variety. This is not the same as defining a slice through a multidimensional array — it is much more general — but it can be made to look like such a slice with careful attention to the indexing arithmetic.

Listing 5 shows the class gslice. The class stores the parameters that characterize a gslice_array when an object of class gslice appears as a subscript for an object of class valarray<T>. The stored values include:

a starting index

a length vector of class valarray<size_t>

a stride vector of class valarray<size_t>

The two vectors must have the same length.

Listing 6 shows the template class gslice_array. The class describes an object that stores a reference to an object x of class valarray<T>, along with an object gs of class gslice which describes the sequence of elements to select from the valarray<T> object.

You construct a gslice_array<T> object only by writing an expression of the form x[gs]. The member functions of class gslice_array then behave like the corresponding function signatures defined for valarray<T>, except that only the sequence of selected elements is affected.

The sequence is determined as follows. For a length vector gs.size() of length N, construct the index vector valarray<size_t> idx(0, N). This designates the initial element of the sequence, whose index k within x is given by the mapping:
k = start;
for (size_t i = 0; i < gs.size()[i]; ++i)
    k += idx[i] * gs.stride()[i];
The successor to an index vector value is given by:
for (size_t i = N; 0 < i--; )
    if (++idx[i] < gs.size()[i])
        break;
    else
        idx[i] = 0;
For example:
const size_t lv[] = {2, 3};
const size_t dv[] = {7, 2};
const valarray<size_t> len(lv, 2), str(dv, 2);
// x[gslice(3, len, str)] selects elements with
//   indices 3, 5, 7, 10, 12, 14
Masking and Indirection

Yet another way of selecting elements from an object of class valarray<T> involves the use of a mask array. Each bit in the mask array selects whether to include the corresponding element of the underlying valarray<T> object.

Listing 7 shows the template class mask_array, which performs this service. The class describes an object that stores a reference to an object x of class valarray<T>, along with an object ba of class valarray<bool> which describes the sequence of elements to select from the valarray<T> object.

You construct a mask_array<T> object only by writing an expression of the form x[ba]. The member functions of class mask_array then behave like the corresponding function signatures defined for valarray<T>, except that only the sequence of selected elements is affected.

The sequence consists of at most ba.size() elements. An element j is included only if ba[j] is true. Thus, there are as many elements in the sequence as there are true elements in ba. If i is the index of the lowest true element in ba, then x[i] is element zero in the selected sequence. For example:
const bool vb[] = {false, false, true, true, false, true};
// x[valarray<bool>(vb, 56)] selects elements with
//   indices 2, 3, 5
Still another selection technique involves indirection. You specify a vector of indexes which in turn select the corresponding elements to include from the underlying valarray<T> object.

Listing 8 shows the template class indirect_array, which performs this service. The class describes an object that stores a reference to an object x of class valarray<T>, along with an object xa of class valarray<size_t> which describes the sequence of elements to select from the valarray<T> object.

You construct an indirect_array<T> object only by writing an expression of the form x[xa]. The member functions of class indirect_array then behave like the corresponding function signatures defined for valarray<T>, except that only the sequence of selected elements is affected.

The sequence consists of xa.size() elements, where element i becomes the index xa[i] within x. For example:
const size_t vi[] = {7, 5, 2, 3, 8};
// x[valarray<size_t>(vi, 5)] selects elements with
//   indices 7, 5, 2, 3, 8
Subscripting

With those elaborate preliminaries out of the way, we can now revisit assignment and subscripting in template class valarray. Listing 9 shows the definitions of the member function operators. These operators, the constructors for valarray, and the auxiliary templates and classes described earlier all work together to provide the clever subscripting tricks described earlier. Here is a brief summary of what you can do with operator[]:
T& operator[](size_t n);
The member operator selects element n. For example:
valarray<char> v0("abcdefghijklmnop", 16);
v0[3] = 'A';
// v0 == valarray<char>("abcAefghijklmnop", 16)
slice_array<T> operator[](slice sa);
The member operator selects those elements of the controlled sequence designated by sa. For example:
valarray<char> v0("abcdefghijklmnop", 16);
valarray<char> v1("ABCDE", 5);
v0[slice(2, 5, 3)] = v1;
// v0 == valarray<char>("abAdeBghCjkDmnEp", 16)

gslice_array<T> operator[](const gslice& ga);
The member operator selects those elements of the controlled sequence designated by ga. For example:
valarray<char> v0("abcdefghijklmnop", 16);
valarray<char> v1("ABCDEF", 6);
const size_t lv[] = {2, 3};
const size_t dv[] = {7, 2};
const valarray<size_t> len(lv, 2), str(dv, 2);
v0[gslice(3, len, str)] = v1;
// v0 == valarray<char>("abcAeBgCijDlEnFp", 16)

mask_array<T> operator[](const valarray<bool>&ba);
The member operator selects those elements of the controlled sequence designated by ba. For example:
valarray<char> v0("abcdefghijklmnop", 16);
valarray<char> v1("ABC", 3);
const bool vb[] =
    {false, false, true, true, false, true};
v0[valarray<bool>(vb, 6)] = v1;
// v0 == valarray<char>("abABeCghijklmnop", 16)

indirect_array<T> operator[](const valarray<size_>& xa);
The member operator selects those elements of the controlled sequence designated by ia. For example:
valarray<char> v0("abcdefghijklmnop", 16);
valarray<char> v1("ABCDE", 5);
const size_t vi[] = {7, 5, 2, 3, 8};
v0[valarray<size_t>(vi, 5)] = v1;
// v0 == valarray<char>("abCDeBgAEjklmnop", 16)
A second group of five member operators each construct an object that represents the value(s) selected. The selected elements must exist.
T operator[](size_t n) const;
The member operator returns the value of element n. For example:
valarray<char> v0("abcdefghijklmnop", 16);
// v0[3] returns 'd'

valarray<T> operator[](slice sa) const;
The member operator returns an object of class valarray<T> containing those elements of the controlled sequence designated by sa. For example:
valarray<char> v0("abcdefghijklmnop", 16);
// v0[slice(2, 5, 3)] returns valarray<char>("cfilo", 5)

valarray<T> operator[](const gslice& ga) const;
The member operator selects those elements of the controlled sequence designated by ga. For example:
valarray<char> v0("abcdefghijklmnop", 16);
const size_t lv[] = {2, 3};
const size_t dv[] = {7, 2};
const valarray<size_t> len(lv, 2), str(dv, 2);
// v0[gslice(3, len, str)] returns
//    valarray<char>("dfhkmo", 6)

valarray<T> operator[](const valarray<bool>& ba) const;
The member operator selects those elements of the controlled sequence designated by ba. For example:
valarray<char> v0("abcdefghijklmnop", 16);
const bool vb[] = {false, false, true, true, false, true};
// v0[valarray<bool>(vb, 6)] returns
//    valarray<char>("cdf", 3)

valarray<T> operator[](const valarray<size_t>& xa) const;
The member operator selects those elements of the controlled sequence designated by ia. For example:
valarray<char> v0("abcdefghijklmnop", 16);
const size_t vi[] = {7, 5, 2, 3, 8};
// v0[valarray<size_t>(vi, 5)] returns
//    valarray<char>("hfcdi", 3)
If you can understand these ten examples, you will understand valarray. You might even be inspired to think of some clever uses for it. o

P.J. Plauger is Senior Editor of C/C++ Users Journal and President of Dinkumware, Ltd. He is the author of the Standard C++ Library shipped with Microsoft's Visual C++, v5.0. For eight years, he served as convener of the ISO C standards committee, WG14. He remains active on the C++ committee, WG21. His latest books are The Draft Standard C++ Library, Programming on Purpose (three volumes), and Standard C (with Jim Brodie), all published by Prentice-Hall. You can reach him at pjp@plauger.com.