Friday, November 11, 2011

C/C++ Arrays with Arbitrary Start Index

Can you have a C/C++ array with any start index? Yes, provided they are created dynamically.

Arrays in C/C++ are indexed starting with zero. Arrays created at compile time (static arrays) always begin with the index zero and cannot be changed. Thus float x[10] creates an array with 10 elements are accessed using indexes starting from 0 up to 9 as x[0] to x[9]. The index of the initial element will always be zero. This is because of the way arrays are defined in C/C++. Name of an array is a constant pointer to the initial element of the array. As a result, an array cannot be re-sized at run time and neither can the name point to a different memory location at run time.

Arrays created at run time (dynamic arrays) using dynamic memory allocation are more flexible than static arrays. Firstly, their size can be changed at run time by reallocating memory (for example, by using realloc() function). Secondly, by repositioning the pointer to which memory is allocated suitably.

Let us demonstrate realloc():

#include <stdio.h>
#include <stdlib.h>


main() {
  float * p;
  int i, n;


  printf("Enter size of array: ");
  scanf("%d", &n);
  p = (float *) malloc(sizeof(float) * n);


  for(i = 0; i < n; i++) {
    p[i] = i + 1;
    printf("%6.2f ", p[i]);
  }
  printf("\n");


  printf("Enter new size of array: ");
  scanf("%d", &n);
  p = (float *) realloc(p, sizeof(float) * n);


  for(i = 0; i < n; i++) {
    printf("%6.2f ", p[i]);
  }


  free(p);
}
Note: that program does not test whether memory allocation was successful, which is not a good practice, but let us ignore it for the moment.

If the size of the array specified second time is smaller than the first time, contents of the array are same as before, except that there are fewer elements. If the size specified second time is greater than the first time, and if memory allocation is successful, values in the elements up to the elements in the first array are unchanged while the values of the rest of the elements are undefined.

Let us now demonstrate how we can shift the pointer so that we can choose the index of the initial element of the array. Let us assume that we want the initial element to be indexed as 1 instead of 0. We can achieve this by shifting the pointer back by one element. The memory location to which the pointer points is now 0. This makes the memory location to which the pointer initially pointed 1. Here are the points to keep in mind:
  1. After shifting the pointer back, pointer points to a memory location which was not allocated to it. Hence the pointer must neither read from or write to this memory location. Thus, pointer must only use indices 1 to 10.
  2. Before freeing up the memory allocated to the pointer by using the function free(), it must first be reset to the memory location allocated to it.
Here is a diagram to illustrate this concept:

Here is a program to illustrate how this is done:
#include <stdio.h>
#include <stdlib.h>

int main() {
  float * p, * p1;
  int i, n;

  printf("Enter size of array: ");
  scanf("%d", &n);
  p = (float *) malloc(sizeof(float) * n);
  p1 = p;
  p--;

  for(i = 1; i <= n; i++) {
    p[i] = i;
    printf("(%6.2f, %6.2f) ", p[i], p1[i-1]);
  }
  printf("\n");

  p++;
  free(p);
}
Note the following points:
  1. After allocating memory to the pointer 'p', a second pointer 'p1' is made to point to the same memory location.
  2. Pointer 'p' is then decremented. Thus, the element p[1] is the same as the element p1[0]. You could check this by printing the address of the elements instead of their values.
This can be generalized. If you want the initial element to be indexed as 2, the pointer must be shifted backwards by two elements and if you want the initial element to be indexed 'n', pointer must be shifted backwards by 'n' elements. This could be achieved by the statement p -= n. You will appreciate that this works even when 'n' happens to be negative, that is, when you want the initial element to have a negative index. If 'n' is negative, the pointer gets pushed forward instead of backward.

This brings a few questions:
  1. Can we do the same for two dimensional arrays? Answer is, we can do something similar, using the concept of pointer to an array of pointers. To the given pointer, allocate an array of pointers equal to the number of rows (or columns in case you want elements to be stored column-wise). To each pointer in this array, allocate memory to hold one row (or column if elements are to be stored column-wise). This would make the memory allocated to the array dis-contiguous. If you wanted memory allocated to an array to be contiguous, you could allocate enough memory to hold the entire array, also allocate memory for pointers and position the pointers appropriately to point to the initial element of each row. It would however be difficult to extend this logic automagically to n-dimensioned arrays.
  2. Can it be done in C++? Obviously, yes. In fact you could use the operators new and delete to dynamically allocate and delete memory. You could additionally use a class template to create arrays of any data type. You could also define operators such as +, -, *, but they would make sense only for numeric arrays.
References
  1. Numerical Recipes in C by Press, W.H., Teukolsky, S.A., Vetterling, W.T. and Flannery, B.P. The above implementation is described in this book.
  2. http://pubs.opengroup.org/onlinepubs/7908799/xsh/realloc.html

No comments:

Post a Comment

Your comments are ciritical input for the sustainance and improvement of this blog.