Programming in C++

Programming in C++
David Wai {wjx}
2025-02-15
 Programming in C++ 2

Why C++?
● C++ shares similar syntax with many other programming languages
○ Java, JavaScript, C#, Objective C, PHP, etc.

● Centered around important CS concepts

○ Data types, control structures, object-oriented programming

● Wide range of applications and can be run in different environments

○ Servers, operating systems, games, embedded systems, etc.
○ C++ standard provides a portable interface. Programs can be compiled into executable
for different systems.
 Programming in C++ 3

Why C++ for competitive programming?

● C++ programs runs very fast
● C++ STL comes with useful algorithms and data structures
○ Sorting, binary search, stack, heap (priority_queue), binary search tree (set, map), etc.

● C++ programs are easier to debug

def has_odd(l):
○ Compilation step can help uncover bugs flag = False
for elm in l:
○ C++ has a stricter syntax
if elm % 2 == 1:
flga = True
return flag

This Python program would not even cause runtime error

 Programming in C++ 4

Why C++ for competitive programming?

● You don’t have any other choice, especially if you want to participate in
external competitions
○ HKOI’s only first class language is C++, Python is a second class programming language
(tasks are not guaranteed to be solvable using python)
○ EGOI supports C++ and Python
○ TFT only supports C++
○ NOI only supports C++
○ APIO only supports C++
○ IOI only supports C++
 Programming in C++ 5

C++ Standard
Starting from 2011, 3 years a standard (C++11, C++14, …)
● C++23 has been published, and work is now underway on C++26
● In most cases, new standards are backward compatible
○ There are some special cases like gets and random_shuffle
● g++ compilation flag: -std=c++11, -std=c++14, …
Different contests and online judges may support different standards
● Codeforces supports C++23
● HKOI Online Judge supports C++20
● IOI, APIO supports C++17
● NOI, EGOI supports C++14
● Be careful about the supported version as some functions may be in new
standard, check the compilation flags if you are not sure about it
 Programming in C++ 6

Basic program structure

#include <iostream> Include library headers
using namespace std;
int main() {
<iostream> provides input
cout << "Hello, World!" << endl; and output functionality
return 0; (cout and endl in this
}
example)
 Programming in C++ 7

Basic program structure

#include <bits/stdc++.h> When using GCC C++ compiler,
using namespace std; <bits/stdc++.h> provides
int main() {
cout << "Hello, World!" << endl;
most functions needed for
return 0; competitive programming
} ● Shorter header
● Avoid compilation errors
caused by missing header,
especially in contests with
no feedback
 Programming in C++ 8

Basic program structure

#include <bits/stdc++.h>
using namespace std; Functions and classes in C++
int main() {
cout << "Hello, World!" << endl;
Standard Library are declared
return 0; within the std namespace
} This line is to “move” everything in
the std namespace into our
program
● Pros: No need to type std::
prefix
● Cons: Program may not be
forward compatible
 Programming in C++ 9

Basic program structure

#include <bits/stdc++.h>

int main() {
Example without
std::cout << "Hello, World!" << std::endl; using namespace std;
return 0;
}
 Programming in C++ 10

Basic program structure

#include <bits/stdc++.h>
using std::cout;
using std::endl; Bring in specific symbols
int main() { This won’t have the forward
cout << "Hello, World!" << endl;
return 0; compatibility issue
}
 Programming in C++ 11

Forward compatibility issue

#include <bits/stdc++.h>
using namespace std; g++ -std=c++03 [Link] -o program
// move first character to the end.
Output: bcdefa
string move(string s) {
return [Link](1) + s[0];
}
g++ -std=c++11 [Link] -o program
int main() {
cout << move("abcdef") << endl; Output: abcdef
return 0;
}
 Programming in C++ 12

Basic program structure

#include <bits/stdc++.h>
using namespace std;
int main() { This is the main program
cout << "Hello, World!" << endl;
return 0;
} Note that the return type is int
 Programming in C++ 13

Basic program structure

#include <bits/stdc++.h> A return code of 0 indicates that the
using namespace std; program ended successfully
int main() { ● Other numbers can be used to
cout << "Hello, World!" << endl;
indicate that there is some
return 0;
} warning / error
● You can use && in the console
to chain commands. In this
example, program B runs only
if program A returns 0
(windows) [Link] && [Link]
(linux) ./a && ./b ● return 0; is optional
 Programming in C++ 14

Basic program structure

#include <bits/stdc++.h>
using namespace std;
int main() {
cout << "Hello, World!" << endl; Send “Hello, World!” and
return 0;
} line break to the output stream

endl also flushes the stream

(useful for interactive tasks)
 Programming in C++ 15

Input and output

#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b; Read two numbers a and b
cout << a + b << endl; Output their sum
return 0;
}
 Programming in C++ 16

Integers
int: 32 bits in most systems
long long: 64 bits in most systems
__int128 is also supported in most modern compilers (no input / output functions)

int main() { Input Output

cout << numeric_limits<int>::min() << '\n';
-2147483648
cout << numeric_limits<int>::max() << '\n';
2147483647
cout << numeric_limits<long long>::min() << '\n'; -9223372036854775808
cout << numeric_limits<long long>::max() << '\n'; 9223372036854775807
return 0;
}

16
 Programming in C++ 17

Arithmetic operators
name syntax name syntax To change the variable itself, you may
also use a += b, a -= b, …
addition a + b bitwise not ~a

subtraction a - b bitwise and a & b For self increment / decrement, you

