Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

Advanced Programming with C++ Cheat Sheet (DRAFT) by

Everything you need to know about this module for the exam

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Stacks

Way of sorting data
Data Structure
Last in First Out (LIFO)
Push Back - Add item to top of stack
Pop Back - Remove item from top of stack

Pointers

Variables which point to a space in memory
Example:
int* ptr = new int;

delete ptr;

Stack

Value objects are pushed onto the stack.
Examples:
int i = 4;

float j = 3.4f;

double k = 7.8;

char l = 'h';

Big O

Expresses the efficiency for an algorithm
Can express worst, average or best case
Mathem­atical analysis
Measure of comput­ational resources
Example: O(n^2) takes longer than O(2n)

Logarithms

Base 2 is assumed (NOT 10)
So logn is log2n
log2n = a
is Equivalent to
2^a = n

Linked Lists

Object is held in a black of memory
An instance of a class includes a pointer to another instance of the same class
[]-> []-> []->
Last in First Out (LIFO)
2 Classes are used
The end of the list is 0
Example:
Push Front method
1. 'Head' points at 0
2. Create a new element
3. Set 'next' pointer of new element to point at head
4. Set 'head' to point at new element
  

Inline

Function which is saved in memory
Usually used for smaller helper functions
Speeds up compile time but results in more memory being used up

Heap

Object created with the 
new
keyword are pushed onto the heap

Casting

Change the data type of a variable to another
Examples:
float var1 = 34.8f;

int var2 = static­_ca­st<­int­>(v­ar1);

int i = 4;

char ptr  = reinte­rpr­et_­cas­t<char>(&i);

Templates

Generic Progra­mming
 
template <cl­ass­T> void trivial(T term)
 
T
can be any data type

Recursion

A Function that calls itself
Hard to debug
Better to use loop in most cases
Process:
- Function Call - carry out operations
- Place state of function onto stack
- Call Recurse function - carry out operations
- Place state of recurse function onto stack
- Call the recurse of the recurse function etc.

Quick Sort

Very Efficient Algorithm
Uses Recurision
Big O Notation - O(nlogn)
Algorithm:
- If array is NOT empty
- Choose a number is act as a pivot (usually rightmost element)
- Partition the array into 2 sections
- If a number is smaller than pivot move into first section
- Else move into second section
- Recurse for both sections until you have one element left
  

Hash Table

Array type Data Structure
Fast storag­e/r­etr­ieval method
Generates integer value
Example: Turns name into a number which is the index of the array
Big O Notation - O(1) - Very Fast
Hashing Methods
Linear Probing
Search for an empty space using linear search
Quadratic Probing
Searching for an empty space making larger steps
e.g. 1, 4, 9, 16... rather than 1,2,3,4... with linear probing
Chained Hash Table
Each location is head of chain
Each location has associated linked list
Retrieval means chain must be searched
Each location is effect­ively a bucket
Open Address Hash Table
All keys are stored directly in the table
Everything gets stored in table
Collisions resolved by probing
Avoid making the hash table larger than 80% capacity to avoid collisions

Bitwise

Changing the binary bits in a variable
Example:
x = x << 1; //Shift bits left by 1

12 is in binary 0000 1100
Shifting left by 1 changes it to
0001 1000 which is 24

?

a > b ? max = a : max = b;
Is equivalent to
if ( a > b ) max = a; else max = b;

Deep Copy

Copy of object and any dynami­cally allocated memory pointed to by the object

Function Pointers

Used for pointing at function calls
Example:
#include <fu­nct­ion­al>

int foo(float a, float b);

std::f­unc­tio­n<i­nt(­flo­at,­flo­at)> fp; //points at function which returns an int and has 2 float parameters

fp = &foo;

Shallow Copy

Copy of Object but not any dynami­cally allocated memory pointed to by the object