Foundations of programming

Lecture Three - Pointers and arrays

WorkPlan

  1. Introduction, types of programming languages, pseudocode
  2. Variables, data types
  3. Pointers and arrays
  4. Simple instructions and tricks
  5. Functions and Procedures
  6. Input / Output
  7. Error Types /Debug
  8. Data Structures
  9. Modern C++
  10. Python
  11. Python II
  12. Python III
  13. Object Oriented / Functional programming
  14. Software development in XXI century
  15. Final exam / Test

Memory once more

For a C++ program, the memory of a computer is like a succession of memory cells, each one byte in size, and each with a unique address.

Data representations larger than one byte occupy memory cells that have consecutive addresses.

Operating system decides the particular memory locations on run time (execution).

image

Pointers

Pointer is a variable type that stores a memory address.

Pointer holds the memory address as its value and has an ability to “point” (hence pointer) to certain value within a memory.

In C/C++ pointers are denoted with the symbol '*' (an asterisk).

Pros and cons

Pros:

Accessing variables directly by pointers rather than through their memory location results in increased efficiency and flexibility of written code.
Allocating memory in dynamic manner.
Passing variables by reference (if x=3; and y=x and y=5 will it change the value of x?)

Cons:

In C++, pointers are allowed to take any address value, no matter whether there actually is something at that address or not.
False manipulation with a memory can result in memory leaks.

Reading the memory address

To retrieve a variable's memory address, we need to use address-of operator &.

#include <iostream>
int main()
{
  using namespace std;

  unsigned short int myInt = 99;

  cout << myInt << endl;
            // Use address-of operator & to print out 
            // a memory address of myInt
  cout << &myInt << endl;

return 0;
}

Output:

99
0xbff26312

Declaration of a pointer

Declaring a pointer in C++ require an asterisk symbol "*" to be add and located after variable type and before a variable name.

#include <iostream>

int main()
{
  using namespace std;

  unsigned short int * pPointer = 0;

  unsigned short int twoInt = 35698;

  unsigned short int oneInt = 77;

            // Use address-of operator & to assign a memory address of twoInt to a pointer

  pPointer = &twoInt;

            // Pointer pPointer now holds a memory address of twoInt

  cout << "pPointer's memory address:\t\t" << &pPointer << endl;
  cout << "Integer's oneInt memory address:\t" << &oneInt << "\tInteger value:\t" << oneInt << endl;
  cout << "Integer's twoInt memory address:\t" << &twoInt << "\tInteger value:\t" << twoInt << endl;

  return 0;
}

Output:

pPointer's memory address:              0xbff43314
Integer's oneInt memory address:        0xbff43318      Integer value:  77
Integer's twoInt memory address:        0xbff4331a      Integer value:  35698

Declaration of a pointer

One rule has to be followed when assigning memory address to a pointer: pointer type has to match with variable type it will point to. One exception is a pointer to void, which can handle different types of variables it will point to.

image

Memory representation

image

Pointer (as a variable) pPointer starts at memory address 0xbff43314 and takes 4 bytes.

Pointer pPointer holds as a value a memory address of a short int twoInt ( 2 bytes ) which is 0xbff4331a.

Dereference

Process accessing a variable's value by a pointer is called indirection.

Value of variable can be indirectly accessed by dereferencing a pointer with dereference operator “ * “ which needs to be placed before a pointer variable name:

#include <iostream>

int main()

{
  using namespace std;

  unsigned short int myInt = 99;

  unsigned short int * pMark = 0;

  cout << myInt << endl;

  pMark = &myInt;

  cout << *pMark << endl;

return 0;
}

Output:

99
99

The dereference operator can be read as "value pointed to by".

Declaration

When pointers are initialized, what is initialized is the address they point to (i.e., myPointer), never the value being pointed (i.e., *myPointer).

int myVariable;
int * myPointer = &myVariable;

is the same as

int myvar;
int * myptr;
myptr = &myvar;

Not the same as:

Wrong

int myvar;
int * myptr;
*myptr = &myvar;

Output:

exampleCPP.cpp: In function ‘int main()’:
exampleCPP.cpp:12:12: error: invalid conversion from ‘int*’ to ‘int’ [-fpermissive]
    *myptr = &myvar;

Dereference vs declaration

Once dereferenced, the type needs to be known.

A pointer has different properties when it points to a char than when it points to an int or a float.

Declaring two pointers:

int *p1, *p2;   

Declaring a pointer and an int:

int *p1, p2;   

Manipulate variable through the dereference

#include <iostream>

int main()

