Sunday, June 26, 2011

All about Array in C/C++

All about Arrays in C and C++


Introduction
This article tries to cover all about Arrays like from it's definition till it's usage using a single dimension.
Definition
An array is a built-in Data Structure that holds a sequence of variables of same data type, that are stored in a contiguous memory locations.

Some characteristics about Arrays
The elements of an array are indicated and accessed by their index, where as first position/index of an array starts from "0" and last position is sizeOfArray-1 !!
By default, Arrays are not initialized.
Like any other variable, an array must be declared before it is used.
Each element in an Array must be printed individually.
An Array cannot be copied/assigned/compared from another Array directly, these operations have to be done element by element basis.
Name of the Array is nothing but address of/pointer to the first element of the Array
There is no Array bound checking done in C. Trying to access the position at sizeof Array or beyond that is an Error and results in an undefined behavior.
ArrayName indicates the base address or address of the first element in the Array.
Address of any element in a Single Dimensional Array can be calculated as

ElementAddress = BaseAddress+ indexOfTheElement * SizeOfTheElement

Declaration of an Array
Declaration of an array takes data_type of the elements to be stored, variable name followed by the size of the array wrapped within square brackets as below:

data_type variableNameOfArray[no_elements]

Example:
int employee[5] = {10,20,30,40,50};

where employee is the name of a single dimensional array variable, that can hold 5 variables of integer type. So, the number 5 indicates the size of the array employee. 
Where "0", "1", "2", "3", "4" shows the indices of the array employee. Any element of an Array, can be accessed by using it's respective index inside [] as below:

printf("%d", employee[2]);

This will access and print the 3rd element i.e. 30 of the Array employee.

Array Initialization
We can Initilize an Array when it is declared. Initializers are constant values/expressions seperated by a comma and enclosed within flower braces {} as below:

dataType variableNameOfArray[no_elements] = {values}

int employee[5] = {120, 121, 122, 123, 124};

As a convenience, if you leave out the size of the array, it creates it with the exact size to hold that number of initial values.

int employee[] = {120, 121, 122, 123, 124};

The elements in the aggregate that are not given initilizers are default initialized according to their data type.


In this code, only the array index 0 and 1 are initialized with values 1 & 2, whereas rest of the elements in the array will be initialized with zeros.

Also, We can initialize all the elements of an integer Array with 0 value by assigning with empty {} as below:

int array[5] = {};

Array Initialization in a class
Arrays are always initialized outside the class. Usually static const data types are initialized inside the class declaration, but, static const Arrays are also initialized outside the class declaration as below:


Size of an Array
Irrespective of whether an Array is initialized or not, the size of an Array is nothing but ;

sizeOf(dataType of the element) * arraySize.
Example:

The above code also confirms that by default array elements are not initialized.

Arrays and References
We cannot have an Array of references. Whereas we can have a Reference to an Array as an argument to a function.
Pointer Arithmetic and Arrays
Address to a first element of an Array is nothing but Array name itself and it is a pointer of it's element type or Array type. Adding 1 to this pointer, gives the address of the next element in the Array. It means, it adds with 1*sizeOf(elementDataType) to the base address of the array.
For Example:
int array[3] = {10,20,30};
cout << "*(array+1)" << *(array+1) << endl;

Results the content of second element i.e. "20". array+1 adds (1*4) to the base address i.e. array and gives the content of that address. Where 4 is size of an int nothing but size of an element of array here!!

In other way we can say

array or array+0 ----> &array[0]

*array -----> array[0]

And

array+1 ------> &array[1]
*(array+1) -----> array[1]

.
.
.

array+i --------> & array[i]
*(array+i) ------> array[i]

Same way, we can as well do subtraction here.

By seeing these examples, we can say that array behaves like a pointer, but really it is not. As we cannot assign values to it as below:
Code: Cpp
int arr[5];
int j;
arr = &j // gives complation error!!
 

But however we can assign an array name to a pointer as below:
Code: Cpp
int arr[5];
int *p = arr; or
p = &arr[0]

Static and Dynamic Array allocation

int employee[5];

When an Array is declared like above, the memory is allocated for all the elements of it and it will be there till the life time of the program. This is called as Static Array allocation. So, here the developer knows in advance the size of the Array at compile time itself.

In case, if the developer does not know the Array size at compile time, then Array can be allocated at run time as well. This is called as Dynamic Allocation of an Array.



