C++ Theory

Complete Study Notes

COMS1018A — Introduction to Algorithms & Programming
1. What kind of language is C++?

Property C++ Why it matters

Type system Statically typed Types are fixed at compile time
— int x can never become a
string
Execution Compiled Source code → machine code
before running — errors caught
early
Paradigm Multi-paradigm Supports procedural, object-
oriented, and generic
programming

Compare: Python is interpreted and dynamically typed — the opposite of C++ in both ways.

2. How a C++ program is structured

Every C++ program follows this skeleton. Understanding each line is essential.

#include <iostream> // 1. Preprocessor directive — pastes in iostream

using namespace std; // 2. Lets us write cout instead of std::cout
//
int main() { // 3. Entry point — execution starts here
cout << "Hello!"; // 4. Output to screen
return 0; // 5. Return 0 = success to the OS
}

Line-by-line explanation

Line What it does

#include <iostream> Tells the preprocessor to paste the iostream
header file here. Without this, cout and cin don't
exist.
using namespace std; Removes the need to write std:: in front of
everything. Convenience shortcut.
int main() The function the OS calls to start your program.
Must return int.
cout << "Hello!" Sends text to standard output (the terminal). << is
 Line What it does
the insertion operator.
return 0; Sends exit code 0 to the OS. 0 = success.
Anything else = error.

The 5 phases of compilation

When you click 'compile and run', your program goes through 5 distinct phases:

Phase What happens Exam answer

1. Preprocess Handles #include, #define. Text substitution
Pastes file contents in and does
text substitution.
2. Compile Translates C++ source to object Type checking
files (.o). Type checking and
syntax errors caught here.
3. Link Combines your object files with Combining files
library files into one executable.
4. Load OS copies the executable into Allocates RAM ← exam
RAM so the CPU can run it. favourite
5. Execute CPU runs the machine code Program runs
instructions one by one.

Exam trap: "Which phase allocates memory in RAM?" → Load. Not Compile, not Execute.

3. Declarations outside int main() — and why

C++ code is organised into scopes. Where you declare something determines where it can be
used. There are three common places things are declared outside main().

3.1 Global variables

#include <iostream>
using namespace std;

int globalCount = 0; // declared OUTSIDE main — global scope

void increment() {
 globalCount++; // accessible here — same global scope
}

int main() {
increment();
cout << globalCount; // prints 1 — accessible here too
return 0;
}

Why declare globally? A global variable is visible to ALL functions in the file. You use it when
multiple functions need to share the same piece of data without passing it around.

Warning: global variables are generally discouraged in large programs because any function can
modify them, making bugs hard to trace. In small programs and exam code they are acceptable.

3.2 Function prototypes (forward declarations)

C++ reads files top to bottom. If you call a function before defining it, the compiler doesn't know it
exists yet and throws an error. A prototype solves this:

#include <iostream>
using namespace std;

// PROTOTYPE — declared outside main, above it

// Tells the compiler: 'this function exists, trust me'
double average(int a, int b);

int main() {
cout << average(4, 9); // works — compiler already knows average exists
return 0;
}

// DEFINITION — can appear after main

double average(int a, int b) {
return (a + b) / 2.0;
}

A prototype consists of exactly three things:

Part Example Note

Return type double What the function gives back.
void if nothing.
Function name average How you call it.
Parameter list (int a, int b) Names are optional in
prototypes — types are enough.
 Exam trap: The prototype does NOT include the function body or a memory address. Those are not
part of a prototype.

3.3 Function definitions outside main

Functions are always defined outside main(). This is because main() is itself a function — you can't
define a function inside another function in C++. Each function lives at the global scope level.

// All of these live OUTSIDE main — at global scope:

void printHello() { // function definition

cout << "Hello";
}

int square(int x) { // another function definition

return x * x;
}

int main() { // main is also a function

printHello(); // calling the functions from within main
cout << square(5);
return 0;
}

3.4 #include and using namespace std

These preprocessor directives also live outside main and affect the entire file:

#include <iostream> // must be outside — preprocessor runs before compilation

#include <vector> // each #include pastes in a header file
#include <algorithm>

using namespace std; // also outside — applies to all code below it

Think of the area above main() as the 'setup zone' — it's where you bring in tools (#include), set up
shortcuts (using namespace), declare types and variables that everyone needs (globals), and register
your functions (prototypes).

4. Variables — declaration, initialisation, assignment

 int x; // DECLARATION only — variable exists, value is garbage
int x = 5; // DECLARATION + INITIALISATION — first value given at creation
x = 10; // ASSIGNMENT — changing the value after declaration

Exam trap: "int x;" is a declaration. Many students say 'allocation' — that is wrong.

Types and their literals

Type Stores Literal example Size

int Whole numbers 42, -7, 0 4 bytes
double Decimal (high 3.14, 2.0 8 bytes
precision)
float Decimal (lower 3.14f 4 bytes
precision)
char Single character 'A', '9', ' ' 1 byte
bool True or false true, false 1 byte
string Text (STL type) "hello", "Bob" varies

Single quotes '9' → char. Double quotes "9" → string. This is a very common exam trap!

const

const int MAX = 100; // value can never change — compiler enforces this
const double PI = 3.14159;

MAX = 200; // COMPILE ERROR — cannot reassign a const variable

5. Operators

Operator Meaning Example Result

% Modulo — remainder 7%3 1
after division
= Assignment — store a x=5 x is now 5
value
== Equality check — 5 == 5 true
returns bool
 Operator Meaning Example Result
!= Not equal 5 != 3 true
&& Logical AND — both true && false false
must be true
|| Logical OR — at least true || false true
one true
! Logical NOT — flips !true false
bool
++ Increment by 1 x++ or ++x x becomes x+1
-- Decrement by 1 x-- or --x x becomes x-1
<< Stream insertion cout << x prints x
(output)
>> Stream extraction cin >> x reads into x
(input)

cin << x is a compile error! Input uses >>, output uses <<. The arrow points toward the destination: cin
>> x means 'put data INTO x'.

Integer division trap

int a = 7, b = 2;
a / b // == 3 (decimal part is DROPPED — not rounded!)
(double)a / b // == 3.5 (cast a to double first)
a / 2.0 // == 3.5 (2.0 is a double literal — forces float division)
(a + b) / 2 // == 4 (integer division!)
(a + b) / 2.0 // == 4.5 (correct for median calculation)

6. Functions — complete guide

A function is a named, reusable block of code. Functions prevent repetition, make programs easier
to test, and break big problems into smaller ones.

// 1. PROTOTYPE — tells compiler the function exists (written above main)

double average(int a, int b);

// 2. CALL — using the function from within main or another function

int main() {
double result = average(4, 9); // result == 6.5
return 0;
 }

// 3. DEFINITION — the actual implementation (can appear after main)

double average(int a, int b) {
return (a + b) / 2.0;
}

Pass by value vs pass by reference

void byValue(int x) { // x is a COPY — original variable is untouched

x = 99;
}

void byRef(int& x) { // x is an ALIAS — directly modifies the original

x = 99;
}

int main() {
int a = 5;
byValue(a); // a is still 5
byRef(a); // a is now 99
}

Technique Syntax Copies? Can modify When to use

original?
By value int x Yes No When you just
need the data
By reference int& x No Yes When you need to
modify the original
Const const int& x No No Read-only access
reference to large objects

void functions — no return value

void greet(string name) { // void means: returns nothing

cout << "Hello " << name;
// no return statement needed
}

The main() function

int main() {
 // Everything starts here.
// The OS calls main() when your program runs.
// All local variables declared here are destroyed when main() ends.
return 0; // 0 = success. Non-zero = error code.
}

// main() can also accept command-line arguments:

int main(int argc, char* argv[]) {
// argc = number of arguments
// argv = array of argument strings
}

The return value of main() is read by the OS. Script files and CI/CD pipelines use this to detect
whether your program succeeded or failed.

