Chapter 6: One-Dimensional Arrays and Strings

Overview

Static one-dimensional arrays and their representation as pointers. Array indexing as indirection. Why an array index range check cannot be performed in C/C++. The price of run-time array index range checking; "compile-time checking" versus "run-time checking" philosophies. Passing static one-dimensional arrays as function arguments. Definition versus declaration of one-dimensional arrays. Dynamic one-dimensional arrays. Strings as static or dynamic one-dimensional char arrays terminated with NULL . How to add a custom-made run-time index range checker in C++.

The most frequently used composite data structures in programming are arrays. Since their use is so ubiquitous, they are provided as almost built-in data types in C/C++. Unfortunately, the emphasis is on "almost" and not on "built-in". On the one hand, "almost" here means that you need not provide any programmatic means of creating (building) and indexing the array and that any C/C++ compiler will provide both automatically. The array definition/declaration and access to the array items through indexing are thus integral parts of the C/C++ language. On the other hand, "almost" also means there is no innate data type array in C/C++ that is treated in its own special way, so each array is represented by an appropriate pointer pointing to an appropriate storage according to appropriate conventions. This has some unexpected consequences for "index out of range" run-time errors and for passing array arguments to functions.

The fundamental notion of an array is just an extension of the basic model of computer memory: an array of bytes accessible through indexes (their addresses). Thus an array of a data type D is a data structure where each array item is a "data container" of the same data type D and can be accessed through its index. This notion is taken to its most abstract form in C++, where you can define an indexing operator operator[] on any class and thereafter use the objects of the class as arrays.

Proper arrays in C/C++ are in fact even more "faithful" memory models, for not only does their indexing start from 0, also they really do consist of identical adjacent "data containers" (i.e., they reside in a contiguous memory segment); see Figure 6.1. It is quite natural (the reader may refer back to Chapter 3) to see the array items as "virtual data containers" accessed via the appropriate pointer. Thus, if a pointer p points to the very first item of an array, then we can see that *p represents the very first item in the array, *(p+1) represents the second item of the array, ..., *(p+i) represents the i th item of the array; see Figure 6.2.

Figure 6.1: Concept of one-dimensional array

Figure 6.2: Accessing a one-dimensional array via a pointer

Seeing how natural it is to access array items through a pointer, we cannot be surprised to learn that C/C++ treats one-dimensional arrays in this fashion. For instance, an int array x[] with six items defined by int x[6]; is thus represented by the C/C++ compiler as a constant pointer (meaning that the pointer cannot be reset) int* x and a statically allocated memory segment to accommodate six virtual data containers of the data type int , as indicated by Figure 6.3.

Figure 6.3: Representation of the int x[6] array

It also comes as no surprise that C/C++ compilers really do translate array indexing expressions like x[i] into indirection expressions like *(x+i) . Moreover, pointers can be "indexed": If p is any pointer (except void* ), then the expression p[i] makes sense when translated by the compiler to *(p+i) and so the program can be perfectly well compiled and executed. As we can see, arrays are treated as constant pointers, and the indexing mechanism is nothing but the dereferencing of these pointers. In fact, a static array is nothing but a constant pointer that points to a properly (statically) allocated memory segment.

This was rather convenient for the designers of C and also for the builders of C/C++ compilers in that there was no real need to deal with an innate data type array . However, it turns out that there are some unpleasant consequences.

The first of these concerns the " size " of an array. It is clear that, upon encountering a definition of an array, the compiler (a) creates a constant pointer, (b) allocates a sufficiently large memory segment (whose address is often referred to as the base of the array), and (c) points the pointer to it. Although the compiler knows the size of the array and the size of the allocated segment, the size is not recorded in any way and hence at run time the pointer holds only the base address, which is all that is known about the array; the knowledge of its size is gone. Unless the programmer remembered correctly the size of the array and worked with it properly in the rest of the program, all kind of problems can crop up during execution (as detailed in Chapter 3). There simply is no way a C/C++ program can make a run-time check of whether an array index is within the proper range.

