Arrays
------

Reading:  Chap 9.5, 10.4, 10.5

0) Introduction

   - arrays - aggregate of similar types
     - arrays in C++ are similar to Java
     - although there are several important differences

   - outline
     - declaration and use
     - relationship between arrays and pointers
     - dynamic allocation of arrays
     - character arrays
     - multi-dimensional arrays


A) Declaration and Use

     #define N 3    // preprocessor directive, not understood by compiler
     int a[N];      // defines a[0], a[1], a[2]

     int b[5] = {1, 2, 3, 4, 5};  // similar to b[0] = 1; b[1] = 2; etc.
     int c[5] = {0}; // initializes a 0 array

     i = 2;
     x = a[i]; // read element at index is i (i+1 th element)

   - arrays always start at 0 index

   - two key differences with Java
     - C++ does not keep track of the size of array
       => there is no out-of-bounds check!
       x = b[7]; // will probably not complain but will return garbage into x
       - common mistake: x = a[N];  // out-of-bounds
     - array sizes (as declared above) are fixed
       - cannot be changed dynamically
       
   - passing array parameters
     
     - arrays are passed by reference because they are pointers. see below
       
       int func(int a[]); // function declaration
     
       func(b);           // function call


B) Arrays and Pointers

   - special relationship
     - name of an array is also a pointer to the first element of the array

   - e.g.
     int p[4] = {4, 3, 2, 1};

     *p is the same as p[0]

                         Address X 4
          ___________
         |___________|  4000000
         |___________|  3999999
         |___________|      ...
       p |_ 300000 __|   400000
         |___________|      ...
         |______ 1 __|      ..3
         |______ 2 __|      ..2
         |______ 3 __|      ..1
       x |______ 4 __|   300000
         |___________|      ...
         |___________|        5
         |___________|        4
         |___________|        3
         |___________|        2
         |___________|        1
         |___________|        0
 
                                  p[0]    p[1]    p[2]    p[3]
          ___________            _______________________________
       p |___________|------> x |__ 4 __|__ 3 __|__ 2 __|__ 1 __|
         (pointer to int)       (int)


    - pointer arithmetic is possible
      *(p + 1) is the same as p[1]
      - confusing, unless you understand the memory model

    - note that + 1 above adds an integer amount (4 bytes) to the value of p


C) Dynamic Allocation of Arrays

   - static allocation
     int b[5];          // size cannot be changed. please don't forget.

   - allocation
       int *p;            // pointer to int, intent to use it as an array
       std::cin >> n;     // read in size of array
       p = new int[n];    // new operator dynamically allocates memory
                          // allocates n ints
                          // p is pointer to first element
     - p is an array
     - p[0], p[1], ... p[n-1] are usable
     - note that the value of n must be managed by the user
     - out-of-bounds access still possible

   - deallocation
     - delete [] p;
     - n does not have to be specified


D) Character Arrays

   - special type of array that stores single byte characters
     - uses a special convention to terminate the array
     - C++ arrays don't store size of the array

   - e.g.

     char c[n];

      c[0]   c[1]   c[2]   ...   c[n-2] c[n-1]
      _________________________________________
     |      |      |      |      |      |      | 
     |  H   |  e   |  l   |  l   |  o   | NULL |
     |______|______|______|______|______|______|

     char c[6] = "Hello";   // c[5] is NULL (or char 0, different from '0')

     char c[10] = "Hello";  // adds NULLs from c[5] onwards

     char c[4] = "Hello";   // simply puts Hell, no NULL, big problem

     char c[] = "Hello";    // compiler allocates 6 characters
                            // including one for NULL

   - string copy

     char c[6];
     strcpy(c, "Hello");    // have to ensure that c has six spaces
     char d[27];
     strcpy(d, c);
     strcat(d, ", ");
     strcat(d, "careful about space");

   - comparing strings

     strcmp(c, "Hello")

     - returns 0 if the two are equal
     - returns -1 if c is lexicographically less than "Hello"
       - lexicographic comparison compares char at a time, left -> right
     - returns +1 if c is lexicographically more than "Hello"

   - converting between character arrays and integers

     char a[5] = "1000";
     char b[5];
     int n;

     n = atoi(a);             // convert string to int
     sprintf(b, "%d", n);     // convert int to string

   - difference between "char *a" and char a[5];
       
       
       
E) Multi-Dimensional Arrays

   1) Statically allocated 2-d arrays

      int a[3][5];


         0      1      2      3      4
       __________________________________
      |      |      |      |      |      |
    0 |      |      |      |      |      |
      |______|______|______|______|______|
      |      |      |      |      |      |
    1 |      |      |  X   |      |      |
      |______|______|______|______|______|
      |      |      |      |      |      |
    2 |      |      |      |      |      |
      |______|______|______|______|______|

      - row major allocation
      - a[1][2] shows an X

                  ---> *(a[1] + 2)
                 /                   \
                /                     \
      - a[1][2]      avoid the mess    ---> *(*(a + 1) + 2)
                \                     /
                 \                   /
                  ---> (*(a + 1))[2]

   2) Dynamically allocated 2-d arrays

      - Take advantage of the special relationship between arrays and pointers

      int **a;              // pointer to pointer to int

      a = new int * [3];    // (int *) is the type
      for (int i = 0; i < 3; i++) {
          a[i] = new int [3 + i];  // ragged array
      }

           a            0      1      2      3      4
         _____        _____________________
        |     |      |      |      |      |
     0  |     | -->  |      |      |      |
        |_____|      |______|______|______|______
        |     |      |      |      |      |      |
     1  |     | -->  |      |      |  X   |      |
        |_____|      |______|______|______|______|______
        |     |      |      |      |      |      |      |
     2  |     | -->  |      |      |      |      |      |
        |_____|      |______|______|______|______|______|
      
      - X is accessed via a[1][2]!


F) Tutorial

   1) Simple implementation of strcpy().

      char *
      strcpy(char *dest, const char *src)
      {
          int i;
          for (i = 0; src[i]; i++) {
              dest[i] = src[i];
          }
          dest[i] = 0;  // '\0'
      }


   2) Implement a function to dynamically increase the size of an integer array. Make sure that the resize retains the old elements.


   3. (Tougher) Now modify the function above so that it will resize an array of any type (including structs). Hint: Look up the man page for memcpy() (run "man memcpy"). What is the difference between strcpy and memcpy?