may use ++ / --
multiplication a * b bitwise or a | b
● x++: return the original value of x,
division a / b bitwise xor a ^ b then increase x by 1
● ++x: increase x by 1, then return the
modulo a % b bitwise left shift a << b reference of x

bitwise right shift a >> b

 Programming in C++ 18

Floating point numbers

float: 32 bits
double: 64 bits
long double: 128 bits
Supported operators: +, -, *, /
 Programming in C++ 19

Division
In C++, we use / for both integer division and floating point division
If both dividend and divisor are integer types, integer division is performed
If any of the dividend and divisor is a floating point type, floating point division is performed

int main() { Input Output

2
cout << 5 / 2 << '\n'; 2.5
2.5
cout << 5.0 / 2 << '\n';
cout << 5 / 2.0 << '\n';
return 0;
}

19
 Programming in C++ 20

Output floating point numbers

By default, C++ output stream outputs large floating point numbers in scientific notation.
Use cout << fixed to output in fixed decimal point
Use cout << setprecision(x) to output in x decimal points (default is 6)

int main() { Input Output

double pi = acos(-1); 3.14159

3.141593
cout << pi << '\n';
3.141592654
cout << fixed << pi << '\n';
cout << setprecision(9) << pi << '\n';
return 0;
}

20
 Programming in C++ 21

Characters
A 8-bit integer type
You can do arithmetic directly on it
In C++, we use single quote for characters and double quote for strings
int main() { Input Output
char c = 'A';
A
cout << c << '\n'; a
c += 32; 0
cout << c << '\n'; 4

c = 48;
cout << c << '\n';
cout << 'E' - 'A' << '\n';
return 0;
}

21
 Programming in C++ 22

Boolean
Only 2 values: true and false
Logical operators:

name syntax

negation !a // not a

and a && b // a and b

inclusive or a || b // a or b
 Programming in C++ 23

Comparison operators
Compare two variables, return bool

name syntax name syntax

equal to a == b less than or equal to a <= b

not equal to a != b greater than or equal to a >= b

less than a < b three-way comparison a <=> b

(since C++20, does not
greater than a > b return bool)
 Programming in C++ 24

If statement
You can omit the bracket if there is only one statement

int main() { Input Output

int a, b;
cin >> a >> b;
3 3 a == b
if (a < b) {
cout << "a < b" << '\n';
}
else if (a > b) {
cout << "a > b" << '\n';
}
else {
cout << "a == b" << '\n';
}
return 0;
}

24
 Programming in C++ 25

For loop
Syntax: for (initial; condition; step)
You can omit the bracket if there is only one statement

int main() { Input Output

1
for (int i = 1; i <= 5; ++i) { 2
3
cout << i << '\n'; 4
5
}
return 0;
}

25
 Programming in C++ 26

Arrays
We can use a character array to store strings

int a[10]; Input Output

const char s[] = "HKOI"; 4 7 11

HKOI
int main() {
cin >> a[0] >> a[1];
cout << a[0] + a[1] << '\n';
cout << s << '\n';
return 0;
}

26
 Programming in C++ 27

Pointers
Pointer stores the address of another variable
Use * to dereference the pointer
Use & to get the address of a variable
int main() { Input Output

int a = 1; 2

int* p = &a;
*p = 2;
cout << a << '\n';
return 0;
}

27
 Programming in C++ 28

C++ array
With the exception of const arrays, (e.g. const char s[])
modern C++ discourages the use of raw arrays
The type and size of an array is fixed once declared
array<int, 10> a; Input Output

const char s[] = "HKOI"; 4 7 11

HKOI
int main() {
cin >> a[0] >> a[1];
cout << a[0] + a[1] << '\n';
cout << s << '\n';
return 0;
}

28
 Programming in C++ 29

C++ array
Arrays can also be declared with initialization
The size and type will be automatically determined (class template argument
deduction, since C++17). Here, the type of a is array<int, 3>
array a{4, 8, 3}; Input Output

int main() { 15
cout << a[0] + a[1] + a[2] << '\n';
return 0;
}

29
 Programming in C++ 30

Benefits of C++ array

For C array, the identifier degenerates into a pointer when passed into
functions
Provides index checking via .at(index), which makes debugging easier
int a[] = {4, 8, 3}; array a{4, 8, 3};
int main() { int main() {
cout << a[0] + a[3] << '\n'; cout << [Link](0) + [Link](3) << '\n';
return 0; return 0;
} }
Likely Output: 4 Runtime error

terminate called after throwing an instance of 'std::out_of_range'

what(): array::at: __n (which is 3) >= _Nm (which is 3)
 Programming in C++ 31

C++ STL
C++ Standard Template Library

A part of C++ Standard Library

Contains four components:

● Algorithms
● Containers
● Functions
● Iterators
 Programming in C++ 32

Why use C++ STL

● STL contains many algorithms and data structures that are useful in
competitive programming
● Can write shorter code
○ Less implementation time (especially if your typing speed is slow)
● No need to care about the implementation detail of the algorithm / data
structure
○ Less debugging time
○ Have more time to focus on other parts of a problem
● Learn about how to write your code in a more standard way
○ You don’t need to know the implementation detail in most of the time
○ But if you want to learn more, you can still look at it and learn some coding conventions
from it
 Programming in C++ 33

Dynamic sized array - Vector

Defined in header <vector>
A dynamic sized array (with O(1) random access)
Similar to pair, comparison (<, <=, ==, …) works with lexicographical order

To declare an empty int vector:

● vector<int> a
To declare a long long vector of size 100:
● vector<long long> a(100)
● vector a(100, 0ll) (since C++17)
 Programming in C++ 34