7. Control flow

if / else if / else

if (x > 0) {
cout << "positive";
} else if (x == 0) {
cout << "zero";
} else {
cout << "negative";
}

for loop

for (int i = 0; i < 5; i++) {

// ^init ^condition ^update — runs after each iteration
cout << i; // prints: 0 1 2 3 4
}

while loop

int i = 0;
while (i < 5) {
cout << i;
i++;
}
Range-based for loop — 3 variants

vector<int> v = {1, 2, 3};

for (int x : v) // COPY — changes to x do NOT affect v

for (int& x : v) // REF — changes to x DO affect v
for (const int& x : v) // CONST REF — read-only, no copy overhead

After for (int x : v) { x = 0; } the vector is unchanged. x is a copy. This appears in almost every exam.

8. Vectors and arrays

C-style array (fixed size)

int arr[5] = {1, 2, 3, 4, 5}; // size must be known at compile time

arr[0]; // first element — 0-indexed
arr[4]; // last element
// NO size(), NO push_back() — raw array has no built-in methods

std::array (fixed size, STL)

#include <array>
array<int, 3> a = {10, 20, 30}; // type first, then size
[Link](); // 3
a[1]; // 20

// 2D array:
array<array<int, 3>, 2> mat; // 2 rows, 3 columns
// When ranging: outer auto gives array<int,3>, inner auto gives int

std::vector (dynamic — use this most of the time)

#include <vector>
vector<int> v; // empty — size 0
vector<int> v(5); // 5 zeros — PRE-FILLED! size is already 5
vector<int> v = {1,2,3}; // initialiser list — size 3
 v.push_back(4); // append to end
v.pop_back(); // remove last element
[Link](); // number of elements
v[2]; // access index 2 (no bounds check!)
[Link](2); // access index 2 — throws if out of bounds
[Link](); // iterator to first element
[Link](); // iterator past last element (used with algorithms)

Classic bug: vector<int> v(N) creates N zeros. push_back(x) then adds MORE elements on top — you
end up with 2N elements. Either declare vector<int> v; (empty) and push_back, OR use v[i] = x to fill
the pre-sized vector.

Useful algorithm functions

#include <algorithm>

sort([Link](), [Link]()); // sort ascending

sort([Link](), [Link](), greater<int>()); // sort descending
count([Link](), [Link](), 42); // count how many 42s
count_if([Link](), [Link](), pred); // count matching predicate
find([Link](), [Link](), 42); // iterator to first 42

9. Recursion

A recursive function is one that calls itself. Every recursive function must have two parts:
• A base case — a condition where the function returns without calling itself
• A recursive case — a call to itself that moves toward the base case

int factorial(int n) {
if (n == 0) return 1; // BASE CASE — stops the recursion
return n * factorial(n - 1); // RECURSIVE CASE — gets smaller each time
}

// Trace for factorial(3):

// factorial(3) → 3 * factorial(2)
// → 2 * factorial(1)
// → 1 * factorial(0)
// → returns 1 (base case)
// ← 1 * 1 = 1
// ← 2 * 1 = 2
// ← 3 * 2 = 6

Stack frames
Each function call pushes a stack frame onto the call stack. The frame stores local variables and a
return address. When the function returns, its frame is popped off.

Term Meaning
Stack frame Memory block created for each function call —
holds local vars and return address
Call stack The pile of all currently active stack frames
Stack overflow Call stack runs out of memory — caused by
infinite recursion
Infinite recursion Recursion with no base case — calls never stop

Without a base case → infinite recursion → stack overflow. The program crashes.

Counting stack frames = counting how many times the function is called until termination. Trace step
by step for the given input value.

10. The auto keyword