This approach to arrays in C and C++ was deliberate . One of the aims of the C language designers was a language compiling to an object code that is as "lean" as possible. If one wants a language (e.g., Pascal) that facilitates run-time range checking, then arrays must be represented by special data structures that "remember" the range, increasing memory requirements. Moreover, every array access instruction of that language must be translated to a code that validates the range of the index before access to the array's storage, significantly increasing the size of the object code and memory requirements. (It is an interesting exercise to write two simple identical programs dealing with arrays, one in C and the other in Pascal, and - after compiling both - to compare the sizes of their respective object files.) Thus C and C++ compilers follow the philosophy of "compile-time checking": if you try to store more than the array can hold (e.g., during initialization of an array) or if some other "clear" violation of the index range occurs, the compiler will give you an error or a warning message. Run-time checking was deliberately omitted because of the associated costs. Consequently, the onus is on the programmer - which means you, the reader - to make sure that the range is not violated.

The second unpleasant consequence of having no array data type concerns passing of array arguments to functions during function calls. The C language professes to pass arguments exclusively by value, yet many a programmer has experienced (intentionally or unintentionally) a function call that somehow modified the array passed to it, as if it were passed by reference. In contrast, C++ is more flexible and gives you a choice between passing by value or by reference. Nevertheless, when passing an array by value, the program behaves as if it were passed by reference and when trying to pass it by reference, the compiler will not compile it! Consider the following simple program.

 /* function doit ----------------------------------------- */    void doit(int y[])    {       y[0] = 0;       y[1] = 1;    }/*end doit*/    /* function main ----------------------------------------- */    int main()    {       int i;       int x[6]={10,11,12,13,14,15};       doit(x);       for(i = 0; i < 6; i++)        printf("%d ",x[i]);       putchar('\n');       return 0;    }/*end main*/ 

This program will display, as values of the array x after the call to doit() , the numbers 0112131415 ; whereas we know that, prior to the call to doit() , they were 10 11 12 13 14 15 . Definitely, x has been modified and hence not passed by value.

The truth is that C does pass x by value; doit() receives the base address via the pointer y and then modifies the first two items that pointer y points to - in effect, the first two items of array x . For instance, let us assume that the base of array x is 80804048. When passing the array x to doit() , instead the base address 80804048 is passed to doit() by value. Locally in doit() , then, y was set to 80804048. In fact, y[0]=0 is the indirection *y=0 and so an integer value of 0 is stored at the address 80804048. The address 80804048 happens to be the address of x[0] . Similarly y[1]=1 was translated to *(y+1)=1 and so an integer value of 1 is stored at the address 80804052, which happens to be the address of x[1] (see Figure 6.4). Case closed.

Figure 6.4: The array x is accessible from the function doit()

An interesting curiosity : C programmers sometimes use the struct construct to "wrap" the arrays and so protect them from being modified by functions if passed to them. The following sample illustrates this technique.

 typedef struct { int array[6]; } wrap;    /* function doit ----------------------------------------- */    void doit(wrap y)    {       y.array[0] = 0;       y.array[1] = 1;    }/*end doit*/    /* function main ----------------------------------------- */    int main()    {       int i;       wrap x;       x.array[0] = 10;       x.array[1] = 11;       x.array[2] = 12;       x.array[3] = 13;       x.array[4] = 14;       x.array[5] = 15;       doit(x);       for(i = 0; i < 6; i++)        printf("%d ",x.array[i]);       putchar('\n');       return 0;    }/*end main*/ 

This program will display values of the "wrapped" array x , after the call to doit() , which are unchanged ( 10 11 12 13 14 15 ). The explanation is simple: the object x (the reader will forgive us for borrowing this C++ terminology, which is not fully appropriate here) is passed to doit() by value and hence the object y has the same value as x (i.e., it is a copy of x ). This copy gets modified, but the original x remains unchanged.