See a more detailed analysis on dynamic memory allocation in C


Arrays of Characters

Arrays of characters are special, as we can Initialize the Array using string literals as below:

char array[8]= {'M', 'r', 'i', 'd', 'u', 'l', 'a'}
char array[8]= "Mridula";


Here we can see that Mridula can be Initized as a string !!

Also, if some of the elements in character Arrays are not given initizers, then they will be initilized with NULL or '\0' character.As like initeger Arrays, character arrays are also can be initilized with NULL character just by assigning them with {} as below.

char array[8] = {};

Otherwise, by Default, it will be initilized with some junk characters.


Array as an Argument to a function

A function can receive Array as an argument with any of the below forms:
  1. As a pointer to an Array like int func(int *array);
  2. As a sized Array like int func(int array[3]);
  3. As an unsized Array like int func( int array[]);
  4. As a reference to an Array like void func(int (&arr)[3]);

But always an array name that as a function argument is converted to a pointer to the start of array, at compile time itself, by the compiler. So any reference to that array inside the function is treated as a pointer reference.

For Example:
Code: Cpp
int array1[50];

void fun(int arr2[])
{
  arr2[1] = 3;
  *arr2 = 3;
  arr2 = array1;
 
}


int main()
{
int arr2[3];

arr2[1] = 3;
*arr2 = 3;

//we cannot do the below
//arr2 = array1;

return(0);
}

If we see the above code snippets, array when it is passed as an argument to a function, can be assigned to another array as it is treated always as a pointer. Whereas we cannot do the same in main function, it would give compilation error, as we are trying to change the array name itself, which cannot be done. Also
Code: Cpp
void func(int [] a)
{
 return sizeof (a); // returns the size of the pointer p not the size of the array !!
}

int main()
{
 int num[2];
 cout << sizeof (num); //Returns the size of the array num!!
 func(num);
}

The above code snippet confirms that array which is passed to as an argument to function, is treated as a pointer inside the function as the sizeof that argument results with sizeof a pointer and not sizeof the Array.

Also, by giving/sending a pointer to any intermediate element of an Array to a function, we can just pass the slice/last part of the array from that intermediate point.

For Example:
The code

Code: Cpp
#include<iostream.h>

void func(int *arr)
{
  int i;
 
  for (i=0; i<2; ++i)
  {
    cout<<arr[i]<<endl;
  }
}

int main()
{
  int array[4] = {100,200,300,400};
  cout<<"Sending slice of an array...\n";

  int * ptr = &array[2];
  func(ptr);
 
  return(0);
}
Output:

./a.out
Sending slice of an array...
300
400

Here ptr which is pointing to 2nd index of the array[4] is sent to func and so only 2nd and 3rd indices has been printed on accessing the array through ptr in function func.


Operations Done on Arrays
      Storing/Collecting elements of same data type.
      Iterating through all the elements in an Array
      Searching an element in an Array
      Comparision of two Arrays
      Assignment operation





Multi-Dimensional Arrays

Multi-dimensional arrays are nothing but Array of Arrays.

Characteristics

All the characteristics that are mentioned for 1-Dimensional array hold good for multi-dimensional arrays too. Apart from that
      Declaration of a multi-dimension array as a argument to a function, must include explicit size declarations in all of the subscript positions except for the first, which is an option.

Memory Mapping

In C/C++, memory mapping for multi-dimensional arrays, is done using Row Major ordering. It means, memory is allocated for successive elements by incrementing the rightmost index until it reaches the end of the current Row.

2-Dimensional Arrays

A 2-Dimensional Array is nothing but Array of 1-Dimensional Array and is represented with two subscripts as below:

data_typeOfArray arrayName [firstDimension] [secondDimension]

whereas firstDimension represents Rows and secondDimension as Columns.

For Example:
int array[2][3];

Can be said as 2 Arrays of 1-Dimensional Array of size 3;

2-Dimensional array can be imagined as a 2-D table made of elements of same data type as in below picture:



Memory Mapping in 2-D Array

For Example if we take int array[2][3];

Here array will be considered as base address and successive address for the elements will be allocated at sizeOfElement*offset in Row Major Ordering. And here if we take the sizeOfElement as 1 then memory mapping for array[2][3] looks as below:

array[0][0] --------> 0
array[0][1] --------> 1
array[0][2] --------> 2