auto tells the compiler to deduce the type automatically from the right-hand side. You don't write the
type — the compiler figures it out at compile time (so it's still statically typed).

auto x = 5; // compiler deduces: int

auto y = 3.14; // compiler deduces: double
auto s = "hello"; // compiler deduces: const char*

// Most useful in range-for loops with complex types:

vector<int> v = {1,2,3};
for (auto x : v) // x is int (copy)
for (auto& x : v) // x is int& (reference)

array<array<int,3>,2> mat;
for (auto row : mat) // row is array<int,3>
for (auto el : row) // el is int

11. #include headers — what each provides

Header What you get

#include <iostream> cin, cout, cerr, endl
 Header What you get
#include <vector> vector<T>
#include <array> array<T, N>
#include <string> string type and string operations
#include <algorithm> sort, count, find, count_if, min, max
#include <cmath> sqrt, pow, abs, floor, ceil, round
#include <numeric> accumulate, iota

Forgetting a header is a compile error. If you use vector without #include <vector> the program won't
compile — even if the rest of the code is perfect.

The correct answer is:

The << operator is known as the [insertion] operator and can be applied to the [output] stream to
[print to] the terminal. Similarly, the >> operator is known as the [extraction] operator and can be
applied to the [input] stream to [read from] the terminal.

VECTOR DECLARATIONS:
Declaration Result Size
vector<int> v; Empty vector 0
vector<int> v(5); 5 zeros — pre-filled trap 5
vector<int> v(5, 9); Five 9s — {9,9,9,9,9} 5
vector<int> v = {1,2,3}; Initialiser list — {1,2,3} 3
vector<string> v; Empty vector of strings 0
vector<vector<int>> v(3, 2D — 3 rows, 4 cols, all zeros 3×4
vector<int>(4,0));

ARRAY DECLARTION

Declaration Result Notes

array<int, 5> a; 5 elements — garbage values trap NOT zeroed
array<int, 5> a = {}; 5 zeros — value-initialised safe
array<int, 3> a = {1,2,3}; {1, 2, 3} must match size
array<array<int,4>,2> m = 2 rows × 4 cols, all zeros read inside-out
{};
array<array<int,3>,3> m = 3×3 grid, all zeros square
{};
12. Exam traps — memorise these

What you see Wrong assumption Correct answer

int x; 'That's allocation' It is a declaration
'9' (single quotes) 'That's an int' It is a char
for (int x : v) { x=0; } 'The vector changes' It doesn't — x is a copy. Need
int& x.
vector<int> v(N) 'v is empty, ready for v has N zeros already — size is
push_back' already N
return type int for 'int is fine for average' Integer division truncates — use
median double + /2.0
const vector<int>& v 'I can modify elements' You cannot — remove const if
modification needed
cin << x 'Reads input' Compile error — use cin >> x
main() return value 'It's the output' It's an exit/error code. 0 =
success.
RAM allocation phase 'Compile phase' The Load phase
No base case 'Recursion stops eventually' Infinite recursion → stack
overflow
Prototype vs definition 'Same thing' Prototype has no body.
Definition has body.

13. Quick definition glossary

Term One-line definition
Declaration Naming a variable/function — reserves the name,
no value yet
Initialisation Declaration + first value in one step: int x = 5
Assignment Giving a new value to an already-declared
variable
Prototype Return type + name + parameter list — no body
Definition The full implementation including the function
body
Base case The recursion-stopping condition that returns
directly without a recursive call
Stack overflow Memory exhaustion caused by too many
nested/infinite function calls
Statically typed Variable types fixed and checked at compile time
Compiled language Source code translated to machine code before
execution
Pass by value Function receives a copy — original unaffected
Pass by reference Function receives alias — modifications affect
original
Global scope Declared outside all functions — visible
everywhere in the file
Local scope Declared inside a function or block — only visible
there
Pointers int x = 5; // normal variable — stores the value 5

int* p = &x; // pointer — stores the ADDRESS of x

cout << x; // prints 5 (the value)

cout << &x; // prints 0x61ff08 or similar (the

address)

cout << p; // prints 0x61ff08 (same address — p

holds it)

cout << *p; // prints 5 (the value AT that address)

Term One-line definition

Good luck! — COMS1018A C++ Theory Notes