The Learning C/C++urve

Columns

The Learning C/C++urve: Very Small Array

Bobby Schmidt

It is possible to build an array type from materials found around the home, but not necessarily easy.

Copyright © 1998 Robert H. Schmidt
In this month's soirée, we start translating the prose description of an array class into its code representation, beginning with the bare-bones definition
class Array
    {
    };
As is my wont, I'll make explicit the four "usual suspects" normally implied in class definitions:
class Array
    {
public:
    ~Array();
    Array();
    Array(Array const &);
    Array &operator=(Array const &);
    };
Consider these declarations tentative; we may find as we go along that we want some of these members declared private and left unimplemented.
I next refer you to the March column and its bulleted list of fundamental array properties. While developing this first-pass array class, I'll summarize each property in turn and map it into the class design.

Nascent Class

The first property is perhaps the most basic: arrays contain a fixed number of other objects. This property implies that our class must at minimum know

what kinds of objects it contains

how many objects it contains

An obvious solution is to specify the contained object "kind" or type as a template parameter, and the number of those objects as a constructor argument:
template<class T>
class Array
    {
public:
    Array(size_t const n);
    // ...
    };
How does Array's implementation use n and T? You may hope Array can directly encapsulate a real array as
template<class T>
class Array
    {
public:
    Array(size_t const n);
    // ...
private:
    T array_[n];
    };
 
Array<char> a(10); // error
Sadly, such a template won't instantiate — you can't dimension array_ this way. Because the length of the array (n) is not known until Array construction, you must defer allocating array_ until then:
template<class T>
class Array
    {
public:
    Array(size_t const n)
        : array_(new T[n])
        {
        }
    // ...
private:
    T *array_;
    };
Array<char> a(10); // OK
The Array constructor allocates a new array of n Ts, and points array_ to that new allocation. Now every ith element of the encapsulated array is equally accessible to Array members as array_[i]. Unfortunately, while this implementation is quite straightforward, it has some subtle differences from real arrays.

Problem 1: new

Any time your code calls new you must ask yourself what would happen were the allocation to fail. In our example, because the Array constructor calls new, declarations like
// calls Array constructor
Array<char> a(10);
could throw an exception. This is certainly a difference from C arrays, and from C++ arrays of POD types [1], which have no hidden dynamic allocation.

To maintain the array-like illusion, you must prevent the exception from percolating to client code:
#include <new>
template<class T>
class Array
    {
public:
    Array(size_t const n) : array_(NULL)
        {
        try
            {
            array_ = new T[n];
            }
        catch (std::bad_alloc)
            {
            // error recovery code here
            }
        }
    // ...
private:
    T *array_;
    };
While this code keeps the existence of new invisible to clients, it still leaves us with a problem: how does Array respond if new fails?
I have no single answer here. Certainly if new fails for a reasonably small Array object, your system is memory constrained; useful recovery is almost certainly impossible. In such a case, you may just want to post a diagnostic trace and abort the program. Alternatively, you could keep array_ set as NULL, and somehow indicate to clients that the Array object has zero length.
For the purposes of this discussion I'll blithely ignore the problem, explaining my rationale shortly.

Problem 2: sizeof

Given the array declared as
T a[N];
(where N > 0), then sizeof(a) == sizeof(T) * N [2]. That is, the array object's size equals the combined size of all its element objects.

This relationship typically fails for our Array implementation. As Array contains but a single pointer object, sizeof(Array) == sizeof(T *), which is most likely less than sizeof(T) * N [3]. Somehow we must make sizeof(Array) — which is really sizeof(array_) — equal to sizeof(T) * N.
Clearly one way to achieve this is to define array_ not as a pointer, but as a real array of N Ts [4]. But we showed earlier that we can't dimension such an array — or at least, we can't with the length available only at run time. If we could somehow know the length at compile time, the story would change.
Fortunately, C++ templates allow us to include just such compile-time information. While we typically give templates type parameters, we can also give them non-type parameters. According to section 14.1.4 of the C++ Standard, possible non-type parameters are

integrals

enumerations

pointers/references to objects/functions

pointers to members

