Object Oriented Programming (CS-504 (B)) Unit 3 Notes

How unit 3 is examined

This unit covers arrays (1D, 2D, multidimensional), their memory layout, and C-style strings with the library functions; the paper asked array definition and initialization, 2D versus multidimensional arrays, and strlen/strcpy/strcat.

Array: what are arrays

Low weight

Definition. An array is a collection of similar (same data type) elements stored in contiguous memory locations and accessed by a common name and an index.

Key points.

All elements of an array have the same data type, for example int marks[5] holds five integers only.
Elements occupy consecutive memory locations, so the address of any element is found directly from its index.
The index starts at 0, so an array of size $n$ has valid indices $0$ to $n-1$.
Declaration syntax is datatype name[size]; and the size must be a constant known at compile time.

Example.

#include <iostream>
using namespace std;
int main(){
    int a[5]={10,20,30,40,50}; int sum=0;
    for(int i=0;i<5;i++){ cout<<"a["<<i<<"] = "<<a[i]<<endl; sum+=a[i]; }
    cout<<"Sum = "<<sum<<endl;
}
// a[0] = 10 ... a[4] = 50
// Sum = 150

Answer frame. Open with the definition; write declaration and initialization (see next topic); give the program above with its output; close with "elements are read by index from 0 to n-1".

Asked: [7 marks] (Jun 2020) Define Array. How it is initialized? Write appropriate program.

Array initialization

Definition. Initialization gives an array its values at the time of declaration, inside braces.

Key points.

Full initialization lists every value: int a[3]={1,2,3};.
If the size is omitted the compiler counts the values: int a[]={4,5,6}; makes size 3.
Partial initialization fills the rest with zero: int a[5]={1,2}; gives 1 2 0 0 0, and int a[5]={0}; zeroes everything.
Without an initializer a local array holds garbage values, while a global or static array is zero.

Bound checking 1D array

Definition. Bound checking means verifying that an index lies between 0 and size-1 before it is used.

Key points.

C and C++ do not check array bounds, so a[10] on int a[5] compiles without any error.
Writing outside the array overwrites neighbouring memory, causing wrong results or a crash (undefined behaviour).
The programmer must check the index, for example if(i>=0 && i<5) a[i]=x;.
The last valid element of an array of size $n$ is a[n-1].

2D array initialization of 1D and 2D array

Definition. A 2D array is an array of 1D arrays, arranged as rows and columns and declared as datatype name[rows][cols];.

Key points.

Row-wise initialization: int m[2][3]={{1,2,3},{4,5,6}}; puts one brace group per row.
Flat initialization int m[2][3]={1,2,3,4,5,6}; also works because values fill row by row.
The column size is compulsory, the row size may be omitted: int m[][3]={{1,2,3},{4,5,6}};.
An element is accessed as m[i][j], so m[1][2] is 6; missing values become zero.

Memory map of 1D and 2D array

Definition. The memory map shows how array elements are laid out in linear memory; C and C++ use row-major order for 2D arrays.

Formula. With base address $B$ and element size $w$:

$$\text{1D: } addr(a[i]) = B + i\times w$$ $$\text{Row-major: } addr(a[i][j]) = B + (i\times C + j)\times w$$ $$\text{Column-major: } addr(a[i][j]) = B + (j\times R + i)\times w$$

Key points.

In 1D, elements sit one after another, each $w$ bytes apart (2 or 4 bytes for int).
Row-major order stores the whole of row 0, then row 1, and so on; C and C++ use it.
Column-major order stores column 0 first, then column 1 (used by FORTRAN).
Example: int a[3][4], $B=1000$, $w=4$: row-major a[1][2] = $1000+(1\times4+2)\times4=$ 1024; column-major = $1000+(2\times3+1)\times4=$ 1028.

Multidimensional array

Definition. A multidimensional array has two or more dimensions, declared as datatype name[s1][s2]...[sn];, and a 2D array is its simplest case with exactly two.

Key points.

A 2D array is a table of rows and columns and needs two indices, a[i][j].
A 3D array such as int a[2][3][4] is 2 tables of 3 rows and 4 columns and needs three indices.
Total elements are the product of all sizes, so a[2][3][4] holds 24 and a[3][4] holds 12.
All are stored in row-major order and initialized with nested braces.

Basis	2D array	Multidimensional array
Dimensions	Exactly two (rows, columns)	Two or more, commonly three or above
Declaration	`int a[3][4];`	`int a[2][3][4];`
Indices	Two: `a[i][j]`	One per dimension: `a[i][j][k]`
Elements	$r\times c$ = 12	Product of all sizes = 24
Memory	Row-major, $(i\times C+j)\times w$	Row-major, extended formula
Use	Matrices, tables	3D data, image frames, time series