Dynamic sized array - Vector

To declare a 2D int vector of size n * m with all elements initialized to -1:
● vector<vector<int>> a(n, vector<int>(m, -1))
● vector a(n, vector(m, -1)) (since C++17)
To add an element x to the end of the vector:
● a.push_back(x)
● a.emplace_back(x) (since C++11)
To remove the last element of the vector:
● a.pop_back()
 Programming in C++ 35

Dynamic sized array - Vector

To get the size of the vector
● [Link]() (be careful that the type of the return value is size_t, which is
an unsigned integer type)
To access the first element of the vector:
● [Link]()
To access the last element of the vector:
● [Link]()
To access the ith element (0 based) of the vector:
● a[i]
● [Link](i) (slower, but have bound checking)
 Programming in C++ 36

Iterator
A generalization of pointer
Similar to pointers, can use *it to dereference

The iterator in vector is a random access iterator

● Type of the iterator of vector<int>: vector<int>::iterator
To find the distance of two iterators:
● distance(it1, it2)
○ O(n) in general (n is the distance between it1 and it2)
○ O(1) if they are random access iterators (vector iterator supports)
 Programming in C++ 37

Iterator
To increment it by n elements:
● advance(it, n)
○ O(n) in general
○ O(1) if it is a random access iterator
To get the next iterator (since C++11):
● next(it)
To get the previous iterator (since C++11):
● prev(it)
 Programming in C++ 38

Vector iterators
To get the iterator pointing to the first element of the vector:
● [Link]()
To get the iterator pointing to the element after the last element of the vector:
● [Link]()
There are also reverse iterators, which can be used to iterate through the
vector in reverse order
● [Link](): the iterator pointing to the last element of the vector
● [Link](): the iterator pointing to the element before the first element of
the vector
 Programming in C++ 39

Vector
To iterate through the whole vector:
● Use an index:
○ for (int i = 0; i < [Link](); i++)
○ Access the value using a[i]
● Use a iterator:
○ for (auto it = [Link](); it != [Link](); it++)
○ Access the value using *it
● Use range-based for loop (since C++11):
○ for (auto v : a) (pass by value)
○ for (auto& v : a) (pass by reference)
○ Access the value using v
 Programming in C++ 40

Vector
vector<int> a; Output
for (int i = 0; i < 10; i++) a.emplace_back(10 - i);
for (auto x : a) cout << x << ' '; 10 9 8 7 6 5 4 3 2 1
cout << '\n'; 1
cout << [Link]() << '\n'; 9
a.pop_back();
10 9 8 7 6 5 4 3 2
cout << [Link]() << '\n';
5 5 5 5 5 5 5 5 5
for (int i = 0; i < [Link](); i++) cout << a[i] << ' ';
cout << '\n';
for (auto& x : a) x = 5;
for (auto it = [Link](); it != [Link](); it++) cout << *it << ' ';
cout << '\n';
 Programming in C++ 41

Vector efficiency
The size of a vector is dynamic, how to ensure it does not take too much time
compared to an array?
The main idea is reallocation
When the vector is full, a larger memory space will be allocated (usually with
double size)
Everything in the old space will then be moved to the new space
 Programming in C++ 42

Vector efficiency
vector<int> a; Output
for (int i = 0; i < 10; i++) {
a.emplace_back(i); size: 1 capacity: 1
cout << "size: " << [Link]() << " capacity: " << [Link]() << size: 2 capacity: 2
'\n'; size: 3 capacity: 4
} size: 4 capacity: 4
size: 5 capacity: 8
The allocated size of a vector can be queried by size: 6 capacity: 8
using [Link]() size: 7 capacity: 8
size: 8 capacity: 8
size: 9 capacity: 16
size: 10 capacity: 16
 Programming in C++ 43

Vector efficiency
Assume that you call push_back() n times.
The total cost comprises of:
● Cost of adding an element
○ 1 operation per push_back
○ Total n operations for n push_back
● Cost of moving elements when vector is full
○ 1, 2, 4, 8, …, 2k (where 2k < n)
○ The sum of above = 2k+1 - 1 < 2n
Total cost for n push_back = n + (<2n) < 3n, and therefore is O(n)
We can say that push_back is amortized O(1)
 Programming in C++ 44

Vector efficiency
If you know the expected maximum size of the vector
● use reserve() to preallocate the memory space so reallocate is not
needed
If you just want to use it like a fix-sized array
● Use constructor when declaring the vector
● Use resize() to set the size of the vector
 Programming in C++ 45

Push_back and emplace_back

emplace_back() is faster especially for a large struct
● push_back() copies the object to the vector
● emplace_back() constructs the object inside the vector
Their implementation are slightly different
For example, pushing pair(1, 2) to a vector:
● a.push_back(make_pair(1, 2))
● a.push_back({1, 2}) (since C++11)
● a.push_back(pair(1, 2)) (since C++17)
● a.emplace_back(1, 2)
 Programming in C++ 46

String
Defined in header <string>
C++ strings are very easy to use
Similar to vector
● You can also use ranged-based for loop to iterate over a string
● You can get iterators from string to perform operations
You can concatenate strings together using the + operator
You can compare strings directly using comparison operators
● You can also use compare(), which returns 0 when the strings are equal,
negative number when the left string is smaller, and positive otherwise
 Programming in C++ 47

Iterate over a string

string s = "abcdef"; Output
for (int i = 0; i < [Link](); i++) cout << s[i] << '\n';
for (char& c : s) c -= 32; a
cout << s << '\n'; b
c
d
e
f
ABCDEF
 Programming in C++ 48

