C++ is a complied (vs interpreted: python), general-purpose (vs domain-specific: HTML) programming language created by Danish programmer Bjarne Stroustrup as an extension to C.

Basic

Compiler

A compiler translate a high level language into a low level language and create an executable program.

  1. Pre-processor: read preprocessing lines #include "foo.hpp"
  2. Compiler: turn the above code it into assembly code (ASM).
    • front end create IR (intermediate representation) with SSA (static singale assignment). The runtime is .
    • middle end optimize IR. remove unnecessary operations, or more.
    • back end produce ASM
  3. Assembler: turn ASM into binary code
  4. Linker: link all relevant headers, libraries together
  5. Debugger: type checking
  6. Object Copy: generate .exe (for windows), and .bin (for mac)

G++

Compile with g++ at the command line:

1
2
3
$ g++ toto.cpp
$ g++ toto.cpp -E (show c pre-processor)
$ g++ toto.cpp --verbose (ask compile to give different steps)

Running the complied result:

1
$ /a.exe

The C++ standard library is a collection of classes and functions, represented by different headers. For example, include the <iostream> header to handle input and outputs and other non-standard headers using double quoto.

1
2
#include <iostream>
#include "foo.h"

Macro

1
2
define N 4
std::cout << N + 2; // show 6

Guards

In C++, function, class and variable can only be declared once. We use guards to make sure we do not duplicate declaration in multiple files.

1
2
#ifndef "foo.h"
#define "foo.h"

Namespace

Some classes and functions are grouped under the same name, which divides the global scope into sub-scopes, each with its own namespaces.

Functions and classes in the C++ standard library are defined in the std namespace. For example, the cin (standard input), cout (standard output) and end (end line) objects.

1
2
3
4
char c;
std::cin >> c;
std::cout << c;
std::endl;

Alternatively, we can use using namespace std;.

Data Type

Every variable has to have a type in C++, and the type has to be declared and cannot be changed. There are fundamental types and user-defined types (classes)

Characters In computer, each bit stores a binary (0/1) value. A byte is 8 bits. The computer stores characters in a byte using the ASCII format.

Numbers The computer stores numbers in binary format with bits. The leftmost bit is used to store the sign of a number. (See twos-complement method). Real values are stored using a mantissa and an exponent:

Note that very few values can be exactly represented, and how close we can get depends on the number of bits available.

Type Size (Bytes) Value Range
bool 1 true or false
char 1 -128 to 127
short 2 -32,768 to 32,767
int 4 -2,147,483,648 to 2,147,483,647
float 4 3.4E +/- 38
double 8 1.7E +/- 308

C++ is a strongly typed language, which means type errors needs to be resolved for all variables at compile time.

Function

Every console application has to have a main() function, which takes no argument and returns an integer value by default.

A function that adds two numbers:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;

int Add(int a, int b)
{
return a+b;
}

int main()
{
int result = Add(2, 3);
cout << " Result: " << result << endl;
}

Overloading allows 2 or more functions to have the same name, but they must have different input argument types.

Function Object

Function object, or functors, are objects that behave like functions, are functions with state.

A regular function looks like this:

1
2
3
4
5
int AddOne(int val)
{
return val+1;
}
int result = AddOne(2)

A function object implementaion:

1
2
3
4
5
6
7
8
9
10
11
12
class AddOne
{
public:
int operator()(int& val)
{
return val+1;
}
};

AddOne addone;
int val = 2;
int result = addone(val)

Lambda

Lambdas is a new feature introduced in C++11, which is an inline function that can be used as a parameter or local object.

1
2
3
4
[] (string s) // [] is the lambda introducer/capture clause
{
cout << s << endl;
}

Example 1

1
2
3
vector<int> v{1, 3, 2, 4, 6};
for_each(v.cbegin(), v.cend(), //range
[](int elem) {cout << elem << endl;}) //lambda

Example 2

