tpop(2.6): Growing Arrays

2.6 Growing Arrays

2011-03-18 Fri

Growing a sorted array by inserting n elements one at a time is an O(n²) operation that should be avoided if n is large.

Often, though, we need to keep track of a variable but small number of things, and arrays can still be the method of choice. To minimize the cost of allocation, the array should be resized in chunks, and for cleanliness the array shoud gathered together with the information necessary to maintain it. In C++ or Java, this would be done with classes from standard libraries; in C, we can achieve a similar result with a struct.

The following code defines a growable array of Nameval items; new items are added at the end of the array, which is grown as necessary to make room. Any element can be accessed through its subscript in constant time. This is analogous to the vector classes in the Java and C++ libraries.

typedef struct Nameval Nameval;
struct Nameval {
        char *name;
        int value;
};

struct NVtab {
        int nval; /* current number of values */
        int max; /* allocated number of values */
        Nameval *nameval; /* array of name-value pairs */
} nvtab;

enum { NVINIT = 1, NVGROW = 2};

/* addname: add new name and value to nvtab */
int addname(Nameval newname)
{
        Nameval *nvp;
        if (nvtab.nameval == NULL) {/* first time */
                nvtab.nameval = (Nameval *)malloc(NVINIT * sizeof(Nameval));
                if (nvtab.nameval == NULL)
                  return -1;
                nvtab.max = NVINIT; /* initial 1 to be the array size */
                nvtab.nval = 0;
        } else if (nvtab.nval >= nvtab.max) { /* grow */
                nvp = (Nameval *) realloc(nvtab.nameval, (NVGROW*nvtab.max) * sizeof(Nameval));
                if (nvp == NULL)
                  return -1;
                nvtab.max *= NVGROW;
                nvtab.nameval = nvp;
        }
        nvtab.nameval[nvtab.nval] = newname;
        return nvtab.nval++;

}

The function addname returns the index of the item just added, or -1 if some error occurred.

The call to realloc grows the array to the new size, preserving the existing elements, and returns a pointer to it or NULL if there isn't enough memory. Doubling the size in each realloc keeps the expected cost of copying each element constant: if the array grew by just one element on each call, the performance could be O(n²).

The return value of realloc does not need to be cast to its final type because C promotes the void* automatically. But C++ does not; there the cast is required.

Deleting a name can be tricky, because we must decide what to do with the resulting gap in the array. If the order of elements does not matter, it is easiest to swap the last element into the hole. If order is to be preserved, however, we must move the elements beyond the hold down by one position:

/* delname: remove first maching nameval from nvtab */
int delname(char *name)
{
        int i;
        for (i = 0; i < nvtab.nval; i++)
          if (strcmp(nvtab.nameval[i].name, name) == 0) {
                  memmove(nvtab.nameval+i, nvtab.nameval+i+1, (nvtab.nval-(i+1)) * sizeof(Nameval));
                  nvtab.nval--;
                  return 1;
          }
        return 0;
}

The call to memmove squeezes the array by moving the elements down one position; memmove is a standard library routine for copying arbitrary-size blocks of memory.

Rules:

• Arrays are the simplest way to group data.
• Arrays are easy to use, provide O(1) access to any item, word well with binary search and quicksort, and haove little space overhead.
• For fixed-size data sets, which can be even be constructed at compile time, or for guaranteed small collections of data, arrays are unbeatable.
• But maintaining a changing set of values in an array can be expensive, so if the number of elements is unpredictable and potentially large, it may be better to use another data structure.