Lesson 2 C introduction and array

From C to C++

What is C++?

C++ is “evolving” extension of C

Reference versus Pointer

reference: C++ way of smarter/safer “pointer”

C:

c_swap(&x,&y);
void c_swap(int* pa, int*pb){
int tmp;
tmp = (*pa);
(*pa) = (*pb);
(*pb) = tmp;
}

C++:

cpp_swap(x,y);
void cpp_swap(int& a, int& b){ // like nickname
  int tmp;
  tmp = a;
  a = b;
  b = tmp;
}

Class versus Structure

class: C++ way of structure “with actions”

C:

typedef struct
{
double real;
double img;
}complex;

complex multiply(complex a, complex b){
/*create a complex variable res*/
/*put a.real*b.real-a.img*b.img in res.real*/
...
}

C++:

class complex{
public:
    double real;
    couble img;
    void multiplyby(complex another){
        // tighter than C
    }
}

Operator versus Function

operator overloading: C++ way of programming with (some) complicated classes more easily
C:

int a,b,c;
c = a + b;/*"built-in plus of int"*/

complex A,B,C;
C = plus(A,B);

C++:

complex A,B,C;
C=A+B;
//C++ complier "translate"
C = operator+(A,B);
C = A.operator+(B);

operator overloading tutorial

Template versus Copy/Paste

template: C++ way of automating safer copy/pasting by compilers

C:

int int_arr[10];
double double_arr[10];
complex complex_arr[10];
/*write this first*/
void int_sort(int int_arr){...}
/*copy/paste/replace*/
void double_sort(double double_arr){...}

C++:

template <class T>
void sort(T arr){...}

int int_arr[10];
sort(int_arr);
sort(complex_arr);

Standard Template Library in C++

STL:one data structure/algorithm can be applied to many classes

Array

What is Array?

• wikipedia: a collection of elements, each identified by one array index

array:numbered lockers
pointer: stores index to memory array

• Memory is (Generally Viewed as) Array

Array as Memory Block in C/C++

• access
  • data getByIndex(index):
    arr[index], which means
    memory[arr+index * sizeof(data)]
• maintenance
  • construct(length):
    • malloc(sizeof(data)*length) in C
    • new data[length] in C++
  • updateByIndex(index, data):
    arr[index] = data
• desired property: fast computation of address from index ===>fast random access

Array as Abstract Data Structure

• access
  • data getByIndex(index)
  • insertByIndex(index, data)
• maintenance
  • construct(length)
  • updateByIndex(index, data)
  • removeByIndex(index)
• implict assumption: index to address done by fast math formula

C++ STL Vector: a Growing Array

• access: two more feature supported with automatic growing
  • insertByIndex(index, data)
  • insertAtBack(data)
• maintenance: one more feature supoorted
  • removeByIndex(index)
• STL vector: a more “structured” way of using arrays

Two Dimensional Array

One Block Implementation of 2-D Array

• access
  index = (row, col)
  • data getByIndex(index)
  • address = arr + sizeof(data) _ (row_nCol+col)
• maintenance
  length = (nRow, nCol)
  • construct(length)
    arr = new data[nRow * nCol]
• fast math formula: arithmetic

Array of Array Implementation of 2-D Array

pointer to tell the header address of each row

• access
  index = (row, col)
  • data getByIndex(index)
    address = arr[row] + sizeof(data) *col
    arr[row][col]
• maintenance
  length = (nRow, nCol)
  • construct(length)
    arr = new data*[nRow]
    arr[c] = new data[nCol] for all c

Comparison of Two Implementation

tradeoff: one block usually faster;
array of array often easier for programmers

example : array of store upper/lower/symmetric matrix

A Tale Between Two Programs

• row sum

int rowsum(){
    int i,j;
    int res = 0;
    for (i=0;i<MAXROW;i++)
        for(j=0;j<MAXCOL;j++)
            res += array[i][j]
}

• column sum

int colsum(){
    int i,j;
    int res = 0;
    for(j=0;j<MAXCOL;j++)
        for(i=0;i<MAXROW;i++)
            res += array[i][j];
}

Which is faster?

knowing architecture helps

• every time fetch lots of neighbored storage blocks ——> computer OS, architecture

Ordered Array

Definition of Ordered Array

an array of consecutive elements with ordered values
arr[0] <= arr[1]<=arr[2]<=…<=arr[end-1]

insert of Ordered Array

normal array: insertByIndex, updateByIndex
{3, 7, 9, 10, 25, 25, 27}
insert(13)
insertByIndex(13,0)

“cut in” from the back