1
2
3
vector<int> v{1, 3, 2, 4, 6};
transform(v.begin(), v.end(),
v.begin(), [] (int elem) {return elem * elem});

Example 3

1
2
3
4
5
6
7
vector<Person> ppl;
sort(ppl.begin(), ppl.end(),
[](const Person& p1, const Person&p2)
{
if (p1.GetAge() < p2.GetAge()) return true;
else return false;
});

Extern

The keyword extern means the function is declared in another file.

1
2
extern int foo(int a);
int main() { return foo(100); }

Inline Function

C++ provides inline funcitons such that the overhead of a small function can be reduced. When inline function is called the entire code of the function is inserted at the point of the inline function call.

Typedef

Use typedef keyword to define a type alias.

1
2
3
4
typedef double OptionPrice;
typedef double StockPrice;
typedef double Strike;
OptionPrice BSPrice(StockPrice S, Strike K)

Operators

Standard operations:

1
2
3
4
5
6
7
8
9
Arithmetic: +, -, *, /
Comparison: <, >, <=, >=
Negate: !
Equality, non Equality: ==, !=
Logical and, or, &&, ||
Assignment: =
Modulo: %
Increment, Decrement: i++, i--
Multiple Operations: i += 1, i -= 1, i *= 1, i /= 1

Note the difference between i++ and ++i

1
2
i++; // return (old) i and increment i
++i; // increment i and return new i

Const

Use the const keyword to define a constant value. The compiler will stop any attempt to alter the constant values.

Since C++ is a strongly typed language, it is preferred to use const int N = 4, instead of #define N 4, as the former defines a type.

Reference

Example 1 A reference is an alias for a variable and cannot rebind to a different variable. We can change val by changing ref:

1
2
3
int val = 10;
int& ref = val;
ref = 20; // this will change val to 20

Example 2 We can also bind a const reference to a const object. An error will be raised if attempt to change the value or the reference.

1
2
3
4
const int val = 10;
const int& ref = val;
val = 20; // error
ref = 20; // error

Example 3 We can also bind a const reference to a non-const object, thereafter we can NOT change the object using the reference.

1
2
3
4
int val = 10;
const int& ref = val;
val = 20; // ok
ref = 20; // error


Pass By Value In a function, we can pass an argument by either value or reference. When passing by value, the variable x will NOT be changed. In this case, we waste time to both create a copy inside the function and memory to store the copy

1
2
3
4
5
6
7
8
9
10
11
void DoubleValue(int number)
{
number = number * 2;
}

int main()
{
int x = 5;
DoubleValue(x);
cout<<"x = "<<x<<endl;
}

1
x = 5

Pass By Reference When passing by reference (by adding & in the function argument parameter), the variable x WILL be changed.

1
2
3
4
5
6
7
8
9
10
11
void DoubleValue(int& number)
{
number = number * 2;
}

int main()
{
int x = 5;
DoubleValue(x);
cout<<"x = "<<x<<endl;
}

1
x = 10

Pass By Const Reference We add const when we do not want the specific function argument to be tempered when passed by reference. In this example, there will be a compiler error as we are trying to change the const reference number in the function.

1
2
3
4
5
6
7
8
9
10
11
void DoubleValue(const int& number)
{
number = number * 2; // error, cannot change const ref "number"
}

int main()
{
int x = 5;
DoubleValue(x);
cout<<"x = "<<x<<endl;
}

Pointer

In computer memory, each stored values has an address associated with it. We use a pointer object to store address of another object and access it indirectly.

There are two pointer operator:

  1. &: address of operator, used to get the address of an object
  2. *: de-reference operator, used to access the object

Example 1

1
2
3
int* ptr = nullptr; // initiate an empty pointer
int* ptr = &val; // initiate ptr with the address of val
*ptr = 20; // change val using the ptr pointer

Example 2 If the object is const, a pointer cannot be used to change it.

1
2
3
const int val = 10;
const int* ptr = &val;
*ptr = 20; // error