{
  using namespace std;

  unsigned short int myInt = 99;

  unsigned short int * pMark = 0;

  cout << myInt << endl;

  pMark = &myInt;
            // Dereference a pMark pointer with dereference operator * and set new value
  *pMark = 11;

  cout << "*pMark:\t" << *pMark << "\nmyInt:\t" << myInt << endl;

return 0;
}

Output:

99
*pMark: 11
myInt:  11            

Note “ * “ is not a multiplication, by the context of your C/C++ code your compiler will differentiate if your intention is to use multiplication or dereference operator.

Test

image

Test

#include <iostream>
using namespace std;

int main ()
{
  int firstvalue = 5, secondvalue = 15;
  int * p1, * p2;

  p1 = &firstvalue;  // p1 = address of firstvalue
  p2 = &secondvalue; // p2 = address of secondvalue
  *p1 = 10;          // value pointed to by p1 = 10
  *p2 = *p1;         // value pointed to by p2 = value pointed to by p1
  p1 = p2;           // p1 = p2 (value of pointer is copied)
  *p1 = 20;          // value pointed to by p1 = 20

  cout << "firstvalue is " << firstvalue << '\n';
  cout << "secondvalue is " << secondvalue << '\n';
  return 0;
}

What are the final values of firstvalue and secondvalue ??

Output:

Null pointer (C++11)

There is a special value that pointer can take that says it points to nowhere, it is called null pointer value.

This value can be expressed in C++ in two ways: either with an integer value of zero, or with the nullptr keyword:

int * p = 0;
int * q = nullptr;

It is always a good practice to assign a NULL value to a pointer variable in case you do not have an exact address to be assigned.

int *x;
*x = 100;

No compilation error, but likely a segmentation fault.

Arithmetic with pointers

Adding one to a pointer, the pointer is made to point to the following element of the same type, and, therefore, the size in bytes of the type it points to is added to the pointer.

char *mychar;
short *myshort;
long *mylong;

++mychar;
++myshort;
++mylong;

are increased by 1,2 and four bytes respectively.

image

Watch out for operators combinations

*p++   // same as *(p++): increment pointer, and dereference unincremented address
*++p   // same as *(++p): increment pointer, and dereference incremented address
++*p   // same as ++(*p): dereference pointer, and increment the value it points to
(*p)++ // dereference pointer, and post-increment the value it points to     

More on the topic next week!

Const pointers

It is possible to declare pointers that can access the pointed value to read it, but not to modify it.

For this you use qualifier const.

const int * p = &y;
x = *p;          // ok: reading p
*p = x;          // error: modifying p, which is const-qualified 

Pointers to pointers

C++ allows the use of pointers that point to pointers.

image

The syntax simply requires an asterisk (*) for each level of indirection in the declaration of the pointer:

char a ;
char * b;
char ** c;
a = 'z';
b = &a;
c = &b;

Dereferencing nested pointers:

var = 3000;

/* take the address of var */
ptr = &var;

/* take the address of ptr using address of operator & */
pptr = &ptr;

/* take the value using pptr */
printf("Value of var = %d\n", var );
printf("Value available at *ptr = %d\n", *ptr );
printf("Value available at **pptr = %d\n", **pptr);    

void pointers

The void type of pointer is a special type of pointer. Void pointers are pointers that point to a value that has no type

* can point to any data type, from an integer value or a float to a string of characters.
* cannot be directly dereference

Example:

void *ptr;    // ptr is declared as Void pointer

char cnum;
int inum;
float fnum;

ptr = &cnum;  // ptr has address of character data
ptr = &inum;  // ptr has address of integer data
ptr = &fnum;  // ptr has address of float data 

Casting void pointers

Proper use of void pointer for getting the value the pointer points to.

#include<stdio.h>
int main()
{
    int a = 10;
    void *ptr = &a;
    printf("%d", *(int *)ptr);
    return 0;
}

Arrays

image

Collections

What if we want to store a list of elements?

Array is a collection of variables belongings to the same data type placed in contiguous memory locations.

That means that, for example, five values of type int can be declared as an array without having to declare 5 different variables.

Arrays

In an array variable declaration, we use square brackets ([]) to tell the compiler both that this is an array variable (instead of a normal variable), as well as how many variables to allocate (called the array length).

Arrays can be made from any data type.

int testScore[30];

A fixed array is an array where the length is known at compile time

The first element in our array is testScore[0]. The second is testScore[1] etc.

Initializer list

We can initialize entire arrays via use of an initializer list. The following example is equivalent to the one above:

int prime[5] = { 2, 3, 5, 7, 11 }; 

If there are more initializers in the list than the array can hold, the compiler will generate an error.

However, if there are less initializers in the list than the array can hold, the remaining elements are initialized to 0.

int array[5] = { };

Initialize whole array with zeroes.