For Array, we'll add an integral template parameter corresponding to the array length, and remove the corresponding constructor parameter, yielding
template<class T, size_t N>
class Array
   {
public:
    Array()
        {
        }
    // ...
private:
    T array_[N];
    };
This has the net effect of dimensioning the array at compile time rather than at run time. It also produces the desired identity sizeof(Array) == sizeof(T) * N. Finally, since array_ is no longer allocated dynamically, the run-time check for a failed new disappears.

With this new implementation, the declaration of Array objects changes:
Array<char, 10> a; // array of 10 chars
In addition to the above-mentioned properties, Array also features value semantics. Furthermore, with the new implementation, element storage lies within the Array object. Thus, the current Array implementation — threadbare as it is — supports the first three real-array properties from last month's set.

Access

An array allows direct or so-called random access to its elements. Each element is identified by a unique whole-number index ranging from 0 to N - 1. Because the number of indices matches the number of elements, there are no gaps in this range.
You can think of arrays as primitive maps, projecting a set of whole numbers onto a set of T objects. This mapping is done via the [] operator, and results in either an lvalue or rvalue expression, depending on context:
char a[10];    // Real array of 10 chars.
               //    Can map whole numbers [0, 9].
a[2] = 'x';    // Map whole number 2 to array element.
               //    a[2] is lvalue expression.
char c = a[3]; // Map whole number 3 to array element.
               //    a[3] is rvalue expression.
Because elements are stored contiguously in their indexed order, the relation &a[i] + sizeof(T) == &a[i + 1] is always true for i in the range [0, N - 2].
To emulate this behavior in Array, we can simply add a user-defined operator[]. To properly design this operator, we must know the types of

the index mapped into an element object

the resulting element

For occurrences of [] in rvalue expressions such as
Array<char, 10> a;
char c = a[3]; // a[3] is an rvalue expression
operator[] must return something that can act like a T rvalue. Since T lvalues can convert to T rvalues, operator[] can be declared to return any of
T operator[](...);        // T rvalue
T &operator[](...);       // modifiable T lvalue
T const &operator[](...); // non-modifiable T lvalue
For occurrences of [] in lvalues such as
a[2] = 'x'; // a[2] is an lvalue expression
however, operator[] must return an lvalue, limiting the possibilities to
T &operator[](...);       // modifiable T lvalue
T const &operator[](...); // non-modifiable T lvalue
Since the above example assigns through a[2], you might think that
T &operator[](...);
is the obvious choice. In this instance you'd be right, but consider the variation
Array<char, 10> const a;
a[2] = 'x'; // should this compile?
With our operator[] returning T &, this would compile. Were a declared as a real array:
char const a[10];
a[2] = 'x'; // error
the example would fail, with the compiler complaining that a[2] is not a modifiable lvalue. To mimic such array behavior, we need to somehow prevent const Array objects from being modified.

operator[] Defined

The trick is to overload operator[]. For non-const Arrays, operator[] allows modification of returned elements; for const Arrays, operator[] disallows such modification. The result is
template<class T, size_t N>
class Array
    {
public:
    T &operator[](...);
    T const &operator[](...) const;
    // ...
    };
We also need to establish the correct type for the array index. At first blush, you might be tempted to use
T &operator[](int);
T const &operator[](int) const;
Remember, though, that array indices are non-negative, meaning half of int's possible values are ineligible. This suggests unsigned might be a better index type, as all of unsigned's values are non-negative.

A better answer still is to use size_t, which is the unsigned type resulting from the sizeof operator. Since the size of an array will never be larger than the length of that array, a size_t will always be big enough to hold any valid array index.
This gives us a new operator[] interface and implementation:
template<class T, size_t N>
class Array
    {
public:
    T &operator[](size_t const i)
        {
        return array_[i];
        }
    T const &operator[](size_t const i)
       const
        {
        return array_[i];
        }
    // ...
    };
Array/Pointer Symbiosis

