Getting Started

Array manipulation

Almost every C program contains an array, and almost every C programmer has made his or her share of array programming errors. Two of the most troublesome kinds of array errors are array reallocation errors and algorithmic array errors. We provide two separate components in C++ Standard Components to target these errors: the Block component and the Array algorithms component.

Array reallocation errors

Arrays in C (and C++) have fixed size. Applications that can't predict an array's size in advance must therefore simulate dynamic array growth using a three-step procedure when the array becomes full:

allocate a new, larger array;
copy the contents of the old array into the new array;
free the old array.

This procedure, called array reallocation, typically looks something like this:

       #include <malloc.h>
       int i,size,newsize;
       int *q, *ip, *iq;
       int index;
       ...
       int* p = (int*)malloc(size*sizeof(int));
       ...
       if (index>=size) {
           newsize = index < 2*size ? 2*size : index+100;
           q = (int*)malloc(newsize*sizeof(int));
           ip=p;
           iq=q;
           for (i=0;i<size;i++)*iq++ = *ip++;
           free(p);
           p=q;
           size=newsize;
       }
       p[index] = 10;

Considering the conceptual simplicity of reallocation, the complexity of its implementation is remarkable. No wonder programmers make so many reallocation errors!

The Block component adds a reallocation feature to ordinary C arrays, plus a few additional features that make arrays easier and safer to work with. The following code uses Block(C++) to solve the same problem as above:

       #include <Block.h>
       //  Block.h contains the template class definition
       //  for instantiating Block<int>.
       int size,index;
       ...
       Block<int> b(size);
       ...
       b.reserve(index);  // guarantees b[index] is
                          // a valid cell
       b[index] = 10;

Note that the Block does not resize itself automatically. We chose not to abstract away this one important detail because ``real'' C programmers insist on controlling (1) when reallocation occurs and (2) how much excess memory to acquire during reallocation. Also note that - except for declaring and reallocating - Blocks look and behave exactly like arrays.

Of course, Blocks of integers could be resized just as easily using the C library function realloc() (see malloc(S). The beauty of Block(C++) is that it works with user-defined types as well as built-in types:

       #include <String.h>
       ...
       Block<String> b(size);
       ...
       b.reserve(index);

or even

       typedef Block<String> String_block;
       Block<String_block> b(size);
       ...
       b[i].reserve(index);

Algorithmic array errors

Even after reallocation errors are eliminated, it is easy to make algorithmic errors when manipulating array contents. Consider code that moves n elements from location from to location to:

       int* from;
       int* to;
       unsigned n;
       ...
       while (n--) {
           while (n--)*to++ = *from++;
       }

This fails when the two arrays overlap, a possibility unlikely to occur to the programmer in release 1. In the next release, the programmer might come up with the following algorithm, which is general and efficient:

       int* end = from + n;
       if (from < to) {
           to += n;
           while (from < end) *--to = *--end;
       }
       else if (to < from) {
           while (from < end) *to++ = *from++;
       }

Alternatively, the programmer could have used the copy() function, one of nearly 100 highly efficient algorithms for operating on contiguously stored data provided by the Array algorithms component:

       #include <Array_alg.h>
       //  Array_alg.h contains template function
       //  declarations for nearly 100 functions
       //  that operate on contiguously stored data,
       //  including "void copy(int*,int*,int*)"

       const N = 100;
       int a1[N];
       int a2[N];
   
       main() {
           ...
           copy(a1,a1+N,a2);
       }

We used the phrase ``contiguously stored data'' rather than ``arrays'' for an important reason: Array algorithms can be used not only on arrays, but on any contiguously-stored data, including Blocks. In fact, you will probably use Array algorithms with Blocks because of the way these two components neatly partition the algorithmic and memory management aspects of working with arrays. Using Blocks, the above example becomes:

       #include <Array_alg.h>
       #include <Block.h>

       const int N = 100;
       main() {
           ...
           Block<int> a1(N);
           Block<int> a2(N);
           ...
           copy(&a1[0],&a1[N],&a2[0]);
       }

To read more about the Block and Array algorithm components, see the tutorials ``No More Array Errors (Part I) - Block(C++)'' and ``No More Array Errors (Part II) - Array_alg(C++)'' later in this guide.