Arrays

In C++ , an array name is a constant pointer to its first element.

#include <>

int main()
{
  using namespace std;

  int Marks [10]= {1,2,3,4,5,6,7,8,9,0};
                        // Print out the memory address of an array name 
  cout << Marks << endl;
                        // Print out the memory address of a first element of an array
  cout << &Marks[0] << endl;
                        // Print out value of the first element by dereferencing a array name
  cout << *Marks << endl;

  return 0;
}

Output:

0xbf83d3fc
0xbf83d3fc
1

Access array elements

#include <iostream>

int main()
{
  using namespace std;

  int Marks [10]= {1,2,3,4,5,6,7,8,9,0};

                            // Access a 6th element by dereferencing array name
  cout << *(Marks + 5) << endl;
                            // Access a 6th element of an array
  cout << Marks[5] << endl;

  return 0;
}

Output:

6
6  

Access array elements

Formula to calculate address:

Address of element of a[i] = base address of array a[] +  data_type_size * (i - starting index )

Access array elements

#include <stdio.h>

int main () {

 /* an array with 5 elements */
 double balance[5] = {1000.0, 2.0, 3.4, 17.0, 50.0};
 double *p;
 int i;

 p = balance;

 /* output each array element's value */
 printf( "Array values using pointer\n");

 for ( i = 0; i < 5; i++ ) {
    printf("*(p + %d) : %f\n",  i, *(p + i) );
 }

 printf( "Array values using balance as address\n");

 for ( i = 0; i < 5; i++ ) {
    printf("*(balance + %d) : %f\n",  i, *(balance + i) );
 }

 return 0;
}

Output:

Array values using pointer
*(p + 0) : 1000.000000
*(p + 1) : 2.000000
*(p + 2) : 3.400000
*(p + 3) : 17.000000
*(p + 4) : 50.000000
Array values using balance as address
*(balance + 0) : 1000.000000
*(balance + 1) : 2.000000
*(balance + 2) : 3.400000
*(balance + 3) : 17.000000
*(balance + 4) : 50.000000

Working with array

When you pass an array as an argument to a function (like printf), you really pass a pointer to the array's first element.

array == &array == &array[0]

In English, these expressions read “array”, “pointer to array”, and “pointer to the first element of array” (the subscript operator, [], has higher precedence than the address-of operator).

In C, all three expressions mean the same thing.

sizeof()

The sizeof operator can be used on arrays, and it will return the total size of the array (array length multiplied by element size)

void printSize(int array[])
{
    std::cout << sizeof(array) << '\n'; // prints the size of a pointer, not the size of the array!
}

int main()
{
    int array[] = { 1, 1, 2, 3, 5, 8, 13, 21 };

    std::cout << sizeof(array) << '\n'; // will print the size of the array

    std::cout << "The array has: " << sizeof(array) / sizeof(array[0]) << "elements\n";
    printSize(array);

    return 0;
}

Output:

32
8
4

If int takes 4 bytes in your compiler. Look out at the behavior when you pass the array to a function.

Multidimensional arrays

Multidimensional arrays can be described as "arrays of arrays".

Example of two dimensional arrays:

int matrix[3][5];

The array has 3 rows and five columns. and is equivalent to

int matrix[15];

Analogously you define higher dimensional arrays.

Test

int array[] = { 45, 67, 89 }; 
int *array_ptr = &array[1]; 
printf("%i\n", array_ptr[1]);

What will happen? (%i - means that print is expecting decimal type - in other words a number).

References

A reference is a type of C++ variable that acts as an alias to another object or value.

You declare the reference with an ampersand &.

int value = 5; // normal integer
int &ref = value; // reference to variable value

References must be initialized and can not be reassigned.

int &invalidRef; // invalid, needs to reference something    

References

References generally act identically to the values they're referencing. In this sense, a reference acts as an alias for the object being referenced

#include <iostream>

int main()
{
    int value = 5; // normal integer
    int &ref = value; // reference to variable value

    value = 6; // value is now 6
    ref = 7; // value is now 7

    std::cout << value; 

    ++ref;

    std::cout << value;

    return 0;
}

Output:

7
8

The address of a variable and a reference to this variable are the same.

Strings

There is no string type in C.

Strings are actually one-dimensional array of characters terminated by a null character '0'.

char greeting[] = "Hello";

The C compiler automatically places the '0' at the end of the string when it initializes the array.

String can also be initialized using pointers as:

char *c = "abcd";

String

image

strcpy, strcat, strlen

Library string.h contains functions which are useful when dealing with arrays of characters:

#include <stdio.h>
#include <string.h>