Using string::iterator
string s = "abcdef"; Output
for (auto it = [Link](); it != [Link](); ++it) cout << *it << '\n';
reverse([Link](), [Link]()); a
cout << s << '\n'; b
c
d
e
f
fedcba
 Programming in C++ 49

Concatenate strings
string s = "ab"; Output
string t = "d";
s += 'c'; // append a character 3
t += "ef"; // append a string abcdef
cout << [Link]() << '\n';
cout << s + t << '\n';
 Programming in C++ 50

Compare strings
cout << ("abc"s == "abc"s) << '\n'; Output
cout << ("abc"s < "def"s) << '\n';
cout << ("abcd"s > "abc"s) << '\n'; 1
cout << "abc"[Link]("abx") << '\n'; 1
cout << "xyz"[Link]("xyz") << '\n'; 1
cout << "def"[Link]("a") << '\n';
-21
It 0can be any negative integer
3

It can be any positive integer

 Programming in C++ 51

Read one line

string s; Output
getline(cin, s);
cout << s << '\n';
cin >> s;
cout << s << '\n';
 Programming in C++ 52

Find string
string s = "This is a string"; Output
int n = [Link]("is");
cout << n << '\n'; 2
n = [Link]("is", 5); 5
cout << n << '\n'; -1
n = [Link]('q');
18446744073709551615
cout << n << '\n';
cout << string::npos << '\n';
 Programming in C++ 53

Modify string
string s = "abc"; Output
[Link](1, "abc", 2);
cout << s << '\n'; aabbc
[Link](3); aab
cout << s << '\n'; a123b
[Link](1, 1, "123");
cout << s << '\n';
 Programming in C++ 54

Get substring
string s = "[Link] Output
cout << [Link](14, 4) << '\n';
cout << [Link](8) << '\n'; hkoi
[Link]
 Programming in C++ 55

String conversion (since C++11)

string s = "123"; Output
int a = stoi(s);
cout << to_string(a + 1) << '\n'; 124
s += ".456"; 123.579000
double b = stod(s);
cout << to_string(b + 0.123) << '\n';
 Programming in C++ 56

Application - string processing

Please read the problem 01000 - Append Insert Replace
 Programming in C++ 57

Functions
Functions with return type should have a return statement
Void functions can omit the return statement

int square(int x) { Input Output

return x * x;
} 25
void print_max(int a, int b, int c) { 9
cout << max(a, max(b, c)) << '\n';
}
int main() {
cout << square(5) << '\n';
print_max(4, 9, 1);
return 0;
}

57
 Programming in C++ 58

Early return
If you have a return statement at the end of a if block, no need to add else

void print_max(int a, int b, int c) { Input Output

if (a > b && a > c) {
cout << a << '\n'; 9
return;
}
cout << (b > c ? b : c) << '\n';
}
int main() {
print_max(4, 9, 1);
return 0;
}

58
 Programming in C++ 59

Pass by reference
Pass by reference makes the identifier refer to the same variable specified in
the argument. Therefore, the value can be changed inside the function
Value 1

void pass_by_value(int a) { a = 5; } Input Output

void pass_by_reference(int& a) { a = 5; }
int main() {
1 5
int x = 1;
int y = 2;
pass_by_value(x);
pass_by_reference(y);
cout << x << " " << y << '\n';
return 0;
}

59
 Programming in C++ 60

Pass by reference - vector

All types are passed by value (unlike Java / Javascript / Python)

void pass_by_value(vector<int> a) { a[0] = 5; } Input Output

void pass_by_reference(vector<int>& a) { a[0] = 5; }
int main() { 1 5
vector<int> x{1};
vector<int> y{2};
pass_by_value(x);
pass_by_reference(y);
cout << x[0] << " " << y[0] << '\n';
return 0;
}

60
 Programming in C++ 61

Recursion
int fib(int n) { Output
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); 610
}
int main() {
cout << fib(15) << '\n';
return 0;
}
 Programming in C++ 62

Lambda expression
An unnamed function object
Can be declared inside a function, or even inside a lambda expression (nested
lambdas)
Other than behave like a normal function (takes parameters), it can also
capture variables
Syntax: [ captures ] ( parameters ) { body }
Capture list (see cppreference for more details):
● =: pass by value
● &: pass by reference
 Programming in C++ 63

Lambda expression
auto sum = [](int a, int b) { return a + b; }; Output
cout << sum(1, 2) << '\n';
auto generic_sum = [](auto a, auto b) { return a + b; }; 3
cout << generic_sum(1.2, 3.4) << '\n'; 4.6

We can store it to a variable and use it like a normal function

We can also define generic lambdas (since C++14), which work like templates
Be careful when you want to capture a large array by value, it will copy the
whole contents of the array, which takes a lot of time
In most cases, you can just write something like auto f = [&](...) { ...
}; to capture all variables by reference
 Programming in C++ 64

Recursive lambda
Lambdas are unnamed function objects, so there is no name for us to call itself
recursively
Is it possible to recursively call it?
Two workarounds:
● Declare a variable by using function first
● Pass itself as a parameter
 Programming in C++ 65

Recursive lambda - use function

function<int(int)> fib; Output
fib = [&](int n) {
if (n <= 1) return n; 610
return fib(n - 1) + fib(n - 2);
};
cout << fib(15) << '\n';
 Programming in C++ 66

Recursive lambda - pass itself

