1.3 Array

• All language support array and think it as build-in data type.
  //C/C++ language 
  int a[3]; or int a[4][5]. 
  STL vector<int> (4,0); 
   
  //C# language 
  object[] a1 = {"string", 123, true};
• Array support three basic operations: Index, insert, delete(erase in STL).
• Dynamic two dimension array can be implemented below: char ** p; should be used as ragged array. Pay attention to p[1][2] and pa[1][2]. They are all correct forms.
• All ragged array should include terminate flag, so you can know the length of each row. For C-style string ragged array, the ’NULL’ in the end of string can be used as terminate flag directly, so ragged array is idea container for C-style string array.
  char **p; 
  char* a[]={"zhao","yan","hello"}; 
  p = a; 
  printf("%c\n",*(*(p+1)+2)); //p[1][2] 
   
  int (*pa)[3]; 
  int aa[2][3] = {{1,2,3},{4,5,6}}; 
  pa = aa; 
  printf("%d\n",pa[1][2]);//*(*(pa+1)+2);
• If you want to insert an element into an array, you need to copy backward from end. if erase an element from an array, copy forward from erasing point.

  
  

• If you have an array of big object, and you need to sort it. You can build a array of pointer to point to each object in the array. When you sort the an array of big object, you just move pointer instead, It is called "indirect addressing", It can help you to avoid moving big chunk of data. If you want to put them into STL container, you can use smart pointer, such as unique_ptr. Don’t use auto_ptr.
• reverse array can be implemented by swap, But reverse list need different algorithm, so in STL , list<> has its own reverse member function.
  1) Initialize start and end indexes. 
          start = 0, end = n-1 
  2) In a loop, swap arr[start] with arr[end] and change start and end as follows. 
          start = start + 1;  end = end - 1
• Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.
  1. single rotate method
     leftRotate(arr[], d, n) 
     start 
       For i = 0 to i < d 
         Left rotate all elements of arr[] by one 
     end 
     //***********************// 
     To rotate by one, store arr[0] in a temporary variable temp, move arr[1] to arr[0], arr[2] to arr[1] ... and finally temp to arr[n-1]
  2. reverse method
     rotate(arr[], d, n) 
       reverse(arr[], 1, d) ; 
       reverse(arr[], d + 1, n); 
       reverse(arr[], l, n);

     Idea: middle part reverse twice, so keep origin value

  3. block swap method