int main () {

   char str1[12] = "Hello";
   char str2[12] = "World";
   char str3[12];
   int  len ;

   /* copy str1 into str3 */
   strcpy(str3, str1);
   printf("strcpy( str3, str1) :  %s\n", str3 );

   /* concatenates str1 and str2 */
   strcat( str1, str2);
   printf("strcat( str1, str2):   %s\n", str1 );

   /* total lenghth of str1 after concatenation */
   len = strlen(str1);
   printf("strlen(str1) :  %d\n", len );

   return 0;
}

Output :

strcpy( str3, str1) :  Hello
strcat( str1, str2):   HelloWorld
strlen(str1) :  10  

Array of chars in C

As a programmer you must distinguish between the following three things:

* An "ordinary" array of characters, which is just like any other array and has no special properties that other arrays do not have.
* A C-string, which consists of an array of characters terminated by the null character '0'. For example if you have a C-string storing "Hello" in a character array of size 10, then the letters of the word "Hello" will be in positions with indices 0 to 4, there will be a null character at index 5, and the locations with indices 6 to 9 will contain who-knows-what.
* A C++ string object available by including the <string> header file.

Look out!

image

Nowadays compilation error!

Array of Pointers

We can also have array of pointers. Pointers are very helpful in handling character array with rows of varying length.

image

Dynamic Variables

It is memory-wise to not use the global variables but to dynamically create objects when necessary and dispose them when they are useless.

For this in C++C we have operator new, delete and malloc, free.

In simple terms, Dynamic memory allocation allows you to manually handle memory space for your program.

The memory management is wise only if you actually free the memory at some point!

Allocating memory

new operator is to be used when allocating a memory is needed. Return value of a new operator is a pointer. Therefore, it should be assigned to only a pointer.

#include <iostream>
int main()
{
    using namespace std;

    unsigned short  * pPointer;
    // allocate a memory with a new operator on the free store 

    pPointer = new unsigned short;

    *pPointer = 31;

    cout << *pPointer << endl;

return 0;
}

Output:

31

The free store memory allocated during the program runtime was released only when the actual program ended.

De-allocating a memory

To return an allocated memory a delete operator is to be used:

#include <iostream>
int main()
{
    using namespace std;

    unsigned short * pPointer;

    pPointer = new unsigned short;

    *pPointer = 31;
    // de-allocating memory back to the free store
    delete pPointer;

    cout << *pPointer << endl;

    return 0;
}

Output:

0

After delete the declaration of the pointer is still valid, so pPointer can be reassigned. The remove operator just removed associated memory address with the pointer.

malloc()

The function malloc() reserves a block of memory of specified size and return a pointer of type void which can be cast into pointer of any form.

int num, i, *ptr;

printf("Enter number of elements: ");
scanf("%d", &num);

ptr = (int*) malloc(num * sizeof(int));  //memory allocated using malloc
if(ptr == NULL)                     
{
    printf("Error! memory not allocated.");
    exit(0);
};

free()

Dynamically allocated memory created with either calloc() or malloc() doesn't get freed on its own. You must explicitly use free() to release the space.

free(ptr);    

Arrays of pointers

Pointers to pointers have a few uses. The most common use is to dynamically allocate an array of pointers:

int **array = new int*[10]; 

Allocate an array of 10 int pointers.

Declaring multidimensional array (not necessary rectangular):

int **array = new int*[10]; // allocate an array of 10 int popninters — these are our rows
for (int count = 0; count < 10; ++count)
    array[count] = new int[count+1]; // these are our columns

In C++11 or newer, this is a good place to use automatic type deduction (if you the size of an array is a previously known constant):

auto array = new int[10][5];

Pointers in Python

In python objects can be either mutable, or immutable. An immutable object is copied when it is modified. A mutable object is altered in-place.

You can say that variables are bound to memory objects rather than memory types.

i=5
# The label i now references 5
j=i
# The label j now references what i references
j=3
# The label j now references 3
print i
# i still references 5

Immutable types in Python : int, float, decimal, complex, bool, string, tuple

The End

image

References

http://www.cplusplus.com/doc/tutorial/pointers/

https://linuxconfig.org/c-understanding-pointers

https://docs.python.org/2/reference/datamodel.html

http://www.learncpp.com/cpp-tutorial/6-8-pointers-and-arrays/

http://boredzo.org/pointers/

http://www.learncpp.com/cpp-tutorial/611-references/

http://www.cplusplus.com/reference/array/array/

http://www.circuitstoday.com/void-pointers-in-c

https://www.tutorialspoint.com/cprogramming/c_strings.htm

https://www.cprogramming.com/tutorial/c/lesson9.html

http://cs.stmarys.ca/~porter/csc/ref/c_cpp_strings.html