auto fib = [](auto&& self, int n) { Output
if (n <= 1) return n;
return self(self, n - 1) + self(self, n - 2); 610
};
cout << fib(fib, 15) << '\n';
 Programming in C++ 67

Template
There are many types of templates in C++
● Class template
● Function template
● Alias template (since C++11)
● Variable template (since C++14)
Compiler will generate a copy for each used type
 Programming in C++ 68

Template
template <typename T> // class template Output
struct Point { T x, y; };
template <typename T> // function template 3 0.3
T sum(T a, T b) { return a + b; }
3 3.14159
template <typename T> // alias template
using P = Point<T>;
template <typename T> // variable template
T pi = T(acos(-1));
int main() {
Point<int> a = {1, 2};
P<double> b = {0.1, 0.2};
cout << sum(a.x, a.y) << ' ' << sum(b.x, b.y) << '\n';
cout << pi<int> << ' ' << pi<double> << '\n';
return 0;
}
 Programming in C++ 69

Template
Usually, you need to specify the the template parameters
● But sometimes you don’t need to specify them for functions and classes if
you provide template arguments
○ int x = max<int>(1, 2) works
○ int x = max(1, 2) also works
○ vector<int> v(10, 0) works
○ vector v(10, 0) also works (since C++17)
A lot of C++ Standard Library functions and classes are templates
In most cases, you don’t have to write your own templates, you just need to
know how to use templates
 Programming in C++ 70

Auto (since C++11)

To get rid of long type names, you may use auto to declare variables
An initial value must be assigned when declaring a variable, and the value is
used to deduce the type of the variable
Examples:
● auto a = 5678ll (deduced type: long long)
● auto b = 3.0 (deduced type: double)
● auto c = ‘a’ (deduced type: char)
● auto f = true (deduced type: bool)
● auto s = “123” (deduced type: const char*)
● auto s = “123”s (deduced type: string)
 Programming in C++ 71

Pair
Defined in header <utility>
A struct template to store two objects

To declare a pair storing two int types:

● pair<int, int> p
● pair p(0, 0) (since C++17)
To access the first / second element:
● [Link] / [Link]
● get<0>(p) / get<1>(p) (since C++11)
 Programming in C++ 72

Tuple (since C++11)

Defined in header <tuple>
A generalization of pair (2 -> N, N should be a fixed number in compile time)

To declare a tuple storing two int types and one double type:
● tuple<int, int, double> p
● tuple p(0, 0, 0.0) (since C++17)
To access the Nth element:
● get<N>(p) (N should be a fixed number in compile time)
 Programming in C++ 73

Pair and tuple

pair<int, int> p = {1, 2}; Output
pair p2(3, 4);
tuple<int, int, double> t; 1 2
tuple t2(1, 2, 3); 1 2 3
cout << [Link] << ' ' << get<1>(p) << '\n'; 0 1
cout << get<0>(t2) << ' ' << get<1>(t2) << ' ' << get<2>(t2) <<
'\n';
cout << (p > p2) << ' ' << (t < t2) << '\n';

Comparison (<, <=, ==, …) works with lexicographical order if all types are
comparable
 Programming in C++ 74

Accessing members of pair and tuple

What if you don’t want to write [Link] / [Link] / get<N>(p) every
time?
Two solutions:
● Tie (since C++11)
● Structured binding declaration (since C++17)
 Programming in C++ 75

Tie
pair p(1, 2); Output
int x, y;
tie(x, y) = p; 1 2
cout << x << ' ' << y << '\n'; 2 2
x = 2; 1 2
cout << x << ' ' << y << '\n';
2 2
cout << [Link] << ' ' << [Link] << '\n';
p = tie(x, y);
cout << [Link] << ' ' << [Link] << '\n';

Changing the values of the tied variables won’t change the member values in
pair, so you need to tie them again and assign it to the pair
 Programming in C++ 76

Structured binding declaration

Binds the specified names to members of a type
Supports 3 types: arrays, tuple-like types, self-defined structures

To get copies (pass by value):

● auto [x, y] = p
To get references (pass by reference):
● auto& [x, y, z] = t
 Programming in C++ 77

Structured binding declaration

array<int, 2> a = {1, 2}; Output
auto [b, c] = a;
b = 2; 2 2
cout << b << ' ' << c << '\n'; 1 2
cout << a[0] << ' ' << a[1] << '\n'; 5 2 3
tuple t(1, 2, 3);
5 2 3
auto& [x, y, z] = t;
x = 5;
cout << x << ' ' << y << ' ' << z << '\n';
cout << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << '\n';
 Programming in C++ 78

Sort
Defined in header <algorithm>
Sorts the elements in the range [first, last) in non-descending order, where
first and last are random access iterators

To sort an array of size n:

● sort(a, a + n)
To sort the whole vector:
● sort([Link](), [Link]())
Time Complexity: O(n log n) in worst case
 Programming in C++ 79

Sort
To sort a int vector in reverse order:
● sort([Link](), [Link](), greater<int>())
● sort([Link](), [Link](), greater<>()) (since C++14)
● sort([Link](), [Link](), greater{}) (since C++14)
● sort([Link](), [Link]())
● sort([Link](), [Link]()) followed by reverse([Link](),
[Link]())

To sort a int vector by a self-defined comparison function cmp:

● sort([Link](), [Link](), cmp)
 Programming in C++ 80

Reverse
Defined in header <algorithm>
Reverses the order of the elements in the range [first, last)
 Programming in C++ 81

Reverse
vector a = {1, 4, 2, 3, 5}; Output
reverse([Link](), [Link]());
for (auto x : a) cout << x << ' '; 5 3 2 4 1
cout << '\n';
 Programming in C++ 82

