Introduction to Algorithms &
Programming
Steve James
Lecture 10
Recap
• Python lists
– Store collection of values (of any type)
values = [27, 39, False, "Batman > Superman"]
• C++ equivalents:
– Arrays (fixed-size) and vectors (variable size)
– Must be same (homogeneous) type
– Both arrays and vectors are STL classes
Declaring Arrays
• Arrays occupy space in memory
• Specify type and number of elements required
by an array using:
array<type, arraySize> arrayName;
• e.g array<int, 9> d;
• Compiler reserves appropriate amount of
memory based on type and size of array
Comparison
• C++ array initialisation
array<int, 5> myArr = {1, 2, 3, 4, 5};
• Python list initialisation
myArr = [1, 2, 3, 4, 5]
Comparison
• C++ range-based for loop
array<int, 5> myArr = {1, 2, 3, 4, 5};
for (int val : myArr){
cout << val << endl;
}
• Python for loop
myArr = [1, 2, 3, 4, 5]
for val in myArr:
print(val)
Data Abstraction
ARRAYS & VECTORS (PART I)
C++11
#include <iostream>
#include <array>
#include <cstdlib>
using namespace std;
int main(){
array<int, 5> d = {1, 2, -1, 3, 5};
cout << "Items before modification: " << endl;
for (int item : d){
cout << item << " ";
}
//multiple elements of d by 3
for (int &itemRef : d){
itemRef *= 3;
}
cout << endl << "Items after modification: " << endl;
for (int item : d){
cout << item << " ";
}
cout << endl;
return 0;
}
/*
Items before modification:
1 2 -1 3 5
Items after modification:
3 6 -3 9 15
*/
Range-based for loop
• Use int reference because d contain int values and we
want to modify each element’s value
• Because itemRef is declared as a reference, any change
you make to itemRef changes the corresponding element
value in the array.
• The range-based for statement can be used in place of the
counter-controlled for statement whenever looping
through an array does not require access to the
element’s subscript.
• However, if a program must use subscripts for some reason
other than simply to loop through an array (e.g., to print
a subscript number next to each array element value),
you should use the counter-controlled for statement.
Summary: Iterating over arrays
for (size_t i = 0; i < arr.size(); ++i){
cout << i << ":\t" << arr[i] << endl;
}
for (int element : arr){
//modifying element will not affect the array
cout << element << endl;
}
for (int &element : arr){
//modifying element will affect the array
cout << element << endl;
}
Multidimensional arrays
• Array declaration:
– array<type, size> name;
• Type can be int, string, double,...
• But arrays are also types
• So we can have arrays of arrays
Multidimensional arrays
• Multidimensional arrays: those with 2 or more
dimensions
• 2D arrays can be used to represent
tables/matrices
– Data arranged in rows and columns
• We must specify two subscripts. By
convention:
– first is the row,
– second is the column
2D arrays
arr is a two-dimensional array
It contains three rows and four columns, so it’s called a 3-by-4 array
Column 0 Column 1 Column 2 Column 3
Row 0 arr[0][0] arr[0][1] arr[0][2] arr[0][3]
Row 1 arr[1][0] arr[1][1] arr[1][2] arr[1][3]
Row 2 arr[2][0] arr[2][1] arr[2][2] arr[2][3]
array name column subscript
row subscript
3 × 4 Matrix
array< TYPE , 3> matrix;
array< array<int, 4> , 3> matrix;
#include <array>
#include <iostream>
To process the elements of a two-dimensional array, we
using namespace std;
use a nested loop in which the outer loop iterates through
//remember const! the rows and the inner loop iterates through the columns
const size_t ROWS = 2;
const size_t COLS = 3; of a given row
//why pass by reference?
void printMatrix(const array<array<int, COLS>, ROWS> &matrix){
//for each row
for (size_t row = 0; row < matrix.size(); ++row){
//for each element in the current row
for (size_t col = 0; col < matrix[row].size(); ++col){
cout << matrix[row][col] << ' ';
}
cout << endl;
}
} Type of array is array<int, COLS>
int main(){
array<array<int, COLS>, ROWS> matrix = {
1, 2, 3,
4, 5, 6
};
cout << "Matrix: " <<endl; Initialising 2D arrays
printMatrix(matrix);
array<array<int, COLS>, ROWS> matrix2 = {
7, 8, 9
};
cout << endl << "Matrix2: " <<endl;
printMatrix(matrix2);
return 0;
}
/*Output:
Matrix:
1 2 3
4 5 6
Matrix2:
7 8 9
0 0 0 */
Side note: iteration
• Quicker way of iterating over 2D array with
range-based for loop
void printMatrix(const array<array<int, COLS>, ROWS> &matrix){
//for each row
for (size_t row = 0; row < matrix.size(); ++row){
//for each element in the current row
for (size_t col = 0; col < matrix[row].size(); ++col){
cout << matrix[row][col] << ' ';
}
cout << endl;
}
}
VS
void printMatrix(const array<array<int, COLS>, ROWS> &matrix){
for (auto row : matrix){ The C++11 auto
//auto infers that row is of type array<int, COLS>
for (auto element : row){ keyword tells the
cout << element << ' '; compiler to infer a
}
cout << endl; variable’s data type based
}
} on its initializer value.
Some array operations
• The STL provides functions that can be applied
to arrays (and vectors)
– #include <algorithm>
• A full list of functions is listed here
– http://www.cplusplus.com/reference/algorithm/
Sorting
• Sort data: place elements into ascending or
descending order
#include <iostream>
#include <array>
#include <string>
#include <algorithm>
using namespace std;
int main(){
array<string, 4> colours = {"blue", "black", "red", "green"};
for (string colour : colours){
cout << colour << ' ';
}
cout << endl;
sort(colours.begin(), colours.end()); begin() and end()
for (string colour : colours){
cout << colour << ' '; refer to the range to
}
return 0;
sort over.
}
/*
Output:
blue black red green
black blue green red
*/
Search (I)
• Determine whether an array contains a certain
key value
• Perform a binary_search for the key
– Pro: super efficient
– Con: array must be sorted first!
Binary Search Example
#include <iostream>
#include <array>
#include <string>
#include <algorithm>
using namespace std;
int main(){
array<string, 4> colours = {"blue", "black", "red", "green"};
sort(colours.begin(), colours.end()); //must be sorted
string key = "black";
bool found = binary_search(colours.begin(), colours.end(), key); //look for
black
if (found){
cout << "We found the key 'black'" << endl;
}
return 0;
}
Search (II)
• Determine the number of elements equal to
something
– Use count function
#include <iostream>
#include <array>
#include <algorithm>
using namespace std;
int main(){
array<int, 5> nums = {1, 2, 3, 100, 2};
//counting number of twos
int numOccurrences = count(nums.begin(), nums.end(), 2);
cout << 2 << " appeared " << numOccurrences << " times" << endl;
return 0;
}
/*
2 appeared 2 times
*/
Search (III)
• Determine the number of elements satisfying
some condition
– Use count_if function
#include <iostream>
#include <array>
#include <algorithm>
using namespace std;
bool isEven(int x){
return x %2 == 0;
}
int main(){
array<int, 5> nums = {1, 2, 3, 100, 2};
//counting number of even numbers
int numOccurrences = count_if(nums.begin(), nums.end(), isEven);
cout << numOccurrences << " numbers are even" << endl;
return 0;
}
/*
3 numbers are even
*/
Vectors
• Arrays are great, but…
– Need to know the size up front
• Enter the vector
– #include <vector>
• Like arrays, but support dynamic resizing
– All STL functions that work on arrays work on
vectors
• Question: Why would we even use arrays
then?
Creating vectors
• Compare arrays:
– array<type, size> name;
• With vectors:
– vector<type> name;
• Different options for declaring vectors
vector<int> v1 // vector of size 0
vector<int> v2(17); // 17 elements, each with value 0
vector<string> v3(17, "Bob"); // 17 elements, each with value Bob
vector<int> v4{17}; // 1 element of value 17
Some Vector Functions
Function Effect Usage
resize Changes the vector<int> vec {1, 2, 3};
number of vec.resize(5);
elements stored //now vec = {1,2,3,0,0}
vec.resize(1);
//now vec = {1}
push_back Adds an element vector<int> vec {1, 2, 3};
to the end vec.push_back(4);
//now vec = {1,2,3,4}
clear Removes all vector<int> vec {1, 2, 3};
elements from vec.clear();
the vector //now vec = {}
reserve Reserve memory vector<int> vec;
for the vector vec.reserve(100);
//now vec = {}, can add many ints
before background resizing needed
Vector Operations
• Everything you can do with arrays, can do with
vectors:
– size() function
– Iteration
– Multidimensional vectors
– Accessing with [] operator
Low-level C++
MEMORY ALLOCATION & LAYOUT
Aims
• Understand
– how C++ organises memory
– when to use which type
– how things like vector work behind the scenes
• Extremely important for low-level languages
(like C)
• Warning: use modern C++11 constructs to
avoid all this unpleasantness in practice
Then why?
• What is the plural of octopus?
• Octopus is not Latin, but from Greek oktopous
• Therefore, its plural is not octopi, but
octopodes
Memory Layout
• Local variables reside on the stack
– Automatic allocation Code
• Global variables are stored in static
data Static data
Heap/Free store
• Code section stores the executable
code
• Heap is a bunch of extra memory Stack
assigned to us
– Dynamic allocation
Stack
• The stack is used to store
– the return addresses at function calls
– arguments passed to the functions
– local variables for functions
– CPU state
• Every time a function is called, a new stack
frame is placed on the stack
• When the function ends, the stack frame is
removed
Stack Frame
Optional
Last auto variable
…
First auto variable
Return address
Optional
First parameter
…
Last parameter
Optional
Return space
Stack Frames
#include <iostream>
using namespace std;
y: 4 bytes
Stack frame for square()
int square(int x){
int y = x * x;
cout << y << endl; 0x643c
return y;
} x: 4 bytesz: 4 bytes
Stack frame for main()
x: 4 bytes
int main(){ 4 bytes
int x = 2; 0x23242f
int z = square(x);
return 0;
}
4 bytes
Stack Issues
• Compiler automatically manages stack for us
• Must know how much memory to allocate
beforehand (sound familiar?)
• Stack size is small
– Cuts down on overhead
– But may run out of memory (try create an 100m
element arrray!)
• This is where the heap comes in
• But first…
Low-level C++
POINTERS
Note
• What we’re about to look at are called raw
pointers
• Where possible, avoid these in your code
• Use smart pointers (C++11) instead
Pointer
• A pointer is a variable that holds the memory
address of another variable
• So variable name refers to a value, while a
pointer indirectly refers to a value
– Indirection: referencing a value through a pointer
y x
int x = 7;
int *y = &x; 7
References vs Pointers
• Pointers can be reassigned; references cannot,
and must be initialised
• Can have pointers to pointers; cannot have
references to references
• Pointers can have a “null” value; references
cannot
• Pointers can be used for iteration
• References are safer and cleaner than pointers
– Prefer references where possible
Declaring Pointers
• int *ptr;
– the variable ptr is declared to be a pointer to an int
value
– any variable declared as a pointer must be preceded
by an asterisk ( * )
• When * appears in a declaration, it is not an
operator; rather, it indicates that the variable is a
pointer
• Pointers can point to objects of any type
• Question: How many bytes does a pointer take
up?
Declaring Pointers
• double *ptr; • A pointer to a double
• int **ptr; • A pointer to an
integer pointer
• const int * ptr;
• int * const ptr;
• const int * const ptr;
READ FROM RIGHT TO LEFT
Initialising Pointers
• Pointers should be given the memory address of
the variable they refer to
• Or, they may be set to “point to nothing”
– This is known as a “null pointer”
• In C++11, use the nullptr keyword:
– int *ptr = nullptr;
• Prior to C++11, 0 or NULL was used instead
– int *ptr = 0;
– int *ptr = NULL;
Pointer Operators
• The address operator (&) gets the address of
its operand
int x = 10; //declare variable x
int *xPtr = nullptr; //declare null pointer xPtr
//... a bit later in the code
xPtr = &x; //make xPtr point to x
x xPtr
10 0xbfb08e58
0xbfb08e58 0xbfb08e5c
Pointer Operators
• The operand of the address operator must be
an lvalue
– the address operator cannot be applied to
constants or to expressions that result in
temporary values (like the results of calculations).
int *xPtr = &(12 * 2); //Are you MAD?! No way, Jose!
Pointer Operators
• The indirection/dereferencing operator (*)
operator returns an lvalue representing the
object to which its pointer operand points.
– This is operation is called dereferencing a pointer.
int x = 10;
int *xPtr = &x;
/* Output
cout << "Address of x: " << &x << endl;
Address of x: 0x7fffedda4f04
cout << "Value of xPtr: " << xPtr << endl;
cout << "Value of x: " << x << endl; Value of xPtr: 0x7fffedda4f04
cout << "Value of *xPtr: " << *xPtr << endl; Value of x: 10
x = 0; //change x's value Value of *xPtr: 10
cout << "Value of *xPtr: " << *xPtr << endl; Value of *xPtr: 0
*xPtr = 42; //change x through the pointer Value of x: 42
cout << "Value of x: " << x << endl; */
Passing Pointers
• Recall: pass-by-reference and pass-by-value
• We can pass a pointer (by value)
• But because it points to an object, we can
modify the object in our function
• Just like pass-by-reference!
– Avoids overhead of passing large objects
#include <iostream>
using namespace std;
//by value
int cubeByVal(int x){
int t = x * x * x;
return t;
}
//by reference
void cubeByRef(int &x){
x = x * x * x;
}
//by pointer
void cubeByPtr(int *x){
*x = (*x) * (*x) * (*x); Dereferencing
}
int main(){
int number = 2;
cubeByVal(number);
cout << "After pass-by-value: " << number << endl;
cubeByRef(number);
cout << "After pass-by-reference: " << number << endl;
cubeByPtr(&number);
cout << "After pass-by-pointer-value: " << number << endl;
Address operator
}
/**
After pass-by-value: 2
After pass-by-reference: 8
After pass-by-pointer-value: 512
**/