array[1][0] --------> 3
array[1][1] --------> 4
array[1][2] --------> 5

Where 0,1,2 etc at right hand side are offsets

Size of a 2-D Array

Here size of the Array can be calculated as:
firstDimension*secondDimension*sizeOfDataType

For example:
size of the int array[2][3] will be 2*3*4= 24 bytes

Address of an Element

Address of an Element at a given rowIndex and colIndex in an array[rowSize][colSize] can be calculated using the below formula:

Element_Address = Base_Address + (col_size*(rowIndex) + (colIndex)) * Element_Size

For Example:
If we take the above array[2][3] with assumption of baseAddress as 0 and element size as 1, then address of element at indices array[0][1] can be found as:

array[0][1] = 0 + (3*(0)+1)*1
= 0 + (0+1)*1
= 0 + 1
= 1


Initializing a 2-D Array

As like in 1-D Arrays, 2-D Arrays can be initialized as below:

int arry[2][3]={10,20,30,40,50,60}; or

int array[2][3] = {{10,20,30}, {40,50,60}}

And they are assigned with array indices as below:

array[0][0]=10;
array[0][1]=20;
array[0][2]=30;
array[1][0]=40;
array[1][1]=50;
array[1][2]=60;


Like in 1-D array, if some of the indices in an interger 2-D array are not given initilizers, then by default they will be initilized with 0. Also if we assign 2-D Array with {}, it would initialize all it's elements with 0 value.

2-D Array of characters

Like in 1-D Arrays, 2-D Arrays of strings can be initilized in two ways as below:

char array[3][4] = {
'd','o','g'
'c','a','t',
'r','a','t'
}


or

char array[3][4] = {"dog", "cat", "rat"};

As said above for integer arrays, if initilizers are not given for some elements in character arrays, they will be initilized with NULL characters.

Accessing elements in 2-D Arrays

In the above mentioned array i.e. int array[2][3], we can access the 1st Rowth 0th column element as array[1][0] i.e. 40

Dynamic Allocation of 2-D Arrays

Suppose we want an int array[row][col]. where size of row and col are unknown at compile time. Then we can allocate the array dynamically and access it's elements with below steps:
      The name array will be a pointer to a pointer to int.
      Initialliy allocate memory of size x for pointers to int i.e. array of pointers
      Then allocate memory of size y for each of these pointer
      Access each of the element of array as array[i][j], where i>=0 and <x and j>=0 and <y.
      Free the memory by deallocating for each of the pointers and then array of pointers itself.

For Example:
The code

Code: Cpp
#include<iostream.h>

int main()
{
 
int row, col;
 
int **array; //array name
 
int i, j;
 
  cout<<
"Enter the matrix size i.e. row and column"<<endl;
  cin>>row;
  cin>>col;

 
//allocate memory of size row to pointer to int
  array =
new int*[row];

 
//allocate memory of size col to each of the pointer to int
 
for(i=0; i<row; ++i)
  {
    array[i] =
new int[col];
  }

  cout<<endl;

  cout<<
"Please eneter the values array["<<row<<"]["<<col<<"] :\n";
 
 
for(i=0; i<row; ++i)
  {
   
for(j=0; j<col; ++j)
    {
      cin>>array[i][j];
    }
  }

  cout<<endl;

  cout<<
"Contents of array["<<row<<"]["<<col<<"] are :\n";

 
for(i=0; i<row; ++i)
  {
   
for(j=0; j<col; ++j)
    {
      cout<<array[i][j];
    }
    cout<<endl;
  }

  cout<<endl;

 
//now for each pointer, free its array of ints
 
for (i = 0; i < row; i++)
  {
   
delete [] array[i];
  }
 
 
//now free the array of pointers
 
delete [] array;
 
 
return(0);
}

Output:
------------
./a.out
Enter the matrix size i.e. row and column
2
3

Please eneter the values array[
2][3] :
1
2
3
4
5
6

Contents of array[
2][3] are :
123
456
2-Dimensional array as an Argument to a function

As said above, the size of the first dimension may be omitted, but the second dimension has to be mentioned in the argument.

For Example:
The code

Code: Cpp
#include<iostream.h>

double sum(double array[][3], int size)
{
 
double temp = 0.0;
 
 
for(int i = 0 ; i < size ; i++)
  {
   
for(int j = 0 ; j < 3 ; j++)       
    {
      temp += array[i][j];
    }
  }
 
return temp;
}