The reader should examine the header of the function doit(int y[]) . The program would work equally well if it were defined either as doit(int* y) or as doit(int y[6]) . This is the first meaningful example of a difference between a definition and a declaration that we have encountered in the book. A definition involves the "creation" of an object (data container) out of "raw" memory. A declaration, on the other hand, only introduces a symbol to the compiler together with what its type is and what it represents. Since we are passing an array to doit() as if by reference, no "creation" takes place; in reality, only a reference (pointer with the base address) is passed. Thus the expression used in the header of doit() is only a declaration, rather than a definition, because the compiler does not have to create the array. It is therefore perfectly acceptable to use either int y[6] (since conceptually we are passing an integer array of size 6 to doit() )or int *y (since we are really passing a pointer) or int y[] (since we are really passing an array reference).

The reader should now be comfortable with the notion that a static one-dimensional array is a pointer holding the base address and pointing to a (statically) allocated segment where the array items are stored. Similarly, readers should be comfortable with the idea that pointers can be indexed. In some sense, a pointer is like an array without a "body" - the segment to store the array items. It does not require a quantum leap of imagination to realize that we could provide the "body" dynamically during execution. This brings us to the concept of dynamic arrays.

A dynamic array is simply a pointer that is set to point to a dynamically allocated segment that will hold the array items. An illustration follows .

 /* function main ----------------------------------------- */    int main()    {       int i;       int* x;       x = malloc(6*sizeof(int));       if (x == NULL) exit(1);       x[0] = 10;       x[1] = 11;       x[2] = 12;       x[3] = 13;       x[4] = 14;       x[5] = 15;       for(i = 0; i < 6; i++)        printf("%d ",x[i]);       putchar('\n');       return 0;    }/*end main*/ 

The only difference from using a static array consists of the lines in which (i) the memory is allocated dynamically and (ii) the allocation is checked to see whether it has worked.

When should we use a dynamic rather than a static array? A static array is always preferable for two reasons: it is faster (dynamic memory allocation is a complex task; see Chapter 4) and it does not pose any danger of leaking memory. But if we do not know in compile time what would be a reasonable cap on the size of the array, or if the array needs to change to accommodate some more dynamically incoming data, then the safer and more efficient way is to use dynamic arrays. An obvious error ( especially with novices) is to "forget" the allocation part. This leaves the pointer uninitialized , and any attempt to store anything in its direction may well lead to the ill effects discussed in Chapter 3. A more ominous error consists of failing to deallocate the dynamic array once it is no longer needed (especially when the array is frequently extended and when realloc() , with its implicit deallocation of the old segment, is not used for the task), which may result in memory leaking; more on this in Chapter 10.

Having covered static and dynamic arrays, we can now turn our attention to strings. Unlike arrays, which are almost innate data types for C/C++, strings are much less so. The C/C++ language does not provide any means of defining and working with strings, with one exception: literal strings. Yet strings are immensely useful and even more ubiquitous than arrays, so something must be done to facilitate their use. In C/C++ programs the compiler stores literal strings in memory as character arrays terminated by the NULL character ( '\0' ), so the same convention is used for all strings. Simply stated, a string is a char array terminated with NULL . Thus a string can be stored in a static array,

 char x[30] = "hello"; 

or

 char x[30];    strcpy(x,"hello"); 

as well as in a dynamic array,

 char* x;    x = malloc(30);    strcpy(x,"hello"); 

In any case, a string is represented by a char* pointer that points to its beginning, and the string continues until NULL . All standard C functions dealing with strings (their prototypes are in the standard header file string.h ) expect the strings to be represented by char* pointers and terminated by NULL . Of course, these functions are not a part of the C/C++ language - they are not terms in the language. For instance, strcpy is not a reserved keyword of C/C++, nor is it meaningful in any way. The compiler realizes only that it is a call to a function, and the linker will try to find the object code for it and link it with the program. However, any C/C++ compiler comes equipped with object libraries that ought to include the object code for strcpy . Thus the programmer's task is (a) to "tell" the compiler what strcpy is (by including the standard header file string.h ), (b) to direct the compiler to the proper object libraries (automatic for the standard functions), and (c) to use the function properly.