Comparison function
The comparison function should take two parameters a and b and return a
boolean value indicating whether a < b
How to write it?
Two main ways:
● A normal function
● A lambda expression (since C++11)
 Programming in C++ 83

Comparison function - normal function

bool cmp(int a, int b) { return a > b; } Output

vector<int> a = {1, 4, 2, 3, 5}; 5 4 3 2 1

sort([Link](), [Link](), cmp);
for (auto x : a) cout << x << ' ';
cout << '\n';
 Programming in C++ 84

Comparison function - lambda expression

vector<int> a = {1, 4, 2, 3, 5}; Output
sort([Link](), [Link](), [](int a, int b) { return a > b; });
for (auto x : a) cout << x << ' '; 5 4 3 2 1
cout << '\n';
 Programming in C++ 85

Application - tree traversal

Please read the problem 01038 - Preorder Tree Traversal
 Programming in C++ 86

Application - tree traversal

vector<vector<int>> edge; // adjacency list to store the connected Output
nodes for each node
vector<int> ans;

void dfs(int u, int par) {

ans.emplace_back(u);
for (auto v : edge[u])
if (v != par) dfs(v, u);
}
 Programming in C++ 87

Binary search functions

Defined in header <algorithm>
Uses binary search algorithm

lower_bound(): Returns an iterator pointing to the first element in the range

[first, last) that is not less than value, or last if no such element is found
upper_bound(): Returns an iterator pointing to the first element in the range
[first, last) that is greater than value, or last if no such element is found
binary_search(): Checks if an element is equivalent to value appears
within the range [first, last)
 Programming in C++ 88

Binary search functions

The range must be sorted in ascending order
● If you want to perform binary search in a range sorted in descending
order, you need to write the comparison function, or you can reverse the
range first
To achieve O(log n) time complexity, first and last should be random access
iterators
 Programming in C++ 89

Binary search functions

vector a = {1, 2, 2, 4, 5}; Output
cout << lower_bound([Link](), [Link](), 2) - [Link]() << '\n';
cout << lower_bound([Link](), [Link](), 3) - [Link]() << '\n'; 1
cout << *lower_bound([Link](), [Link](), 2) << '\n'; 3
cout << *lower_bound([Link](), [Link](), 3) << '\n'; 2
cout << upper_bound([Link](), [Link](), 2) - [Link]() << '\n'; 4
cout << upper_bound([Link](), [Link](), 3) - [Link]() << '\n'; 3
cout << *upper_bound([Link](), [Link](), 2) << '\n'; 3
cout << *upper_bound([Link](), [Link](), 3) << '\n'; 4
cout << binary_search([Link](), [Link](), 2) << '\n'; 4
cout << binary_search([Link](), [Link](), 3) << '\n'; 1
0
 Programming in C++ 90

Unique
Defined in header <algorithm>
Eliminates all except the first element from every consecutive group of
equivalent elements from the range [first, last) and returns a past-the-end
iterator for the new logical end of the range
Usually followed by calling erase() which clears the unused range at the end
 Programming in C++ 91

Unique
vector a = {1, 2, 2, 4, 2}; Output
auto it = unique([Link](), [Link]());
cout << it - [Link]() << '\n'; 4
cout << [Link]() << '\n'; 5
for (auto x : a) cout << x << ' '; 1 2 4 2 2
cout << '\n';
4
[Link](it, [Link]());
1 2 4 2
cout << [Link]() << '\n';
for (auto x : a) cout << x << ' ';
cout << '\n';
 Programming in C++ 92

Discretization
By using the above algorithms, we can do discretization very easily:
● Make a copy of the original array
● Sort it, then all elements of the same values will be in continuous ranges
● Call unique() to get an array containing distinct elements
● Use lower_bound() to find the rank of each element in the original array
(which is the index of the new array + 1)

Time complexity: O(n log n)

 Programming in C++ 93

Discretization
vector a = {748934, 23, 3232, 1, 328490, 2342, 123, 1, 2342, 123, Output
3232, 1};
vector b = a; 7 2 5 1 6 4 3 1 4 3 5
sort([Link](), [Link]()); 1
[Link](unique([Link](), [Link]()), [Link]());
for (auto& x : a) x = lower_bound([Link](), [Link](), x) - [Link]()
+ 1;
for (auto x : a) cout << x << ' ';
cout << '\n';
 Programming in C++ 94

Application - discretization
Please read the problem S152 - Apple Garden
 Programming in C++ 95

Deque
Defined in header <deque>
A double-ended queue with random access

To push an element to the front: q.push_front(x) / q.emplace_front(x)

To push an element to the end: q.push_back(x) / q.emplace_back(x)
To pop an element at the front: q.pop_front()
To pop an element at the end: q.pop_back()
To access the first element: [Link]()
To access the last element: [Link]()
To access the ith element (0 based): q[i] or [Link](i)
 Programming in C++ 96

Deque
deque q{4, 5, 6}; Output
q.emplace_front(3);
q.emplace_back(7); 5
cout << q[2] << '\n'; 6
q.pop_back(); 4
cout << [Link]() << '\n';
4 5 6
q.pop_front();
cout << [Link]() << '\n';
for (auto x : q) cout << x << ' ';
cout << '\n';
 Programming in C++ 97

Deque
It seems that deque is stronger than vector, why we use vector?
The answer is the memory usage:
● deque: n + c1
● vector: 2n + c2
● c1 > c2
The internal storage of deque are not contiguous
Be careful of the memory used by many deques of small size
 Programming in C++ 98

