A Proposal for Standard C++ Array Classes Technical Report 93-08 Al Vermeulen Rogue Wave Software, Inc. PO Box 2328 Corvallis OR 97339 (503) 754-3010 Copyright (c) Rogue Wave Software, Inc. 1993 1.0. What are arrays? Arrays are simple, ordered collections of objects - the most fundamental aggregate data structure used in programming. The mechanisms built in to C for describing and manipulating arrays are weak at best: there is no support for dynamic sizing and resizing, manipulating arrays as a single unit, extraction and manipulation of subarrays, or bounds checking. Fortunately, we can use the C++ class mechanism to construct C++ array types that do have these properties. In an effort to avoid duplicating effort, and to aid in porting code, we propose that the model and interface proposed in this paper be adopted as a minimal standard. The classes described in this paper are based on the Rogue Wave Math.h++ array classes; they are the result of over five years of experimentation and the experience of thousands of users. Before we can decide on an interface, we need to decide precisely what an array is. We define an array as a rectangular grid of objects. The grid doesnt have to be two dimensional: it can be one, two, three, or even n-dimensional. Every object in the array is explicitly represented, and each is unique in the sense that it has a unique address. Every object in the array has a unique index; the index consists of as many integers as the array has dimensions. Every array object is of the same type (so you have to use pointers or some other means of indirection for heterogeneous arrays). One and two dimensional arrays are used so frequently that we give them special names: a one dimensional array is a vector, and a two dimensional array is a general matrix. We do not consider the question of representing matrices more abstract than two dimensional arrays, for example representing symmetric or band matrices. This is a separate issue, and, if there is interest, we could be persuaded to write a separate proposal on a standard interface to these abstractions. 1.1. Fortran 90 arrays It is often considered heresy to propose that the C++ community could learn something from Fortran. In the case of arrays, however, Fortran, more specifically Fortran 90, is clearly several steps ahead of C. For example, in Fortran 90 the size of a two dimensional array can be set at run time like this INTEGER N ... set N ... REAL A(N,N) Arrays can be used in expressions; the expression is applied to each element of the array, as in A = B + C * SIN(D) One of the nicest features of Fortran 90 arrays is that rectangular subarrays, called sections, can be extracted and themselves used as arrays. So to pass a vector containing the fourth row of A to a subprogram you do this CALL FOO(A(4,:)) and to set a matrix equal to an upper submatrix, you might say U = A(1:4,1:4) A section can also be extracted with non-unit spacing between the selected elements. Thus, the following selects every other element in a length 10 vector V(1:10:2) The data in a section is the same data as in the original array. Although it sounds like this has the potential to be confusing - two arrays referencing the same data  this is what gives the idea of a section power: it can be used to change a section of data in an array with one statement. Also, because both the array and the section use the same data, creating a section is fast  no data need be copied. This model of arrays is simple, intuitive and powerful. While the Fortran definition holds only for numerical arrays, the model is also useful for non-numerical types: it is easy to imagine setting up a 3-D array of objects representing finite volumes in a 3-D computational fluid dynamics code and then using the concept of a section to consider a volume and its immediate neighbours. 2.0. Model We propose adopting the Fortran 90 model of an array as the underlying foundation of our C++ classes. The ideas of dynamic run time sizing, copy by reference, and sections will provide us with the power and efficiency necessary for both numerical and non-numerical appli- cations. 2.1. Data-view model The idea that more than one array can refer to the same data is central to the model we have chosen. It seems sensible to consider an array as two parts: a shared part holding the data, and a non-shared part representing the array itself. We refer to these two parts as the data and view. An array, then, is a view into a block of data. By using sections and copies we can construct multiple arrays, all of which could be views into the same data. 2.2. Classes We propose 6 template classes as the interface to the array model. The classes are shown in the following table. Vector (1-D) General Matrix (2-D) Array (3,4-D) General data Vec GenMat Array Numeric data NumVec NumGenMat NumArray Operations valid for numeric arrays are a superset of operations valid for arrays of general objects. The important difference is that the standard arithmetic operators are overloaded for the numerical array classes. The two-tiered approach allows us to use exactly the same model for both numeric and non-numeric arrays, while also allowing us to standardize on operators and functions for the numeric types. It would be possible to dispense with the vector and general matrix classes, and simply add the functionality of one and two dimensional arrays to the array classes. However, there are several advantages to having vector and matrix classes distinct from array classes: - Objects representing vector or matrix views can be made smaller and much more efficient than the more general array view objects. This is especially important for operations on numerical vectors and matrices where the compiler might be able to use the simpler structure of a vector, say, to generate optimized, even vectorized, code. - Use of vectors and matrix classes increases the ability of the compiler to check code at compile time. If you try to pass a 1-D vector to a routine expecting a 2-D general matrix, this can be caught before runtime only if separate types are used for vectors and matrices. - Vectors and matrices are such important special cases of arrays that many programmers will simply never need to know about the existence of the more general array classes. Having special 1 and 2 dimensional types makes things simpler for these users. Why not have special classes for 3 and 4 dimensional arrays as well? We decided that although 1 and 2 dimensional arrays are important enough to merit special classes, arrays of higher dimension are not. Also, by requiring that the Array class handle arrays of varying dimensions an obvious place is provided for adding arbitrary dimension functionality, or at least for extending these classes to more than four dimensions. 2.3. Why not a simpler model? It has been suggested that C++ should adopt a simpler, one dimensional, standard array class, and that this class could serve as a building block for higher dimensional classes. The proposed vector class would have a rich set of operations and member functions built in to allow operations which act on all elements at once. Unfortunately, such an abstraction is not powerful enough to seve as a building block for the array classes required by many programmers. The fundamental problem is that the built in operations act on all the elements at once; whereas a multi-dimensional array abstraction which allows operations on sections requires the ability to operate only on parts of the data block. Even adding BLA-like operations to the one dimensional standard class is not sufficient: the data patterns for, say, a two dimensional section of a three dimensional array cannot be described using only the BLAs length and stride parameters. This dismissal of the idea of using a one dimensional standard array class as a building block is based solidly on experience. Originally, the matrix classes of Rogue Waves Math.h++ were implemented using such a vector abstraction. Years of experience convinced us that this approach was too inflexible for constructing the array abstractions we required: in order to address general submatrices, and to implement three and higher dimensional arrays, we needed more sophisticated addressing capabilities than could be reasonably built in to a one dimensional vector abstraction. For this reason, we abandoned the idea of the one dimensional building block and adopted the architecture described in this document. 3.0. General array classes Now that we have identified a model and decided which classes we want to include, it is time to establish what goes into those classes. In this section we consider the minimal set of constructors and member operators valid for all array classes, both numeric and non-numeric. In the last section of this document, header files are given which summarize and make specific the interface. You may find it useful to refer to this while reading the next sections. 3.1. Operations required for element types The intent of the general array classes is to make them useful for arrays of just about anything - strings, finite elements, other arrays - and therefore we must make minimal assumptions about the elements. However, to be suitable as an element, a type must have the following functionality: - default constructor. The class must have a constructor with no arguments, so that uninitialized arrays can be constructed, and so that arrays can be resized. - copy constructor. A copy constructor with well defined semantics (either copy or reference). This can sometimes be generated by the compiler. - assignment operator. The assignment operator can have either copy or reference semantics. This can sometimes be generated by the compiler. Any type with these properties can be used as an element type. Note in particular that all C++ pointer types have the required functionality, so it is always possible to create an array of pointers to any type regardless of what that type may be. 3.2. Constructors There are four types of constructors provided: 1. Default constructors. Vectors and general matrices constructed using the default constructor contain zero elements. In the case of the Array class, the semantics of the default constructor are left undefined: it may construct a zero dimensional (a scalar) array containing a single uninitialized element, or it may construct an array of some number of dimensions with zero elements. In any case, a vector, general matrix, or array created using the default constructor can subsequently be resized or reshaped dynamically. 2. Copy constructors. A copy constructor creates a new view of the same data. Since no data elements need be copied, the copy constructor is efficient. 3. Uninitializing constructors. These constructors allow you to specify the size of the array, and then fill it with uninitialized elements (created using the elements default constructor). In order to avoid ambiguity problems with other constructors, and to avoid undesired automatic type conversion of integers to vectors, the last parameter in this constructors is the variable uninitialized, which is a global variable of enum type Uninitialized. 4. Initializing constructors. These are identical to the uninitialing constructors except that they allow you to specify a value with which to initialize the data in the array. The data is initialized using the elements assignment operator. While it would be nice to use the copy constructor to initialize the elements, unfortunately there is no way in C++ to implement this. 3.3. Subscripting operations The most basic array operation is to extract elements using subscripting. Subscripting is done using the function call operator, (). While the C++ subscript operator, [], would have been a nicer choice, it is, unfortunately, not suitable for arrays of more than one dimension since it cannot be overloaded to take more than one argument. A subscripting operation always returns a rectangular section of the array which refers to the same data as the object being subscripted - it is a new view of the same data. In the simplest case, all the subscripts are integers: the operation returns a reference to a specific element of the array. Although the subscripts are integers, they are of type size_t rather than int. This will accomodate the case when integers are too small to hold all possible subscripts (for example any machine where sizeof(size_t)==sizeof(int) since the integer type can also represent negative numbers). As in C, the first element in a dimension is indexed by zero. Adding a provision to allow indexing from an arbitrary offset is tempting, but causes two sorts of problems: - cost. Adding an offset inceases the time and space cost of the subscripting function. This is especially important because integer subscripting will likely be implemented as an inline function. - complexity. It is unclear what the semantics of a base index should be. In particular, when a binary operation is done on two vectors with the same size but different base indices, should this be a run time error? What should the base of the result be? If arbitrary offsets are very important, it is possible to use the array classes proposed here as building blocks for the construction of arbitrary offset arrays. If more complex sections than a single element are required, it becomes necessary to subscript with something other than just integers. As weve discussed, Fortran 90 allows subscripting with expressions of the form a:b:c to slice through a dimension from a to b with a stride of c. Unfortunately, there are no convenient operators in C++ we can use for this purpose, so a helper class is used. We propose using a class Slice with the following minimal public inter- face: class Slice { public: Slice(size_t start, size_t length, size_t stride=1); }; To construct new sections, you subscript your array with a combination of integers and at least one Slice object. The dimensionality of the returned section depends on the number of integers used: each integer reduces the dimension by one. The type of array returned must correctly reflect the dimension of the section. Thus if A is a four dimensional Array object, the following lines of code return a three dimensional Array, a GenMat, and a Vec respectively. Array = A(Slice(1,2), Slice(1,2), Slice(1,2), 2); GenMat = A(Slice(1,2), Slice(1,2), 3, 4); Vec = A(Slice(1,2), 2, 3, 4); Often, it is desired to access all of the indices in a dimension. For example, you might like to access rows or colums of matrices, or planes in a three dimensional array. To facilitate this, the special subscript All selects all of a given dimension. Thus to access a row or column of an general matrix, or a plane of a 3-D array, you can use Vec = A(2,All); // A row Vec = A(All,2); // A column GenMat = X(All,All,2); // Plane of a 3-D array One possible implementation is to make All an external Slice object with a special flag set. This helps avoid an explosion of possible subscript operators. 3.4. Assignment operator The assignment operator for arrays is implemented using copy semantics. The data itself is changed, not the view. This allows you to change whole subarrays at once by using sections. Assignment is a conformal operator  if the size of the array on the right hand side of the equal sign differs from the size of the array on the left, a run time error occurs. How this error is handled is implementation dependent; for compilers which support it, throwing an exception would be reasonable. The approach of changing the data, not the view, is used so that array sections can be conveniently used as lvalues. For example, consider the code fragment Array A(5,5,5); // A 5x5x5 array GenMat B(5,5); // A 5x5 array A(0,All,All) = B; The intention of the last line is to set the first 5x5 plane of data in A equal to the data in B. The result of the subscripting expression is a temporary 5x5 array which refers to the same data as A; the data in B is then copied over the data refered to by the temporary. If the assignment operator were implemented without copying, that is by simply changing the data block, then the above code would not work as expected: after the assignment statement the temporary would be destroyed and no data would have been altered. There is one exception to the conformal copying rule. If an array has been constructed using the default constructor, and therefore has no associated data, then assignment causes the array to become a view of the right hand sides data. This exception exists so that default construction followed immediately by assignment has the same semantics as copy construction. This special case allows you to construct a C style array of arrays and then initialize them. Thus, the following two code fragments have identical semantics: Array A = t; Array A; A = t; A tricky implementation point is that it may sometimes be necessary to make a copy of the data before doing the assignment in the case when both the left and right side operands are views of the same data block. This is the traditional C pointer aliasing problem. Fortunately, optimization is much simpler for these C++ classes than in the C case, because the C++ case is more structured. As long as both sides are views of separate data blocks, we are guaranteed that no aliasing can take place and so no extra copying is necessary. 3.5. Member functions The following member functions are defined for all array types. - shape inquiry functions: length() for vectors and rows() and cols() for general matrics. For arrays, the function dimension() returns the number of dimensions of the array; the function length(i) returns the size of the ith dimension. - dynamic resizing functions. The reshape function takes the same arguments as the non-initializing constructor. Its effect is to make the view refer to a new block of data of the indicated size. The resize function is the same, except that it copies appropriate entries from the old block to the new one using the assignment operator. - A copy function. The copy() function returns a view which refers to a new block of data. The items in the array are copied over using the assignment operator. - A function to run an operation on every element of the array. The apply function takes as an argument a function with a parameter that returns a void. Calling apply runs this function for each member of the array; the order of execution is undefined. Conceptually (and maybe even in practice) these executions occur concurrently. 3.6. Constness of arrays There are two ways to look at what the C++ const qualifier means: bitwise constness and semantic constness. The language enforces only bitwise constness, but many practitioners choose to expand the idea of const from just the object itself to things referred to by the object. This semantic const approach is often more useful because you are given stricter guarantees (more like promises, since they are not enforceable by the compiler) that things will not change if an object is const. There are two components to an array: view and data. In a bitwise const approach only the view part of a const array is kept const. This means that you can change elements of the array (the data) even though the array is const. A more useful, semantic const, approach is to make both the view and the data of a const array unchangeable. This is the approach we advocate. Thus, a const subscripting operator returns a const section, or a const element if all indices are integers. You cannot directly reference the elements of the array if it is const. There are const holes in the semantic approach. The most obvious is the copy constructor. Ideally, it would be nice to enforce the idea that a copy of a const array constructed using the copy constructor is itself const. Unfortunately, in C++ this is not possible  an object constructed using the copy constructor cannot be forced to be const. Yet not allowing a copy constructor which takes a const argument is too restrictive. In practice we have found that const holes of this type are not a substantial problem. The theoretically nicest approach is to consider the constness of the view part and the data part independently. As a direct analogy, consider the four variants of constness associated with C++ pointers: - non-const pointer to non-const object (Foo *x) - const pointer to non-const object (Foo *const x) - non-const pointer to const object (const Foo *x) - const pointer to const object (const Foo *const x). Similiarly, we would need two sets of array classes: one pointing to const data (ConstArray), and the other to non-const data (Array). In combination with the standard C++ const qualifier we have, just as with pointers, four types - non-const array of non-const data (Array x) - const array of non-const data (const Array x) - non const array of const data (ConstArray x) - const array of const data (const ConstArray x). In practice, however, only non-const pointers to non-const data and non-const pointer to const data are used frequently. For this reason, we decided that the doubling of the number of classes required by the more correct approach was not worthwhile. Most of the benefits are achieved at less cost via the idea of semantic constness. 4.0. Numerical array classes The numerical array types are the same as the general array types, except that operations valid specifically for numerical types have been added. The most important additions are the overloaded arithmetic operators. In this section, only operations new to the numerical array types are described. All the operations described in the previous section remain valid. One possible implementation of the numeric types would be to use public inheritance to get the functionality of the general array classes, and then add functionality specific to the numerical types. Unfortunately, this approach does not work well in practice. None of the constructors are inherited. The subscripting operators return the base type, not the derived type. We choose instead to implement numerical array classes as a type completely distinct from the general arrays. Of course, even though the type is distinct, the numerical array classes could well be implemented using general arrays, perhaps using private inheritance. 4.1. Operations required for element types The types allowed as entries in numerical arrays must have the same properties as those allowed in general arrays. In addition, all of the following operators must be defined: - the standard 4 binary arithmetic operators (+,-,*,/) - the arithmetic assignment operators (+=,-=,*=,/=) - the unary plus and minus operators 4.2. Overloaded operators The standard four arithmetic operators, the arithmetic assignment operators, and the unary operators, are overloaded for the numeric arrays. The semantics of each is to do element by element operations on the elements of the arrays. On machines with parallel processing capabilities, the operations may occur concurrently. Just as with assignment, an implementation must be careful to check for the case when the two array operands alias the same data. 4.3. Matrix Multiplication According to the above definition of operator behaviour, the expression A*B, where A and B are matrices, does element by element multiplication, and does not compute an inner product (matrix multiplication). Although it is tempting to make this an exception, it was felt that the concept does not extend easily to arrays of higher dimension, and that the lack of symmetry was not worth the gains. Instead, inner product style matrix-matrix and matrix-vector multiplication is done using a set of overloaded product functions. 5.0. Specific array types Up to now, we have discussed only templated array types. Often, it is desirable to augment the template array types with functions specific to the type of entries in the array. A simple example is type conversion: youd like to specify functions to convert from, say, arrays of integers to arrays of doubles. The mechanism in C++ for creating a new type with increased functionality is inheritance. Unfortunately, inheritance does not work particularly well with concrete types, such as the array classes. The problem is that return types and constructors are not changed correctly, leading to a large amount of code that must be duplicated in the new class. We propose here a set of specific array types which are (as a minimum) typedefs to template types. In practice, these types can be implemented fully independently from the template types, and extra functionality can be added where desired. The user of these types will not be able to tell that they are not simply derived from the templates, except that there may be increased functionality and better type checking. The classes we propose are defined as typedef NumVec IntVec; typedef NumVec FloatVec; typedef NumVec DoubleVec; typedef NumGenMat IntGenMat; typedef NumGenMat FloatGenMat; typedef NumGenMat DoubleGenMat; typedef NumArray IntArray; typedef NumArray FloatArray; typedef NumArray DoubleArray; 6.0. Class definitions In this section, we give code that represents a minimal interface to the classes described in this document. 6.1. General array class definitions Here is the minimal public interface to the general vector class: class Vec { public: Vec(); // constructors Vec(const Vec&); Vec(size_t, Uninitialized); Vec(size_t, const T&); Vec& operator=(const Vec&); // member operators const T& operator()(size_t) const; // subscripting T& operator()(size_t); const Vec operator()(const Slice&) const; Vec operator()(const Slice&); size_t length() const; // member functions void reshape(size_t); void resize(size_t); Vec copy() const; void apply(void (*f)(const &)); }; Here is the general matrix class minimal interface: class GenMat { public: GenMat(); GenMat(const GenMat&); GenMat(size_t,size_t, Uninitialized); GenMat(size_t,size_t,const T&); GenMat& operator=(const GenMat&); const T& operator()(size_t,size_t) const; T& operator()(size_t,size_t); const Vec operator()(size_t,const Slice&) const; const Vec operator()(const Slice&,size_t) const; Vec operator()(size_t,const Slice&); Vec operator()(const Slice&,size_t); const GenMat operator()(const Slice&,const Slice&) const; GenMat operator()(const Slice&,const Slice&); size_t cols() const; size_t rows() const; void reshape(size_t,size_t); void resize(size_t,size_t); GenMat copy() const; void apply(void (*f)(const &)); }; Here is the general array class minimal interface. For brevity, not all possible subscripting operators are shown. class Array { public: Array(); Array(const Array&); Array(size_t,size_t,size_t, Uninitialized); Array(size_t,size_t,size_t,size_t, Uninitialized); Array(size_t,size_t,size_t,const T&); Array(size_t,size_t,size_t,size_t,const T&); Array operator=(const Array&); T& operator()(size_t,size_t,size_t); T& operator()(size_t,size_t,size_t,size_t); Vec operator()(size_t,size_t,const Slice&); . . . size_t dimension() const; size_t dimension(size_t) const; void reshape(size_t,size_t,size_t); void reshape(size_t,size_t,size_t,size_t); void resize(size_t,size_t,size_t); void resize(size_t,size_t,size_t,size_t); Array copy() const; void apply(void (*f)(const &)); }; 6.2. Numerical array class definitions Here is the minimal public interface to the general numerical vector class: class NumVec { public: NumVec(); NumVec(const NumVec&); NumVec(size_t, Uninitialized); NumVec(size_t, const T&); NumVec operator=(const NumVec&); const T& operator()(size_t) const; T& operator()(size_t); const NumVec operator()(const Slice&) const; NumVec operator()(const Slice&); size_t length() const; void reshape(size_t); void resize(size_t); NumVec copy() const; void apply(void (*f)(const &)); NumVec operator+() const; NumVec operator-() const; NumVec operator+=(const NumVec&) const; NumVec operator-=(const NumVec&) const; NumVec operator*=(const NumVec&) const; NumVec operator/=(const NumVec&) const; }; NumVec operator+(const NumVec&,const NumVec&); NumVec operator-(const NumVec&,const NumVec&); NumVec operator*(const NumVec&,const NumVec&); NumVec operator/(const NumVec&,const NumVec&); T product(const NumVec&,const NumVec&); Here is the numerical matrix class minimal interface: class NumGenMat { public: NumGenMat(); NumGenMat(const NumGenMat&); NumGenMat(size_t,size_t, Uninitialized); NumGenMat(size_t,size_t,const T&); NumGenMat operator=(const NumGenMat&); const T& operator()(size_t,size_t) const; T& operator()(size_t,size_t); const Vec operator()(size_t,const Slice&) const; const Vec operator()(const Slice&,size_t) const; Vec operator()(size_t,const Slice&); Vec operator()(const Slice&,size_t); const NumGenMat operator()(const Slice&,const Slice&) const; NumGenMat operator()(const Slice&,const Slice&); size_t cols() const; size_t rows() const; void reshape(size_t,size_t); void resize(size_t,size_t); NumGenMat copy() const; void apply(void (*f)(const &)); NumGenMat operator+() const; NumGenMat operator-() const; NumGenMat operator+=(const NumGenMat&) const; NumGenMat operator-=(const NumGenMat&) const; NumGenMat operator*=(const NumGenMat&) const; NumGenMat operator/=(const NumGenMat&) const; }; NumGenMat operator+(const NumGenMat&,const NumGenMat&); NumGenMat operator-(const NumGenMat&,const NumGenMat&); NumGenMat operator*(const NumGenMat&,const NumGenMat&); NumGenMat operator/(const NumGenMat&,const NumGenMat&); NumGenMat product(const NumGenMat&,const NumGenMat&); NumVec product(const NumVec&,const NumGenMat&); NumVec product(const NumGenMat&,const NumVec&); Here is the numerical array class minimal interface. For brevity, not all possible subscripting operators are shown. class NumArray { public: NumArray(); NumArray(const NumArray&); NumArray(size_t,size_t,size_t, Uninitialized); NumArray(size_t,size_t,size_t,size_t, Uninitialized); NumArray(size_t,size_t,size_t,const T&); NumArray(size_t,size_t,size_t,size_t,const T&); NumArray operator=(const NumArray&); T& operator()(size_t,size_t,size_t); T& operator()(size_t,size_t,size_t,size_t); Vec operator()(size_t,size_t,const Slice&); . . . size_t dimension() const; size_t dimension(size_t) const; void reshape(size_t,size_t,size_t); void reshape(size_t,size_t,size_t,size_t); void resize(size_t,size_t,size_t); void resize(size_t,size_t,size_t,size_t); NumArray copy() const; void apply(void (*f)(const &)); NumArray operator+() const; NumArray operator-() const; NumArray operator+=(const NumArray&) const; NumArray operator-=(const NumArray&) const; NumArray operator*=(const NumArray&) const; NumArray operator/=(const NumArray&) const; }; NumArray operator+(const NumArray&,const NumArray&); NumArray operator-(const NumArray&,const NumArray&); NumArray operator*(const NumArray&,const NumArray&); NumArray operator/(const NumArray&,const NumArray&); };