Answer frame. Open by defining a 2D array with int a[3][4];; then define a multidimensional array with int a[2][3][4];; draw the table above; close with "a 2D array is a special case of a multidimensional array".

Asked: [7 marks] (Jun 2020) Differentiate between 2D array and Multi-dimensional array.

Strings: what are strings

Definition. A string in C/C++ is a character array terminated by the null character '\0'.

Key points.

It is declared as char s[10]; and initialized as char s[]="Hello"; or char s[]={'H','i','\0'};.
The compiler adds '\0' automatically for a string literal, so "Hello" needs 6 bytes.
cin>>s reads one word only; cin.getline(s,size) reads a line with spaces.
Functions of <cstring> (or <string.h>) work by scanning until '\0'.

Standard library string functions

Definition. The header <cstring> provides ready-made functions on null-terminated strings: strlen(), strcpy(), strcat() and strcmp().

Key points.

strlen(s) returns the number of characters before '\0', not counting it; strlen("Hello") is 5.
strcpy(dest, src) copies src, including '\0', into dest, so dest must be large enough.
strcat(dest, src) appends src at the end of dest and returns dest; dest must have room for both.
strcmp(s1, s2) returns 0 if equal, a negative value if s1 is smaller and a positive value if larger (dictionary order).

#include <iostream>
#include <cstring>
using namespace std;
int main(){
    char s1[20]="Hello", s2[20];
    cout<<"Length = "<<strlen(s1)<<endl;
    strcpy(s2,s1);
    cout<<"Copy = "<<s2<<endl;
    strcat(s1," RGPV");
    cout<<"Joined = "<<s1<<endl;
}
// Length = 5
// Copy = Hello
// Joined = Hello RGPV

Answer frame. Open by naming <cstring>; give syntax, purpose and return value of each function in turn; write the program above with output; close with a note that strcmp gives 0 for equal strings.

Pitfall: the question spells strcpy as "strcp"; write strcpy(dest, src) with the destination first.

Asked: [7 marks] (Jun 2020) Explain the function strlen( ), strcp( ) and strcat( ) with example.

2D array of characters

Definition. A 2D character array stores several strings, one string per row: char names[3][10];.

Key points.

Each row is one null-terminated string, so the column size must fit the longest string plus '\0'.
It is initialized as char names[3][10]={"Amit","Ravi","Sita"};.
names[1] is the string "Ravi" and names[1][0] is the character 'R'.
Each string is read or printed with one index, such as cout<<names[i];.

Last-minute revision

An array is a collection of same-type elements in contiguous memory with a common name.
Valid indices for size $n$ are 0 to $n-1$; C/C++ do not check bounds.
int a[5]={1,2}; leaves the remaining elements as 0.
1D address: $B+i\times w$.
Row-major address: $B+(i\times C+j)\times w$; column-major: $B+(j\times R+i)\times w$.
With $B=1000$, int a[3][4], a[1][2] is at 1024 (row-major) and 1028 (column-major).
Total elements of a multidimensional array is the product of its sizes.
A string is a char array ending with '\0'; "Hello" takes 6 bytes.
strlen excludes '\0'; strcmp returns 0 for equal strings.
Column size is compulsory in 2D initialization.

Memory hooks

Array = "same type, side by side, start at zero".
Row-major: read a page like a book, row by row (C/C++).
strlen counts, strcpy copies, strcat chains, strcmp compares.
String = characters + '\0', so always one extra byte.

Coverage checklist

Array: what are arrays: Jun 2020 (Define Array, initialization, program).
array initialization: no past question.
bound checking 1D array: no past question.
2D array initialization of 1D and 2D array: no past question.
memory map of 1D and 2D array: no past question.
Multidimensional array: Jun 2020 (2D versus multidimensional).
Strings: what are strings: no past question.
standard library string function strlen(), strcpy(), strcat(), strcmp(): Jun 2020 (strlen, strcp, strcat).
2D array of characters: no past question.

Account

Object Oriented Programming (CS-504 (B)) - Unit 3 Short Notes

How unit 3 is examined

Array: what are arrays

Array initialization

Bound checking 1D array

2D array initialization of 1D and 2D array

Memory map of 1D and 2D array

Multidimensional array

Strings: what are strings

Standard library string functions

2D array of characters

Last-minute revision

Memory hooks

Coverage checklist