Deque
std::vector std::deque
 Programming in C++ 99

Stack
Defined in header <stack>
A container adaptor for a LIFO (last-in, first-out) data structure
Default container: deque
No random access and iterators

push_back() in deque → push() in stack

emplace_back() in deque → emplace() in stack
pop_back() in deque → pop() in stack
back() in deque → top() in stack
 Programming in C++ 100

Stack
stack<int> st; Output
[Link](1);
[Link](2); 2
cout << [Link]() << '\n'; 1
[Link]();
cout << [Link]() << '\n';
 Programming in C++ 101

Queue
Defined in header <queue>
A container adaptor for a FIFO (first-in, first-out) data structure
Default container: deque
No random access and iterators

push_back() in deque → push() in queue

emplace_back() in deque → emplace() in queue
pop_front() in deque → pop() in queue
front() in deque → front() in queue
 Programming in C++ 102

Queue
queue<int> q; Output
[Link](1);
[Link](2); 1
cout << [Link]() << '\n'; 2
[Link]();
cout << [Link]() << '\n';
 Programming in C++ 103

List
Defined in header <list>
Implemented as a doubly-linked list
No random access

Supports push_front(), push_back(), pop_front(), pop_back(), etc.

To declare an empty int list: list<int> l
To sort the list:
● [Link]() (time complexity: O(n log n))
● sort([Link](), [Link]()) (time complexity: O(n2))
 Programming in C++ 104

List
To insert x before the element pointed by it:
● [Link](it, x)
● Returns an iterator pointing to the element inserted
To remove the element pointed by it:
● [Link](it)
● Returns an iterator pointing to the next element after it
 Programming in C++ 105

List
list l{10, 20};
Output
l.emplace_back(30);
l.emplace_front(0);
cout << [Link]() << ' ' << [Link]() << '\n'; 0 30
auto it = [Link](); 0 20 30
it++;
it = [Link](it); 0 20 25 30
for (auto x : l) cout << x << ' '; 0 20 25 30 40
cout << '\n';
it++; 25
it = [Link](it, 25);
for (auto x : l) cout << x << ' ';
cout << '\n';
[Link]([Link](), 40);
for (auto x : l) cout << x << ' ';
cout << '\n';
cout << *it << '\n';
 Programming in C++ 106

Priority queue
Defined in header <queue>
Implementation of a max heap
Default container: vector

To insert an element: [Link](x) / [Link](x)

To get the largest element: [Link]()
To remove the largest element: [Link]()
Time complexity: O(1) for top() and O(log n) for push() / pop()
 Programming in C++ 107

Priority queue
priority_queue<int> q; Output
[Link](1);
[Link](3); 3
[Link](2); 2
cout << [Link]() << '\n';
[Link]();
cout << [Link]() << '\n';
 Programming in C++ 108

Min heap
If you want a min heap, there are 3 ways:
● Use greater
○ priority_queue<int, vector<int>, greater<int>> q
○ You can use alias template so you can use it in the future easily:
■ template<typename T> using min_heap = priority_queue<T,
vector<T>, greater<T>>
■ min_heap<int> q
● Define a struct that contains operator()
● Define a lambda expression, and use decltype() to get its type
 Programming in C++ 109

Min heap - self-defined struct

struct cmp { Output
bool operator()(int a, int b) { return a > b; }
}; 1
2
priority_queue<int, vector<int>, cmp> q;
[Link](1);
[Link](3);
[Link](2);
cout << [Link]() << '\n';
[Link]();
cout << [Link]() << '\n';
 Programming in C++ 110

Min heap - self-defined lambda expression

auto cmp = [](int a, int b) { return a > b; }; Output

priority_queue<int, vector<int>, decltype(cmp)> q(cmp); 1

[Link](1); 2
[Link](3);
[Link](2);
cout << [Link]() << '\n';
[Link]();
cout << [Link]() << '\n';
 Programming in C++ 111

Set and multiset

Defined in header <set>
Associative containers
set contains a sorted set of unique keys
multiset contains a sorted set of keys
Usually implemented as a red-black tree
Time complexity: O(log n) for each operation
 Programming in C++ 112

Set and multiset

To declare an empty int set: set<int> s
To insert an element x: [Link](x) / [Link](x)
To remove elements that are equal to x: [Link](x)
To remove the element at it: [Link](it)
To find x: [Link](x)
To get the lower bound of x: s.lower_bound(x)
(lower_bound([Link](), [Link](), x) compiles but is O(n))
To get the upper bound of x: s.upper_bound(x)
(upper_bound([Link](), [Link](), x) compiles but is O(n))
 Programming in C++ 113

Set
set s{1, 2, 2, 3, 4}; Output
[Link](5);
cout << [Link]() << '\n'; 5
[Link](2);
3
auto it = s.lower_bound(2);
if (it != [Link]()) cout << *it << '\n'; 5
else cout << "None\n"; 3
it = [Link](5).first;
1 3 4
cout << *it << '\n';
[Link](it);
it = [Link](3);
if (it != [Link]()) cout << *it << '\n';
else cout << "None\n";
for (auto x : s) cout << x << ' ';
cout << '\n';
 Programming in C++ 114

Multiset
multiset s{1, 2, 2, 3, 4}; Output
[Link](5);
cout << [Link]() << '\n'; 6
[Link](2);
3
auto it = s.lower_bound(2);
if (it != [Link]()) cout << *it << '\n'; 5
else cout << "None\n"; 3
it = [Link](5);
1 3 4 5
cout << *it << '\n';
[Link](it);
it = [Link](3);
if (it != [Link]()) cout << *it << '\n';
else cout << "None\n";
for (auto x : s) cout << x << ' ';
cout << '\n';
 Programming in C++ 115