Example 3 You can have a pointer that itself is const

1
2
3
4
5
6
int val = 10;
int* const ptr = &val;
*ptr = 20; // ok

int val2 = 20;
ptr = &val2 // error, as the pointer is const

Casting

C++ allows implicit and explicit conversions of types.

1
2
3
4
short a = 1;
int b;
b = a; // implicit conversion
b = (int) a; // explicit conversion

However, the traditional explicit type-casting allows conversions between any types, and leads to run-time error. To control these conversions, we introduce four specific casting operators:

  • dynamic_cast<new_type>( ): used only with pointers (and/or references to objects); can cast a derived class to its base class; base-to-derived conversions are allowed only with polymorphic base class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Base {virtual void foo() {} };
class Derived : public Base { };

int main() {

Derived* derived_ptr;
Base* base_ptr = dynamic_cast<Base*> (derived_ptr);

Base* base_ptr_2 = new Derived;
Derived* derived_ptr_2 = dynamic_cast<Derived*> (base_ptr_2);
// ok, base class polymorphic

Base* base_ptr_3 = new Base;
Derived* derived_ptr_3 = dynamic_cast<Derived*> (base_ptr_3);
// will not work, derived_ptr_3 will be assigned a nullptr

std::cout << "derived_ptr_2: " << derived_ptr_2 << std::endl;
std::cout << "derived_ptr_3: " << derived_ptr_3 << std::endl;
return 0;
}
1
2
derived_ptr_2: 0x7fa5cec00630
derived_ptr_3: 0x0


  • static_cast < new_type>( ): used only with pointers (and/or references to objects); can cast base-to-derived or derived-to-base, but no safety check at run-time;
1
2
3
Base* base_ptr_3 = new Base;
Derived* derived_ptr_3 = static_cast<Derived*> (base_ptr_3);
// not nullptr this time, but lead to error when de-referencing derived_ptr_3
1
derived_ptr_3: 0x7fc3d7400690


  • reinterpret_cast <new_type>( ): convert pointer to another unrelated class; often lead to unsafe de-referencing
1
2
3
4
5
class A {};
class B {};

A* a = new A;
B* b = reinterpret_cast<B*> (a);


  • const_cast <new_type>( ): remove/set the constant-ness of an object

Array (C-Style)

An array is a fixed collection of similar kinds of items that are stored in a contiguous block in memory. We define the size of the array at creation, and the array index starts a 0 in C++.

1
2
int a[10];
int a[] {1, 2, 3} // uniform initializer syntax

The address of the array is the same as the address of the first element of the array. Therefore, we can access an array using pointer increment - very efficient.

1
2
3
4
int a[10];
int* ptr = &a[0]; // the same as int* ptr = a
int a0 = a[0]; // the same as int a0 = *ptr
int a3 = a[3]; // the same as int a3 = *(ptr+3) or *(a+3)

Dynamic Allocation

Dynamic memory allocation is necessary when you do NOT know the size of the array at compile time. We use a new keyword paired with a delete keyword.

1
2
3
int* a = new int[10];
delete[] = a; // correct. this tells the CPU that it needs to clean up multiple variables instead of a single variable
delete a; // incorrect. using this version will lead to a memory leak.

Dynamic allocate a matrix with cast.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
void func(double** a) {
* a = new double[16];
}


int main() {
int (* a)[4];
func( (double**)&a );

for (int i=0; i<4; i++) {
for (int j=0; j<4; j++) {
a[i][j] = 1;
}
}

for (int i=0; i<4; i++) {
for (int j=0; j<4; j++) {
std::cout << a[i][j] << " " ;
}
std::cout << std::endl;
}
}