An array typically converts or "decays" to a pointer referencing the array's first element. This conversion — from a to &a[0] — implies that a can appear in contexts requiring a T pointer. In particular, the conversion allows the expression a + i, which (by substitution) is tantamount to &a[0] + i.
Note that a + i points not i bytes beyond the start of a, but i elements beyond. This leads to the relationship a + i == &a[i]. As each expression represents a pointer to the same object, it follows that *(a + i) == *(&a[i]). Simplifying, we get *(a + i) == a[i].
Since a in the expression *(a + i) converts to a pointer, the expression should work if a is a real pointer to begin with:
char a[10];
char *p;
char c;
c = a[0]; // OK
p = a;    // OK, a converts to &a[0]
c = *a;   // OK, *a == *(&a[0]) == a[0]
c = *p;   // OK
c = p[0]; // OK, p[0] == *(p + 0) == *p
Because the + in (a + i) and (p + i) is commutative, we must face the unpleasant truth that
a[3] == *(a + 3) == *(3 + a) == 3[a]
As Dave Barry would say, I am not making this up. I counsel disbelievers to read section 6.3.2.1 of the C9X Draft Standard.

Emulating Array/Pointer Behavior

To emulate real array-to-pointer decay, we must somehow let an Array object become a pointer to its first element. A brute-force approach would add a member function explicitly returning said pointer:
template<class T, size_t N>
class Array
    {
public:
    T *pointer()
        {
        return array_;
        }
    // ...
    };
 
Array<char, 10> a;
char *p = a.pointer();
While this code builds and runs, it hardly suffices. Real arrays silently convert; to make the illusion complete, we must allow
Array<char, 10> a;
char *p = a;
In the example
char a[10];
char *p = a;
a implicitly converts to a char *, as if the code had been written
char a[10];
char *p = (char *) a;
If we provide an analogous conversion for Arrays, it will be similarly named to turn an Array into a T *:
template<class T, size_t N>
class Array
    {
public:
    operator T *()
        {
        return array_;
        }
    operator T const *() const
        {
        return array_;
        }
    // ...
    };
 
Array<char, 10> a;
char *p;
p = a;                   // OK
p = (char *) a;          // OK, equivalent
p = a.operator char *(); // OK, equivalent
Like operator[] before it, operator T * has const and non-const overloads. All of these operators return access to Array elements; we must ensure that supposedly const (unchangeable) Arrays can't have their elements inadvertently modified.
This brings up an interesting design point: the potential difference between a non-const container of const elements and a const container of non-const elements. In your view, should
Array<char, 10> const a
and
Array<char const, 10> a
behave identically? If so, why? If not, how should they differ, and why?

Real arrays shed no light here, since they cannot make this distinction. In the statement
char const a[10];
is a considered an array of ten const chars, or a const array of ten chars? My reading of the Standards suggests the former is correct; otherwise, a const a could decay to a pointer of type char *, sabotaging the array's alleged constness. However, this is purely an educated guess, as I've yet to find a simple unambiguous ruling in either Standard.

This distinction is no mere sophistry, and becomes quite significant in the C++ Standard Template Library (STL). I will completely sidestep the issue for now, and constrain Array to non-const element types. Eventually, we'll revisit this when considering how Array can be generalized into a more STL-like container.

In The Pipeline

Our current Array definition appears as Listing 1. Next month we'll continue the Array development, revel in fan mail, fix bugs in last August's column, and ruminate on Carlo Pescio's article on parameterized integers. It's sure to be another action-filled adventure, so don't touch that dial. o

Notes

1. "POD" is Standardese for "plain old data," and designates C++ types conceptually like those in C.
2. Arrays can have zero length. Contrary to intuition, zero-length arrays have non-zero size, which of course cannot equal sizeof(T)* N.
3. Implementations may add any padding required for placing class objects in an array. For this discussion, I'm assuming the Array object has no such padding.
4. All you @microsoft.com denizens can stop palpitating: this is not the same as an array of NTs.

Bobby Schmidt is a freelance writer, teacher, consultant, and programmer. He is also a member of the ANSI/ISO C standards committee, an alumnus of Microsoft, and an original "associate" of (Dan) Saks & Associates. In other career incarnations, Bobby has been a pool hall operator, radio DJ, private investigator, and astronomer. You may summon him at 14518 104th Ave NE Bothell WA 98011; by phone at +1-425-488-7696, or via Internet e-mail as rschmidt@netcom.com.