For an illustration, we will examine two of the standard string functions: strcpy() and strcat() .

 char* strcpy(char* dest,const char* src)    {       char *dest1 = dest;       while((*dest++ = *src++) != NULL);       return dest1;    } 

There are two interesting aspects of the function strcpy() that concern memory. First, it is the user 's responsibility to provide sufficient memory for the string to be copied to (the pointer to points to it); this is often a source of overflow problems (see Chapter 3) when the memory provided is insufficient, or a source of memory access problems when the argument to is not set properly. Second, it neatly illustrates the essential role of the terminator NULL , since strcpy() will continue merrily copying until it reaches NULL . If NULL is not there, strcpy() will go through the whole memory (of course, the operating system will terminate it for memory access violation long before that). The sample program

 int main()    {       char* p;       strcpy(p,"hello");       return 0;    } 

will exhibit the whole range of erratic behavior described in Chapter 3, for we are trying to store a copy of the string "hello" wherever p happens to point. Similarly, the following code may exhibit erratic behavior owing to overflow:

 int main()    {       char* p;       p = malloc(4);       strcpy(p,"hello");       return 0;    } 

The most frequent error is forgetting to allocate storage for the terminating character at the end of the string. Thus, when making a copy of a string q , we must not forget to add 1 to the length of q as computed by strlen() (which does not include the terminator NULL ):

 char* p;    p = malloc(strlen(q)+1);    strcpy(p,q); 

The function strcat() is used to concatenate strings:

 char* strcat(char* dest,const char* src)    {       char* dest1 = dest;       while(*dest++ != NULL);       while((*dest++ = *src++) != NULL);       return dest1;    } 

As with strcpy() , it is the user's responsibility to provide enough memory after the end of the string dest to accommodate a copy of the string src . And again, if either of the strings is not properly terminated, the function will go through all memory until terminated by the operating system. Unfortunately, it is not always the case that the programmer is responsible for the allocation of memory; char* strdup(const char* src) will allocate the memory for a copy of the string src itself. This inconsistency may lead to programs with memory leaks (see Chapter 10).

The problem of when to use the static rather than the dynamic version of strings is the same as that for arrays, and likewise for the possible perils of using the dynamic version.

The final topic of this chapter will turn our attention to C++ and how we can provide arrays with run-time index range checking. Although we cannot provide this for the proper arrays, we can define a special class of such arrays. The following code illustrates a class of essentially int arrays that performs the index range checking (see the method Array::operator[] ) for any access.

 class Array {   protected:     int* body;     int last_index;   public:     Array(int k) {      //constructor       body = new int[k];       last_index = k-1;     }//end constructor     //destructor     ~Array() { if (body) delete[] body; body=0; last_index=-1; }     //subscript operator     int& operator[] (int i) {       if (i < 0  i > last_index)  // index is out of range         exit(1); // exit or throw an appropriate exception                  // or take an appropriate action       return body[i];     }//end subscript operator };//end class Array // function main ----------------------------------------------- int main() {    Array x(4);    x[0] = 1;    printf("%d\n",x[0]);    return 0; }//end main 

Of course, the class could be defined as a template class and as such would allow us to have all kinds of arrays, not only int . Nor would it be too complicated to make the array grow dynamically if need be, but for the sake of simplicity we did not include these variations. For the same reason we did not include the copy constructor. We could have also defined body statically (for fixed-length arrays), but we wanted to include some dynamic memory allocation in the example. The reader should examine the destructor ~ Array() , which guarantees that once an object of this class (static or dynamic) is destroyed , all dynamic memory linked to it is deallocated as well. Hence no memory will leak on account of the Array objects.

In Chapter 9 we will discuss linked data structures and will also briefly focus on arrays as models of memory, showing how linked data structures can be created without pointers and pointer arithmetic.