Map and multimap

Defined in header <map>
Associative containers
map contains key-value pairs with unique keys
multimap contains a sorted list of key-value pairs
The value can be accessed by operator[] in map
Time complexity: O(log n) for each operation
 Programming in C++ 116

Map
map<int, int> mp; Output
auto it = [Link](1, 2).first;
cout << it->first << ' ' << it->second << '\n'; 1 2
mp[2] = 0; 2 1
mp[2]++; 1 2
it = [Link](2);
2 1
if (it != [Link]()) cout << it->first << ' ' << it->second << '\n';
else cout << "None\n";
for (auto [key, val] : mp) cout << key << ' ' << val << '\n';

In practice, we use map to store the frequency of a key instead of using

multiset with count()
 Programming in C++ 117

Unordered set and unordered map (since C++11)

Defined in headers <unordered_set> and <unordered_map> respectively
Similar to set and map, but use hash table to implement
operator< is no longer required, but a hash function is required (built-in hash
for int, long long, …)
To define a hash function: similar to defining a comparison function object, but
returns integers instead of a boolean value
Expected time complexity: O(1) for each operation
Worst case time complexity: O(n) for each operation
You can use reserve() to save time if you know the final size
 Programming in C++ 118

Hash function - self-defined class

struct Hash { Output
int operator()(pair<int, int> x) const { return [Link] ^
[Link]; }
};

unordered_map<pair<int, int>, int, Hash> mp;

 Programming in C++ 119

Bitset
Defined in header <bitset>
Represents a fixed-size sequence of n bits
Supports bitwise operations (&, ^, |, …)
Can use operator[] to access values (like a boolean array)

To declare a bitset: bitset<n> s; (n must be known in compile time)

 Programming in C++ 120

Bitset
To set a bit to 1: [Link](x) / s[x] = 1
To set a bit to 0: [Link](x) / s[x] = 0
To flip a bit: [Link](x)
To set all bits to 1: [Link]()
To set all bits to 0: [Link]()
To flip all bits: [Link]()
To count number of bits set to 1: [Link]()
 Programming in C++ 121

Bitset
bitset<10> s(100); Output
cout << s << '\n';
cout << [Link]() << '\n'; 0001100100
[Link](0); 3
cout << s << '\n'; 0001100101
[Link](3);
0001100101
cout << s << '\n';
0001100111
[Link](1);
0001000111
cout << s << '\n';
s[5] = 0;
0000000000
cout << s << '\n';
[Link]();
cout << s << '\n';
 Programming in C++ 122

Application - bitset
Please read the problem M2002 - Corona and Movies
 Programming in C++ 123

Mathematical constants (since C++20)

There are a lot of mathematical constants defined in header <numbers>,
using the std::numbers namespace
● Be careful if you want to using namespace std::numbers, as there
are a lot of names that are commonly used
● A better way is to explicitly state which constant you want to use by
using, for example: using numbers::pi;
 Programming in C++ 124

More in C++ Standard Library

<algorithm>:
● count: count the number of matching elements in a range
● find: find the position of the first matching elements in a range
● fill: fill a value to all elements in a range
● rotate: perform cyclic shift in a range
● is_sorted (since C++11): check is a range is sorted
● partial_sort: partially sort a range
● stable_sort: perform stable sort in a range
● nth_element: find the nth smallest element in a range
● merge and inplace_merge: merge two sorted ranges
 Programming in C++ 125

More in C++ Standard Library

<algorithm>:
● includes, set_difference, set_intersection and set_union: perform set
operations in to sorted ranges
● max and min: get max / min of two elements / among any number of
elements (by using initializer_list, since C++11)
● max_element and min_element: get max / min among a range
● clamp (since C++17): clamp a value between a pair of boundary values
● is_permutation: check if a range is a permutation of another range
● next_permutation and prev_permutation: find the next / previous
permutation of a range
 Programming in C++ 126

More in C++ Standard Library

<numeric>:
● iota: fill a range with continuous increasing numbers
● accumulate: calculate the sum of a range
● inner_product: calculate the sum of the product of two ranges
● adjacent_difference: calculate the differences between adjacent elements
in a range
● partial_sum: calculate the partial sum of a range
● gcd and lcm (since C++17): calculate the gcd (greatest common divisor) /
lcm (least common multiple) of two values
 Programming in C++ 127

More in C++ Standard Library

<numeric>:
● midpoint (since C++20): calculate the midpoint between two numbers
<cmath>:
● lerp (since C++20): calculate the linear interpolation / extrapolation
between two numbers
<complex>:
● complex: a type for handling complex numbers

Explore cppreference for more

 Programming in C++ 128

Non-standard Library
Possibly not existing in some C++ compilers
Usable in g++ (which is used in HKOI Online Judge)
Lack of good (and official) documentation
[Link]
[Link]
ta-structures/OrderStatisticTree.h
[Link]
[Link]
[Link]
 Programming in C++ 129

Conclusion
● C++ standard libraries are useful
● You can save a lot of time during the contest by using them appropriately
● Every problem can be your practice problem
● Try to develop your own coding style base on them
● cppreference is always your good friend
 Programming in C++ 130

Reference
[Link]
Standard Template Library - Wikipedia
C++ Standard Library - Wikipedia
[Link]
[Link]
[Link]
[Link]