Dan Saks is the owner of Saks & Associates, which offers consulting and training in C and C++. He is secretary of the ANSI and ISO C++ standards committees, and also contributing editor for Windows/DOS Developer's Journal. Dan recently finished his first book, C++ Programming Guidelines, written with Thomas Plum. You can write to him at 393 Leander Dr., Springfield, OH 45504, or dsaks@wittenberg.edu (Internet), or call (513)324-3601.
Dynamic array classes let you create arrays for which you can delay choosing the number of elements until runtime. In my last column, I described reasons why you might want to use such things in your programs (see "Dynamic Arrays", CUJ, November, 1992). I also presented a fairly typical implementation for class float_array, a simple dynamic array of float.
Each float_array has two data members: array, a pointer to the first element of an actual array of float allocated from the free store, and len, the number of elements in that array. Listing 1 shows the class definition. It has two constructors, a destructor, an assignment operator, a subscript operator, and a function that returns the number of elements.
const Member Functions Revisited
Last time I also introduced const member functions. For the most part, you can think of a const member function as one that promises not to change the object addressed by its this pointer. Although you can call a const member function for both const and non-const objects, you can call a non-const member function only for non-const objects.You declare a member function as const by placing the keyword const after the parameter list in the member function declaration. Class float_array in Listing 1 has two const member functions: operator[] and length. You must also use the keyword const when you write the function definitions, as shown in Listing 2.
If you accept my belief that you should declare objects const whenever feasible, then clearly the length function should be const. length simply returns the number of elements in the array without changing anything.
It also appears that operator[] should be const. If you don't declare it const, you can't subscript a const float_array. The operation appears to be perfectly safe. After all, it doesn't change anything. It simply returns a reference to the selected element. But, when I concluded last time, I said that the operator[] in Listing 2 is an accident waiting to happen. It lets you write an expression, without a cast, that inadvertently modifies a const float_array. For example, given
const float_array fb(fa);you can write
fb[0] = 0;which overwrites the value of the fb's first element. This is valid C++. The assignment statement compiles and executes without error. But that assignment is probably an accident, and you might find the results surprising.
constness is Shallow
To see how the accident can happen, let's take a closer look at what it means for a member function to be const. In a non-const, non-static member function for class X, the type of this is X *const. That is, the function cannot change the value of its this pointer, but it can modify each non-const data member of the object addressed by this.In a const member function of class X, this has type const X *const. Not only is the this pointer const, but so is the object it points to. Each data member of a const object is in turn const. This applies recursively to any data members that are objects of a class type. Thus, a const member function cannot change the value of any data members in the object addressed by this. (A const member function must be non-static because the const qualifier modifies the object addressed by the this pointer. A static member function has no this pointer, so it cannot be const.)
Aye, there's the rub: constness is shallow. A pointer member in a const object is a const pointer, but it is not pointer to const unless explicitly declared so. In other words, inside operator[], the object's array data member (that is, this>array) has type float_array *const, not the desired const float_array *. You cannot change the pointer, but you can change the values of the array elements. This violates the intuitive notion that the elements of a const array are themselves const.
operator[] in Listing 2 is a const member function. Inside the function, the array member is const, but the element array[i] is not. The function returns a float &, not a const float &. Thus, even though operator[] doesn't change any values, it returns a modifiable reference to an array element that the caller might accidentally use to change a value in a const float_array.
From the programming language's standpoint, this is not an error. The behavior of the float_array class, even with this questionable operator[], is well-defined. For a non-class type T, writing over a const T object (or a part thereof) yields undefined behavior because you might be writing into ROM (read-only memory). But C++ only places a const class object in ROM if that class has neither constructors nor a destructor. Since class float_array has constructors and a destructor, the translator will never put const float_array objects in ROM. In this case, const float_array objects behave at runtime just like non-const objects. However, if class float_array had neither constructors nor a destructor, the translator might place const float_array objects in ROM, and calling operator[] for a const float_array would have undefined behavior.
C++ has no notation for specifying "deep" constness. That is, in a class X with pointer member T *p, you can't make the p member of a const X object have type const T *. However, you can design X to simulate "deep" constness.
Overloading with const
Let's consider correcting the problem in operator[] (Listing 2) by changing the function's return type from float & to const float & in both Listing 1 and Listing 2. Then when you declare
const float_array fb(fa);and write
fb[0] = 0;you will get a compilation error because the expression fb[0] refers to a const float object, which you cannot modify. Unfortunately, now every float_array subscripting expression is const, so you cannot do that assignment even if fb were non-const.What you need is two different subscripting operators: one for const float_arrays, and another for non-const float_arrays. C++ lets you overload a member function as const and non-const. That is, you can declare two member functions in a given class with identical names and parameter lists, provided one of the functions is const and the other is not. In this case, you overload operator[] as a const function returning a const float &, and as a non-const function returning a (plain) float &. Listing 3 shows the float_array class definition with both declarations for operator[]. Listing 4 shows the corresponding function definitions.
When the compiler encounters a float_array subscripting expression like fb[i], it chooses an operator[] by the constness of fb. It does not matter whether fb[i] appears as an lvalue or rvalue. For example, given
float_array fa(fx); const float_array fb(fy);then
fa[i] = fb[i];calls the non-const operator[] on the left of the assignment, and calls the const operator[] on the right. Everything works fine. However, the assignment
fb[i] = fa[i];calls the const operator[] on the left side and calls the non-const operator[] on the right. But the const operator[] returns a non-modifiable lvalue (a const float &), so it cannot appear as the destination of the assignment, and you get a compile-time error.Furthermore, the compiler selects the operator[] based on the constness of the float_array expression that refers to the object, and not the constness of the object itself. For example,
const float_array *p = &fa;binds p, a pointer to const, to a non-const object, fa. Then (*p) [i] calls the const operator[] because *p has type const float_array, even though p points to a float_array that's declared non-const.
Arrays That Grow
When I first introduced operator[] in my previous column, I suggested that the function could handle a subscript out-of-bounds in a number of ways. Thus far, my float_array class has treated subscripts out of bounds as an error caught by assert. Now let's consider rewriting operator[] to automatically extend the array so that the subscript is in bounds.For example, if you declare
float_array fa(4);then fa has four elements whose indices are 0 through 3. Now if you write
fa[6] = 1.0;then operator[] adds three more elements to fa at indices 4, 5, and 6, so the assignment operator has some place to store the 1.0.Rewrite only the non-const operator[]. Extending an array changes the array (by making it bigger), and a const member function should not change the object addressed by its this pointer. Subscripting out of range in a const float_array should remain a runtime error.
Listing 5 shows my revised implementation for the non-const operator[]. If the function determines that the subscript is out of bounds, it allocates a new, larger array. It copies the values of the elements of the old array into their corresponding positions in the new array, and fills the remaining elements in the new array with zeros. Then it deletes the old array, thus returning that storage to the free store.
Listing 6 shows a trivial test program that uses operator[] to extend an array. Figure 1 shows output from that program. The second for loop in main (Listing 6) overwrites the values in fb and then adds new elements. The output expression just before the return statement forces a subscripting error on the const float_array fc. I added that expression just to reinforce that operator[] is different for const and non-const float_arrays.
The subscripting error makes the assertion in operator[] fail. assert displays an error message and aborts the program. Unlike the exit function, abort does not flush and close the standard output stream, cout. Thus I changed the body of the display function from
cout << s << " = " << fa << '\n';(as it was in my previous column), to
cout << s << " = " << fa << endl;endl is a special kind of function called a manipulator. It's defined in iostream.h. The expression
cout << endl;writes a newline to cout and flushes cout's output buffer to standard output. Typically, you won't see the difference between \n and endl unless you redirect standard output to a file.You might recognize an opportunity to use realloc in the non-const operator[]. realloc is a Standard C library function that changes the size of a dynamically-allocated block of memory. However, realloc only works with storage previously allocated by calloc, malloc, or realloc. Many C++ environments implement the new operator in terms of malloc, so realloc might work with new. But there is no guarantee that it always will.
For float_arrays, you could simply abandon the new operator and use malloc and realloc. The code for class float_array will still be portable. However, using malloc and realloc only works for arrays of objects without constructors and destructors. The new operator applies a default constructor to each element of the array it allocates. malloc just grabs storage.
On occasion, members of the C++ standards committee have suggested adding a renew operator that works with new as realloc works with malloc. So far, nothing has come of it.
Dangling Pointers and References
A dangling pointer or reference is one that remains bound to an address after the program deallocates the object at that address. The potential occurrence of a dangling pointer or reference is an ever present fact of life for C++ programmers, as it is for C programmers. operator[] offers yet another opportunity for the unwary to get bitten.Consider, for example, the following code fragment:
float_array fa, fb; ... float *p = &fa[i]; ... fa = fb; ... *p = 1.0;p's declaration binds it to the address of an element of fa. (Remember, fa[i] is a reference to an element, and so &fa[i] is the address of the referenced element.) If fb and fa have a different number of elements, the assignment fa = fb deletes the old elements of fa with new ones at a different address. This leaves p dangling.An even subtler problem occurs in the test program in Listing 7 when using the (non-const) operator[] that may extend a float_array (Listing 5) . If you run the program with 4 as the input value for size, it initializes fa with four elements { 0 1 2 3 }. The subsequent statements
size_t n = fa.length(); fa[n] = fa[n - 1] = 123;look like they extend fa by one element and copy 123 into the last two elements, so that
fa = { 0 1 2 123 123}I tested the assignment against three MS-DOS C++ compilers (Borland, Comeau, and Zortech), and they all produced that result.The next two statements
n = fa.length(); fa[n - 1] = fa[n] = 456;look like they should extend fa by one more element, and store 456 in the last two elements, so that
fa = { 0 1 2 123 456 456 }Interestingly, only Borland and Zortech produced that result; Comeau produced
fa = { 0 1 2 123 123 456 }Apparently, Comeau evaluates
fa[n - 1] = fa[n] = 456;more or less as follows:
float &t1 = fa[n - 1]; float &t2 = fa[n]; t2 = 456; t1 = t2;But the call to fa[n] in the second step extends fa and moves its elements to a different place in the free store. Unfortunately, t1 has already been bound to the original location of fa[n - 1], and the call to fa[n] leaves t1 dangling. Thus, the final step (t1 = t2), copies 456 from fa[n] into the original location of fa[n - 1], not the current one.The Comeau compiler is generating correct code. C++ compilers, like C compilers, have considerable freedom about the order in which they evaluate operands between sequence points, and the Comeau compiler is merely exercising its freedom. The problem is in the test program, because the expression depends on a particular evaluation order for success.
Subscripting Objects
operator[] opens the door for dangling pointers and references because it returns a reference to part of a float_array's internal representation. That representation tends to move around, but the references don't rebind to the new locations. You can eliminate many opportunities for dangling references by rewriting operator[] to return a subscripting object instead of a reference.A reference to a float can only keep track of a single float element in a float_array. The reference has no way of knowing if the value it's referring to has moved. A subscripting object keeps track of both the float_array and the value of the subscript, so it always subscripts using the current location of the array.
Listing 8 is the header for class float_array using a subscripting class, fa_index. fa_index has two data member: fa, a pointer to a float_array, and ix, a subscript for an element of that float_array. fa_index has a two-argument constructor that fills in values for members fa and ix.
Notice that the constructor is private. Thus, clients (users) of fa_index can't create fa_index objects. How, then, does the program ever create an fa_index? fa_index declares float_array as a friend class. Hence, every member function of class float_array is a friend of class fa_index. float_array member functions has access rights so they can construct fa_index objects.
Listing 9 presents the implementations for both the fa_index and float_array member functions. (The listing includes all the float_array member functions for completeness.) The only float_array member function that changes to use fa_index is the non-const operator[]. Rather than return a float & as before, it returns an fa_index object.
The fa_index class has a conversion operator that converts an fa_index to a float. When you use an expression like fa[i] as an rvalue in a context expecting an arithmetic expression, the program implicitly calls operator float to convert the fa_index object into the value of element that the object designates. That is, the compiler translates the assignment in
float x; ... x = fa[i];into something like
fa_index t1(fa[i]); x = float(t1);The program constructs a temporary fa_index t1 to hold the result of fa[i]. Then it applies fa_index::operator float to t1 to get the value of the array element.When fa[i] appears to the left of an assignment, the program calls fa_index::operator=(float) to write through the fa_index object and into the float_array element it designates. For example, an assignment like
fa[i] = 1;translates into
fa_index t1(fa[i]); t1.operator=(float(1));Using this new implementation for float_array with the test program in Listing 7 eliminates the dangling reference. It enables all three compilers to produce the same (intended!) result.But you pay for subscripting objects. They slow down every subscripting operation on a non-const float_array. Furthermore, you lose some functionality that you have to reconstruct by writing more member functions for fa_index. For example, fa_index::operator= only lets you use an expression like fa[i] as the left side of an = operator. It doesn't cover any other uses as an lvalue, such as fa[i] *= 10 or ++fa[i]. If you want these operators, you must define them for class fa_index.
Other Uses for operator[]
Some C++ applications use operator[] as a file positioning operator, replacing explicit calls to a function like lseek. For example,
File f("myfile"); ... f[10] = 'X';writes an X into the tenth character position of File f. Coplien (1992, 49-52) outlines a simple implementation for this scheme using subscripting objects.Cargill (1992, 91-112) provides an excellent description of what goes wrong with poorly-designed subscripting objects. His example uses a file object similar to Coplien's. Cargill also provides some thoughtful discussion on whether using operator[] this way is just too clever. The pitfalls may out-weigh the notational advantages.
References
Cargill, Tom. 1992. C++ Programming Style. Reading, MA: Addison-Wesley.Coplien, James O. 1992. Advanced C++ Programming Styles and Idioms. Reading, MA: Addison-Wesley.