1
2
3
4
5
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
`

Library

A C++ library is a package of reusable code typically with these two components:

  • header file
  • precompiled binary containing the machine code for functionality implemntation

There are two types of c++ libraries: static and dynamic libraries.

  • a static library has a .a (.lib on Windows) extension and the library codes are complied as part of the executable - so that user only need to distribute the executable for other users to run the file with a static library.
  • a dynamic library has a .so (.dll on Windows) extension and is loaded at run times. It saves space as many program can share a copy of dynamic library code, and it can be upgraded to new versions without replacing all the executables using it.

Condition

If/Else

1
2
3
4
5
6
7
8
9
10
11
12
if (condition_1)
{
statement1;
}
else if (condition_2)
{
statement2;
}
else
{
statement2;
}

Switch

A switch statement tests an integral or enum value against a set of constants. we can NOT use a string in the switch statement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
int value = 0;
cin >> value;
switch(value)
{
case 0:
cout << "value is zero";
break; // if remove this break, it will also show case 1 even if value is 0
case 1:
cout << "value is one";
break;
default:
cout << "value is not 0 or 1";
}
}

While / Do While / For Loop

While loop:

1
2
3
4
5
6
int n = 0;
while (n < 10)
{
cout << " n: " << n << endl;
n = n + 1;
}

Do while loop:

1
2
3
4
5
6

do {
cout << "Enter number (0 to end): ";
cin >> n;
cout << "You entered: " << n << "\n";
} while (n != 0);

For loop:

1
2
3
4
for (unsigned int n = 0; n < 10; ++n)
{
cout << "n: " << n << endl;
}

For loop with two variables:

1
2
3
4
for (unsigned int i = 0, j = 0; i < 10 && j < 10; ++i, j+=2)
{
cout << "i:" << i << ", j:" << j << endl;
}

Enum

The enum (enumerated) type is used to define collections of named integar constants.

1
2
3
4
5
6
7
enum CurrencyType {USD, EUR, GBP};
cout << USD << " " << EUR << " " << GBP;
0 1 2

enum CurrencyType {USD, EUR=10, GBP};
cout << USD << " " << EUR << " " << GBP;
0 10 11

Class

A class achieve data abstraction and encapsulation.

  • abstraction refers to the separation of interface and implementation
  • encapsulation refers to combining data and functions so that data is only accessible through functions.

Member Variable & Function

Define a customer class with member variable and function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Customer
{
public:
Customer(); // default constructor
Customer(string name, string address);
~Customer(); // destructor, to free up resources

string GetName();
string GetAddress();
void SetAddress(string address);

private:
string name_;
string address_;
};

Instantiate Customer class instances to represent different customer.

1
2
3
4
5
6
7
Customer c1("Joe", "Hyde Park");
Customer c2("Jim", "Chicago");
Customer c3("John", "New York");

// Use `.` to access member function.
c1.GetName()
c2.SetAddress("Beijing")

Protection Level

There are three protection levels to keep class data member internal to the class.

  1. public accessible to all.
  2. protected accessible in the class that defines them and in classes that inherit from that class.
  3. private only accessible within the class defining them.

Constructor / Destructor

A constructor is a special member functions used to initialize the data members when an object is created. This is an example to use initializer list to create more efficient constructors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Customer::Customer()
: name_(""),
address_("")
{
// name_ = "";
// address_ = "";
}

Customer::Customer(string name, string address)
: name_(name),
address_(address)
{}

Customer::~Customer()
{}

Free-Store

There are several ways to create objects on a computer:

  • Automatic/Stack int a;

  • Dynamic Allocated

    • Free Store int* ptr = new a[10];
    • Heap allocated/freed by malloc/free

Summarized in a table from geeksforgeeks

Parameter Stack Heap
Basic Memory is allocated in a contiguous block Memory is allocated in any random order
Allocated and de-allocation Automatic by compiler instructions Manual by programmer
Cost Less More
Access time Faster Slower
Main issue Shortage of memory Memory leak/fragmentation

We use -> to access free-store object’s member functions:

1
2
3
Customer* c = new Customer("Joe", "Chicago");
c->GetName()
c->SetAddress("New York")

Const Member Functions

A const object can only invoke const member function on the class. A const member function is not allowed to modify any of the data members on the object on which it is invoked. However, if a data member is marked mutable, it then can be modified inside a const member function.

1
2
const Customer c1("Joe", "Hyde Park");
cout << c1.GetName(); // ok if GetName() is a const member function.

Static Member

We use static keyword to associate a member with the class, as oppose to class instances. A static data member can NOT be accessed directly using a non-static member function.

Static member variables can NOT be initialized through the class constructor, rather, they are initialized once outside the class body. However, a const static member variable can be initialized within the class body.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Counter
{
public:
Counter();
static int GetCount();
static void Increment();
private:
static int count_; // non-const static need to be initialized outside
const static int count_2_ = 0; // const static can be initialized within
};

int Counter::count_ = 0;

Counter c;
c.Increment(); // or Counter::Increment()

This

Every non-static member function has access to a this pointer, which is initialized with the address of the object when the member function is invoked.

1
2
3
4
5
6
double Currency::GetExchangeRate()
{
return exchangeRate_;
return this->exchangeRate_; // equivalent
return (*this).exchangeRate_; // equivalent
}

Copy Constructor

We use the copy constructor to construct an object from another already constructed object of the same type.

1
2
3
4
5
6
7
8
9
10
11
class Customer
{
Customer(const Customer& other);
};

Customer::Customer(const Customer& other)
: name_(other.name_)
address_(other.address_)
{}

Customer c2(c1);

Assignment Operator

We use the assignment operator to assign an object of the same type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Customer
{
Customer& operator=(const Customer& other);
};

Customer& Customer::operator=(const Customer& other)
{
if (this != &other) //checking for self assignment
{
name_ = other.name_;
address_ = other.address_;
}
//return the object on which the function was invoked
return (*this);
}

Shallow / Deep Copy

The default copy constructor and assignment operator provides shallow copy, which copies each member of the class individually. For pointer member, the shallow copying copies the address of the pointer, resulting in both members pointing to the same object on the free store.

A deep copy, however, creates a new object on the free store and copy the contents of the object the original pointer is pointing to.

Deep Copy copy constructor

1
2
3
4
5
6
Customer::Customer(const Customer& other)
:name_(other.name_),
address_(other.address_),
account_(new Account(other.account_->GetAccountNumber(),
other.account_->GetAccountBalance()))
{}

Deep Copy assignment operator

1
2
3
4
5
6
7
8
9
10
11
12
Customer& Customer::operator=(const Customer& other)
{
if (this != &other)
{
name_ = other.name_;
address_ = other.address_;
delete account_;
account_= new Account(other.account_->GetAccountNumber(),
other.account_->GetAccountBalance());
}
return (*this);
}

The Rule of 3

There are 3 operations that control the copies of an object: copy constructor, assignment operator, and destructor. If you define one of them, you will most likely need to define the other two as well.

Singleten Class

The Singleton design pattern makes sure only one instance of an object of a given type is instantiated in a program, and provides a global point of access to it

  1. change the access level of the constructor to private
  2. add new public member function Instance() to create the object
  3. use static member variable to hold the object
1
2
3
4
5
6
7
8
9
10
class CurrencyFactory
{
public:
static CurrencyFactory* Instance();
Currency CreateCurrency(int currencyType);

private:
CurrencyFactory();
static CurrencyFactory* instance_;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
CurrencyFactory* CurrencyFactory::Instance()
{
if (!instance_)
instance_ = new CurrencyFactory;
return instance_; // no more than one CurrencyFactory object.
}

Currency CurrencyFactory::CreateCurrency(int currencyType)
{
switch(currencyType)
{
case EUR:
return Currency("EUR", 0.7901);
case GBP:
return Currency("GBP", 0.6201);
case CAD:
return Currency("CAD", 1.1150);
case AUD:
return Currency("AUD", 1.1378);
default:
return Currency("USD", 1.0);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "CurrencyFactory.h"
int main()
{
cout << "Enter amount in USD:";
double amount;
cin >> amount;

cout << "Enter currency to convert to (ECU/GBP/CHF/JPY): ";
string symbol;
cin >> symbol;

double convertedAmount = 0.0;
Currency currency = CurrencyFactory::Instance()->CreateCurrency(symbol);
cout << currency.ConvertFromUSD(amount) << endl;
}

Inheritance

Classes related by inheritance form a hierachy consisting of base and derived classes. The derived class inherit some members from the base class subject to protection level restrictions, and may extend/override implementation of member functions in the base class.

1
2
3
4
5
6
7
8
9
10
class Person
{
protected:
string name_;
string address_;
};
class Student : public Person
{
string school_;
};



Virtual

Different derived classes may inplement member functions from the base class differently. The base class uses virtual keyword to indicate a member function that may be specialized by derived classes.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Base
{
public:
virtual void Method1();
virtual void Method2();
void Method3();
};
class Derived : public Base
{
void Method1(); // specializes Method1()
// uses default implementation of Method2()
// can NOT specialize Method3()
};

Abstract Class

The base class has to either provide a default implementation for that function or declare it pure virtual. If a class has one or more pure virtual function, it is called an abstract class or interface. An abstract class cannot be instantiated.

1
2
3
4
5
6
7
8
9
class Base
{
public:
virtual void Method1() = 0;
};
class Derived : public Base
{
// this derived is also an abstract
};

Virtual Destructor

When we delete a derived class we should execute both the derived class destructor and the base class destructor. A virtual base class destructor is needed to make sure the destructors are called properly when a derived class object is deleted through a pointer to a base class.

If we delete a derived class object through a pointer to a base class when the base class destructor is non-virtual, the result is undefined.

Polymorphism

The types related by inheritance are known as polymorphic. types. We can use polymorphic types interchangeably.

We can use a pointer or a reference to a base class object to point to an object of a derived class – this is known as the Liskov Substitution Principle (LSP). This allows us to write code without needing to know the dynamic type of an object

1
2
3
4
5
BankAccount* acc1 = new Savings();
acc1->ApplyInterest(); // ApplyInterest() on the Savings object

BankAccount* acc2 = new Checking();
acc2->ApplyInterest(); // ApplyInterest() on the Checking object

We can write one function which applies to all account types.

1
2
3
4
5
void UpdateAccount(BankAccount* acc)
{
acc->ApplyBankingFees();
acc->ApplyInterest();
}

1
2
3
4
5
void UpdateAccount(BankAccount& acc)
{
acc.ApplyBankingFees();
acc.ApplyInterest();
}

Standard Template Library (STL)

Sequential Container

std::array

The STL array class from offers a more efficient and reliable alternative for C-style arrays, where size is known and we do not have to pass size of array as separate parameter.

1
2
3
4
5
6
7
8
#include <array>
array <int> a1 = {1, 2, 3};

a1.front();
a1.back();
a1.size();
a1.at(1);
get<1>(a1);

std::vector

Vectors are the stored contiguously same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted. Vector size is double whenever half is reached.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <vector>
vector<int> v1;

v1.begin();
v1.end();
v1.size();

v1.push_back(); // pushes the elements into a vector from the back
v1.pop_back(); // removes the elements from a vector from the back.

v1.insert(i); // inserts new elements before the element at the specified position
v1.assign(i); // assigns new value to the vector elements by replacing old ones
v1.erase(i); // removes elements from a container from the specified position or range

std::list

Different from arrays and vectors, A list is a sequential container that allows non-contiguous memory allocation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <list>
list<int> l1;
for (int i = 0; i < 10; i++) {
l1.front(); // returns the value of the first element
l1.back(); // returns the value of the last element

l1.push_front(i); // adds a new element ‘i’ at the beginning of the list
l1.push_back(i); // adds a new element ‘i’ at the back of the list

l1.pop_front(); // removes the first element and reduces list size by 1
l1.pop_back(); // removes the last element and reduces list size by 1

l1.begin(); // returns an iterator pointing to the first element of the list
l1.end(); // returns an iterator pointing to the last element of the list
}

std::string

The STL string class stores the characters as a sequence of bytes, allowing access to single byte character. Any string is terminated by a \0, so the string foo actually stores four characters.

size()

The use sizeof() to return the size of an array in bytes. Use .size() member function to return the number of elements in a STL container.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>

using namespace std;

int main() {
int a[5] {1, 2, 3, 4, 5};
cout << "The size of a: " << sizeof(a) << " bytes" << endl;

vector<int> b {1, 2, 3, 4, 5};
cout << "The size of b: " << sizeof(b) << " bytes" << endl;
cout << "The size of b: " << b.size() << " elements" << endl;

}

1
2
3
The size of a: 20 bytes
The size of b: 24 bytes
The size of b: 5 elements

Associative Container

std::set

Sets are an associative container where each element is unique. The value of the element cannot be modified once it is added to the set.

1
2
3
4
5
6
7
8
9
10
11
#include <set>
set<int> s1;
for (int i = 0; i < 10; i++) {
s1.begin();
s1.end();
s1.size();

s1.insert(i);
s1.erase(i);
s1.find(i);
}

std::map

A std::map sorts its elements by the keys.

Algorithm

The STL provides implementations of some widely used algorithms.

  • <algorithms> header: sorting, searching, copying, modifying elements
  • <numeric> header: numeric operation

Sort

1
2
3
4
5
6
int main()
{
vector<int> values{10, 1, 22, 12, 2, 7};
//sort takes a range
sort(values.begin(), values.end());
}
1
2
3
4
5
6
int main()
{
vector<int> values{10, 1, 22, 12, 2, 7};
//binary_search takes a range and a value
bool found = binary_search(values.begin(), values.end(), 12);
}

Copy

1
2
3
4
5
6
7
8
int main()
{
vector<int> values1{ 10, 1, 22, 12, 2, 7 };
//destination
vector <int> values2;
copy(values1.begin(), values1.end(), //input range
back_inserter(values2)); //output iterator
}

Replace

1
2
3
4
5
6
7
int main()
{
vector<int> values{ 10, 1, 22, 12, 2, 7 };
replace(values.begin(), values.end(), //range
1, //old value
111); //new value
}

Numeric

1
2
3
4
5
6
7
8
9
int main()
{
vector<int> v2{ 5, 4, 3, 2, 1 };
vector<int> v2{ 1, 2, 3, 4, 5 };
int r1 = accumulate(v1.begin(), v1.end(), 0); //range

int r2 = inner_product(v1.begin(), v1.end(),
v2.begin(), 0);
}

Complexity Comparison

complexity.png

Smart Pointer

std::unique_ptr

A unique pointer takes unique ownership in its pointed object. The unique pointer delete the object they managed either when the unique pointer is destroyed or when the object’s value changes.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <memory>

std::unique_ptr<Option> sp(new Option());
// initates a smart pointer (or through reset: sp.resert(Option()).)

std::unique_ptr<Option> sp2(sp);
// error: does not allow two reference (sp, sp2) to the same object (new Option());

std::unique_ptr<Option> sp2(std::move(sp));
// now sp is destroyed and sp2 takes ownership of the Option object

sp2->getPrice();
// smart pointer can be used as regular pointer

std::shared_ptr

The shared pointer counts the reference to its pointed object and can store and pass a reference beyond the scope of a function. In OOP, the share pointer is used to store a pointer as a member variable and can be used to reference value outside the scope of the class.

1
2
3
4
5
6
7
std::share_ptr<Option> sp2;
{
std::share_ptr<Option> sp(new Option());
sp2=sp;
}
sp2->getPrice();
// the Option object is not deleted after local scope ends

Creating a vector of shared_ptr:

1
2
3
4
5
#include <vector>
std::vector<std::shared_ptr<Option>> option_list;
for (int i=0; i< 10; i++) {
option_list.push_back(std::shared_ptr<Option>(new Option(i)));
}

std::weak_ptr

A weak_ptr works the same as shared pointer, but will not increment the reference count.

1
2
3
4
5
6
std::weak_ptr<Option> sp2;
{
std::share_ptr<Option> sp(new Option());
sp2=sp;
}
sp2->getPrice(); // error! the Option object does not exist beyond scope.

Parallel Processing

Threading

A thread is a small sequence of programmed instruction and is usually a component of a process. Multi-threading can exist within one process, executing concurrently and share resources such as memory, while processes do not share their resources.

The std::thread class in c++ supports multi-threading, and can be initiated to represent a single thread. We need to pass a callable object (function pointer, function, or lambda) to the constructor of the std::thread class. We use the std::thread.join() method to wait for the copmletion of a thread.

Here we initiate two threads. Both threads share memory and attempt to modify the balance variable at the same time which lead to concurrency issue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <thread>

using namespace std;

int main() {

int balance = 0;

// t1 starts
thread t1([&balance] {for (int i=0; i<1000000; i++) {balance++;}});

// t2 starts
thread t2([&balance] {for (int i=0; i<1000000; i++) {balance--;}});

t1.join(); // the main() waits here until t1 completes
t2.join(); // the main() waits here until t2 completes

cout << balance << endl;
cout << "END OF CODE" << endl;
}

1
2
153258
END OF CODE

We introduce the an mutex, or mutual exclusive, object, which contains a unique id for the resources allocated to the program. A thread can lock the resource by a std::mutex.lock() method, which prevent other thread from sharing the resource until the mutex becomes unlocked.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <thread>
#include <mutex>

using namespace std;

int main() {

int balance = 0;
mutex m;

// t1 starts
thread t1([&balance, &m] {for (int i=0; i<1000000; i++) {
m.lock();
balance++;
m.unlock();
}});

// t2 starts
thread t2([&balance, &m] {for (int i=0; i<1000000; i++) {
m.lock();
balance--;
m.unlock();
}});

t1.join(); // the main() waits here until t1 completes
t2.join(); // the main() waits here until t2 completes

cout << balance << endl;
cout << "END OF CODE" << endl;
}
1
2
0
END OF CODE

Condition Variable

A condition variable is an object that can block the calling thread until notified to resume. It uses a unique_lock (over a mutex) to lock the thread when one of its wait functions is called.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <mutex>
#include <thread>
#include <vector>

using namespace std;

mutex m;
condition_variable cv;
vector<int> v;

bool ready = false;
bool processed = false;

void make_vector() {

unique_lock<std::mutex> lk(m); // own the mutex
cv.wait(lk, []{return ready;}); // wait until main() sends data

for (int k = 0; k < 10; ++k) {
v.push_back(k);
}

processed = true;
lk.unlock(); // manual unlocking is done before notifying
cv.notify_one();
// unblocks one of the threads currently waiting for this condition
// if no threads are waiting, the function does nothing
// if more than one threads are waiting, it is unspecified which will be selected
}

int main() {
thread t(make_vector);

ready = false;
processed = false;
{
cout << "main() signals ready for processing\n";
ready = true;
}
cv.notify_one();

{
unique_lock<std::mutex> lk(m); // own the mutex
cv.wait(lk, []{return processed;}); // wait for cv.notify_one
cout << "back to main(), vector is processed\n";
}

for (auto i : v)
{
cout << i << " ";
}

t.join();
}
1
2
3
main() signals ready for processing
back to main(), vector is processed
0 1 2 3 4 5 6 7 8 9




Reference:

  • FINM 322 Lecture Notes, Chanaka Liyanaarachchi, the University of Chicago