int main() {
 
double array[2][3] = {
                         {
1.02.03.0},
                         {
5.06.07.0}
                       };

 
cout << "Sum of all the elements in array[2][3] is: "<< sum(array, sizeof array/sizeof array[0])<< endl;
 
return 0;
}

Output:
----------
Sum of all the elements in array[
2][3] is: 24
Easy way of reading a 2-D Array

Imagine a 2-D array as shown in below example picture and then put the elements at the respective indices in the picture. This helps to read/recognise any element of the array at a given indcies.



3-Dimensional Arrays

Multi Dimensional Arrays are not limited to 2-D alone. They can be of as many indices as needed. But developer must be careful here, as the memory that consume increases with proportional to the dimension.

A 3-Dimensional Array can be said as Array of 2-Dimensional Arrays and is represented with three subscripts as below:

data_typeOfArray arrayName [firstDimension] [secondDimension] [thirdDimension]
whereas firstDiemnsion is also called as depthSize here.

For Example:

int arry[2][3][4]; can be called as
2 Arrays of 2-Dimensional Arrays of size 3X4 !!

Memory Mapping in 3-D Array

If we take int array[2][3][4];

And array will be considered as base address and successive address for the elements will be allocated at sizeOfElement*offset in Row Major Ordering as below:

array[0][0][0] --------> 0
array[0][0][1] --------> 1
array[0][0][2] --------> 2
array[0][0][3] --------> 3

array[0][1][0] --------> 4
.
.
.

array[0][2][0] --------> 8
.
.
.
array[1][0][0] --------> 12
.
.
.
array[1][1][0] --------> 16
.
.
.
array[1][2][0] --------> 20
array[1][2][1] --------> 21
array[1][2][2] --------> 22
array[1][2][3] --------> 23

Where 0,1,2 etc at right hand side are offsets

Size of a 3-D Array

Here size of the Array can be calculated as
firstDimension*secondDimension*thirdDimension*size OfDataType

For example the size of the below array will be:
int array[2][3][4]

2*3*4*4 = 96 bytes


Address of an Element

Address of an Element at a given depthIndex, rowIndex and colIndex in an array[depthSize][rowSize][colSize] can be calculated using the below formula:

Element Address = Base Address + ((depthIndex*colSize+colIndex) * rowSize + rowIndex) * Element_Size

If we take the above array[2][3][4] with assumption of baseAddress as 0 and element size as 1, then address of an element at indices array[1][2][3] can be found as:

array[1][2][3] = 0 + ((1*4+3)*3+2)*1
= 0 + ((4+3)*3+2)1
= 0 + ((7)*3+2)1
= 0 + 23


Easy way of Reading a 3-D Array

Elements in a 3-D array also can easily be read/recognised by imagining the picture of the Array as below:


7 comments:

  1. Good work dude , Keep it up

    ReplyDelete
    Replies
    1. Thank You.

      Please do post your suggestions also in case you feel any wrong and improvement that can be made.

      Regards,
      Saurabh Gupta
      saurabh.gupta@ccplusplus.com

      Delete
    2. Hi ,
      could you pls clarify my below query

      char array[7]= {'M', 'r', 'i', 'd', 'u', 'l', 'a'}; // size 7 is enough to hold the elements , whereas in string we need to have size 8 to hold the same

      char array[8]= "Mridula";

      Note : In both the cases,NULL is available at the end

      Delete
    3. Hi,

      when you declare your array of characters you need to add one extra null character at the end. As you have not added in this case:

      char array[7]= {'M', 'r', 'i', 'd', 'u', 'l', 'a'};

      Here when you will print the array you will get the junk values after the a, something like that,

      Mridula��������L

      So you need to increase the array size by 1 and adding a null character as when you are initializing the character array null character is not automatically added.

      char array[8]= {'M', 'r', 'i', 'd', 'u', 'l', 'a', '\0'};
      When you print aray here you will get this

      Mridula

      In other case when you are using string literals a null character is added automatically.
      Double quoted strings (") are literal constants whose type is in fact a null-terminated array of characters. So string literals enclosed between double quotes always have a null character ('\0') automatically appended at the end.

      Here when you will print your array you will get Mridula only.

      Delete
  2. you guys are gods amongst (wo)men

    ReplyDelete