Advanced C++ STL

Tony Wong
2017-03-25
C++ Standard Template Library
▸ Algorithms
▹ Sorting
▹ Searching...
▸ Data structures
▹ Dynamically-sized array
▹ Queues...
▸ The implementation is abstracted away from the users
▹ The implementation may differ from compilers, and may change over
time (to improve performances)
Advanced C++ STL 2
What is a template?
▸ Class / function template can be applied to different data types

▸ The type T will be determined at compile time, and for each

different type, a function for that type will be created
triple(1) triple(2.3) triple(true) triple(string{"abc"})
T = int T = double T = bool T = string
result: 3 result: 6.9 result: true result: abcabcabc

Advanced C++ STL 3

What is a template?
▸ Another function template example

Can compile: Compilation error:

Advanced C++ STL 4

What is a template?
▸ Class template example:

Advanced C++ STL 5

Enabling C++11
▸ Some features introduced here
are only available in C++11

Advanced C++ STL 6

<algorithm> sort Best case: 𝑂(𝑛)
Avg/Worst case: 𝑂(𝑛 lg 𝑛)
▸ sort(RndAccIt l, RndAccIt r); where 𝑛 = 𝑟 − 𝑙

▸ sorts the range [l, r) in non-decreasing order

▸ where l and r are Random Access Iterators
▹ Pointers are also random access iterators

Result: 1 2 3 4 4 5 6 7 8 9

Advanced C++ STL 7

<algorithm> sort
Cause all identifiers defined in the std namespace
usable without using std::

Input: 1 4 2 8 5 7
Output: 1 2 4 5 7 8 Advanced C++ STL 8
 <algorithm> sort
▸ To sort user-defined types, you need to "teach" sort how to
compare objects:
▹ Implement operator<
bool operator<(const T& o) const
Method 1: Method 2:

Can be omitted if you are lazy

Sorts in descending order instead

Advanced C++ STL 9
 <algorithm> sort
▸ Alternatively, you can implement function and instructs sort to use it
bool cmp(const T& a, const T& b)
!!! Be careful !!!
The comparison function should return
you can use any name true if and only if object a must be
placed before b.
If your function returns true for both
cmp(x, y) and cmp(y, x) you will
get runtime error TLE because the
algorithm tries to place x before y and
place y before x (contradiction)
This also applies to the variant in the
previous slide

Advanced C++ STL 10

<algorithm> sort
▸ With C++11 you can also write an anonymous function
▸ The return type bool will be inferred by the compiler

Advanced C++ STL 11

<algorithm> stable_sort Worst case: 𝑂(𝑛 lg 𝑛)

▸ stable_sort(RndAccIt l, RndAccIt r)
▸ It only has effect when some data is not part of the sorting key,
e.g. string name
▸ For details, read Sorting and Searching

1.38s 3.08s
Advanced C++ STL 12
<algorithm> nth_element Average case: 𝑂(𝑛)
Worst case: 𝑂(𝑛 lg 𝑛)

▸ nth_element(RndAccIt l, RndAccIt nth, RndAccIt r)

▸ Implements the quick select algorithm: 𝑂(𝑛)
▸ Reorders the range [l, r) such that
▹ The element at nth will contain the same value if [l, r) is sorted
▹ All elements in [l, nth) is less than or equal to that in nth
▹ The element nth less than or equal to those in (nth, r)

Possible output:
5314247689
Advanced C++ STL 13
<algorithm> reverse 𝑂(𝑛)

▸ reverse(BiDirIt l, BiDirIt r)
▸ Obviously, reverses the range [l, r)

▸ Now array a becomes {9, 8, 7, 6, 5, 4, 4, 3, 2, 1}

▸ Result: !dlroW ,olleH

Advanced C++ STL 14
<algorithm> unique 𝑂(𝑛)

▸ FwdIt unique(FwdIt l, FwdIt r)

▸ Removes consecutive equal elements and returns an
ForwardIterator / pointer to the end of the range
▸ Therefore we can get the new length by substracting the
returned pointer by the beginning of the range

Result: abcdcba

▸ To get the distinct elements in a range, sort the range first then
apply unique
Advanced C++ STL 15
<algorithm> binary_search RndAccIt: 𝑂 lg 𝑛
𝑂(𝑛) otherwise

▸ bool binary_search(FwdIt l, FwdIt r, val)

▸ Searches the range [l, r) for the value val
▸ The range [l, r) must be either:
▹ Sorted in non-descending order
▹ Partitioned with respect to val < val == val > val

1
0

1 Incorrect usage
?
Advanced C++ STL 16
<algorithm> lower_bound RndAccIt: 𝑂 lg 𝑛
𝑂(𝑛) otherwise

▸ FwdIt lower_bound(FwdIt l, FwdIt r, val)

▸ Finds the left-most position that val can be inserted into the
range such that the range remains sorted/partitioned
▸ Equivalently, finds the left-most element that is >= val

2
6

10
If every element in the range is < val, r is returned
Advanced C++ STL 17
<algorithm> upper_bound RndAccIt: 𝑂 lg 𝑛
𝑂(𝑛) otherwise

▸ FwdIt upper_bound(FwdIt l, FwdIt r, val)

▸ Finds the right-most position that val can be inserted into the
range such that the range remains sorted/partitioned
▸ Equivalently, finds the left-most element that is > val

5
6
Note: distance is 𝑂(1) for RndAccIt, 𝑂(𝑛) for FwdIt

Advanced C++ STL 18

<algorithm> next_permutation
𝑂(𝑛)
𝑂(1) amortized

▸ bool next_permutation(l, r)
▸ Rearranges the range to form the next lexicographically greater permutation
▸ If the range already contains the greatest permutation (elements in non-
increasing order), false is returned and the range is rearranged to form the
smallest permutation (elements in non-decreasing order)
Result:
12345
Result: 12354
4223:0 12435
....
54312
54321
Result:
2234:1 Advanced C++ STL 19
string
▸ When writing modern C++ programs,
Input:
avoid using arrays, C strings and raw pointers
abc def
creates an empty string
Output:
stops at space, new line or tab s is ""
s is "abc"
▸ string uses 0-based indexing
{} or () both ok
Output:
ghijkl
gxi
Advanced C++ STL 20
string
Append a character
Output: abcde

Concatenate Append

Output: 500000 Output: 500000

Time: 0.67 sec Time: 0.02 sec
Advanced C++ STL 21
string
Input:
▸ Reading a whole line including spaces: abc def
Output:
▸ Get substring from abc def
▹ s.substr(index, length)

▸ Compare strings (lexicographically)

▹ Comparison operators: < <= == >= > !=
▹ s.compare(t) returns negative number when s < t,
0 when s == t, positive number when s > t

▸ Convert C++ string into null-terminated C string:

Advanced C++ STL 22
string
▸ s.begin() returns a RndAccIt of type string::iterator that points to
the first character
▸ s.end() returns a RndAccIt that points to position past the last character
▸ Reverse a string

▸ Reverse a substring

▸ Sort the characters in a string

Advanced C++ STL 23

Exercise - G091BB
▸ Input: a number N
▸ Output: output the next number greater than N that contains the
same number of 1s, 2s, ... 9s
▹ Note: you can change the number of 0s

Input Output
4
115 Case #1: 151
1051 Case #2: 1105
6233 Case #3: 6323
321 Case #4: 1023
Advanced C++ STL 24
 Exercise - G091BB

Next permutation Find position of first

exists non-'0' element
Swap the elements
pointed by
the iterators

Advanced C++ STL 25

Containers
▸ Sequence containers
▹ vector, list, deque
▸ Associative containers
▹ set, map (and multi-variant)
▸ Unordered associative containers
▹ unordered_set, unordered_map
▸ Adapters
▹ queue, stack, priority_queue
▸ Automatic memory management
Advanced C++ STL 26
vector<T>
▸ Dynamically sized array
▸ Always prefer vector to raw arrays
▸ To declare an empty int array

▸ To declare a zero-initialized long long "array" of size 100

▸ To declare an int "array" of size n, with element initialized to 100

Advanced C++ STL 27

vector<T>
▸ Unlike arrays, vector is aware of its size
curly braces
initializer

append an item to the end

𝑂(1) amortized

Advanced C++ STL 28

vector<T>
▸ When there is no capacity left, another memory of size 2 times
the original capacity is allocated. The capacity is now doubled and
the data is moved to the newly allocated memory.
1 4 2 8 push_back(5) 1 4 2 8 1 4 2 8 5 - - -
▸ After 𝑛 push_backs , the elements are moved at most 2𝑛 times

Output:
Initial capacity: 0
1 2 4 4 8 8 8 8 16 16

Advanced C++ STL 29

vector<T>
Traversing using iterators

Traversing using indices

C++11 range-based for loop

Advanced C++ STL 30

vector<T>
▸ Buggy bubble sort

▸ .size() returns an
unsigned integer

▸ Possible fixes:

Advanced C++ STL 31

vector<T> For vector,
.begin() and .end() return
RandomAccessIterators
▸ Sorting and binary search

don't
do this

Advanced C++ STL 32

vector<T>
▸ 2D vector

Advanced C++ STL 33

vector<T>
𝑂(𝑛)

▸ vectors can be compared directly (lexicographical order)

using comparison operators < <= == >= > !=

Advanced C++ STL 34

vector<T>
▸ Performance
▹ array: 3.62 sec
▹ vector: 3.73 sec

Advanced C++ STL 35

pair<T1, T2>
▸ pair is a type template defined in <utility>
▸ A pair<T1, T2> stores two data:
▹ first of type T1
▹ second of type T2
▸ For example, we can use a pair<string, int> to store a
person's height and his/her height

Advanced C++ STL 36

pair<T1, T2>
▸ pairs can be compared directly using comparison operators
< <= == >= > != if both first can second can be compared (have
operator< implemented)
▸ Therefore, a vector<pair<string, int>> can be sorted directly
without writing custom comparison function
Eunha 163
SinB 165
Sowon 173 (sorted by name)
Umji 163
Yerin 167
Yuju 169
Advanced C++ STL 37
list<T>
▸ Implements bidirectional linked list
it = l.insert(it, x) 𝑂(1)
Inserts x before the element pointed by it
Returns an iterator pointing to the element inserted

it = l.erase(it) 𝑂(1)
Remove the element pointed by it
Returns an iterator pointing to the
next element after it

Advanced C++ STL 38

list<T>
▸ Traverse the list in reverse

▸ Sorting a linked list 𝑂(𝑛 lg 𝑛)

▹ You cannot use sort(l.begin(), l.end()) because l.begin()
and l.end() return BiDirIt instead of RndAccIt
▹ Instead, call the specialized version l.sort()

Advanced C++ STL 39

deque<T>
▸ Double-ended Queue
▸ 𝑂(1) push_front / pop_front / push_back / pop_back
▸ 𝑂(1) random access to any element

Advanced C++ STL 40

queue<T>
▸ An adapter of deque with:
▹ push_back(x) becomes push(x)
▹ pop_front() becomes pop()
▹ Random access removed
▹ No iterators, no range-based loop
▹ No curly braces initializer
▸ Note: list can also be used as the underlying container

Advanced C++ STL 41

stack<T>
▸ An adapter of deque with:
▹ push_back(x) becomes push(x)
▹ pop_back() becomes pop()
▹ back() becomes top()
▹ Random access and front() removed
▹ No iterators, no range-based loop
▹ No curly braces initializer
▸ Note: list and vector can also be used as
the underlying container
Advanced C++ STL 42
vector / list / deque comparison
vector list deque
Random Access [] O(1) No O(1)
push / pop front O(n) O(1) O(1)
push / pop back O(1) O(1) O(1)
Iterators RndAccIt BiDirIt RndAccIt
Insert / erase at iterator O(n) O(1) O(n)
Sort O(n lg n) O(n lg n) O(n lg n)
Binary search O(lg n) No O(lg n)
Contiguous memory Yes No No
Advanced C++ STL 43
vector / deque?
▸ The data inside vector is always stored in contiguous memory

vector
0.42s

deque
1.50s

Advanced C++ STL 44

priority_queue<T>
▸ Implementation of a max heap
▸ Included in the <queue> header, but is not related to queue at all
▸ An adapter of vector
▸ push(x): inserts x
▸ top(): returns the greatest element
▸ pop(): removes the greatest element

Advanced C++ STL 45

priority_queue<T>
▸ If you need a min-heap
▹ Method 1: negate all numbers
▹ Method 2: Specify greater<T> as the custom comparison function
▹ Note: defined in <functional> header

▹ Method 3: Implement operator<

with reversed logic (not recommended)
Advanced C++ STL 46
Associative Containers
▸ Elements in an array / a vector are indexed by consecutive non-
negative integers 0, 1, 2, ..., n - 1
▸ Associative containers allow element access based on keys
▸ The type of the key is not necessarily integral, but must
implement strict weak ordering (e.g. operator<)
▸ Element access by key is 𝑂(lg 𝑛)
▸ Associative containers are usually implemented as
Red-Black trees

Advanced C++ STL 47

set<T>
Initialize with unsorted sequence:
▸ set is like an "always sorted" array
𝑂(𝑛 lg 𝑛)

insert / erase
𝑂(lg 𝑛)

Initialize with sorted sequence:

𝑂(𝑛)

Advanced C++ STL 48

 set<T> 𝑂(lg 𝑛)

▸ Two keys x and y are considered equal

if (x < y) = (y < x) = false
▸ st.insert(x) returns
pair<set<T>::iterator, bool>
iterator to the inserted/existing element
whether an new element is actually inserted

erase using key

Advanced C++ STL 49
set<T>
▸ set<T>::iterator is a BidirectionalIterator
▸ We can traverse a set by advancing and backing an iterator

Erase using iterator

Both erase(x) and erase(it) version returns an iterator
pointing to the element after the deleted one
Note: distance(it1, it2) is 𝑂(𝑖𝑡2 − 𝑖𝑡1)
for BidirectionalIterator

Advanced C++ STL 50

set<T> 𝑂(lg 𝑛)

▸ Since set can be considered as an "always sorted" array

(binary search tree actually), we can perform binary search on it
▸ lower_bound and upper_bound can also be used

Input: 3 Output: 3
Input: 6 Output: 7
Input: 12 Output: None

Warning:
lower_bound(st.begin(), st.end(), x)
will compile but is O(n)
Advanced C++ STL 51
map<K, M>
▸ Sometimes it might be more useful to store extra information
other than the key
▸ map<K, M> is similar to set<K> but extra information of type M
is added to each key
If key is not found,
an insertion is performed

If key is found,
the value is updated
Advanced C++ STL 52
map<K, M>
▸ mp.find(k) returns an iterator to the element with key k if it
exists, returns mp.end() instead of key k does not exist
▸ The iterator points to the value type, which is a
pair<const K, M> with first being the key and
second being the mapped value

Changing mapped value

is 𝑂(1) using iterator

Compilation error: Advanced C++ STL 53

Key cannot be changed this way
unordered_set / unordered_map Access
Average: 𝑂(1)
Worst: 𝑂(𝑛)
▸ Hash table implementation
▸ Since elements are unordered, you cannot perform binary search
▸ Also, begin() does not return the smallest element
▸ Handles collisions using separate chaining
▸ By default, when the number of elements (size) reaches the number of
buckets (load factor = 1.0), the capacity increases (~2x) and all elements
are rehashed Output:
1 11 22 23
2 11 23 47
... ...
10 11 46 47
11 23 47 97
Advanced C++ STL 54
unordered_set / unordered_map
▸ In order to use unordered_set/map, classes must have hash
function implemented
▸ Most compilers have already implemented hash functions for
common types such as int, double, string, but not for pair
Hasher class implements operator()

0 1 2 3 4 5 6 7 8 9 10
specify hasher class {4, 2}
{0, 6}
{10, 12}

Advanced C++ STL 55

unordered_set / unordered_map
▸ However, since element access is O(n) worst case, it is possible to
craft test cases that causes most element access to take O(n) time
▸ Also, the hash function of integers is weak

▸ This is especially true if people can look at your code

(e.g. Codeforces) http://codeforces.com/blog/entry/44731
▸ In such cases, use set/map instead of unordered_set/map
▸ Alternatively, implement a stronger hash function that produces
different, unpredicatble hashes for the same number across runs
Advanced C++ STL 56
(unordered_)multiset
▸ For (unordered_)set, there is a multi version which allow
duplicate keys

▸ However, the time complexity of count is additionally

linear to the number of elements having the key

0.48s

Advanced C++ STL 57

(unordered_)multimap
▸ Elements can no longer be accessed using []

▸ Therefore there are very few use cases

Advanced C++ STL 58

Frequency map
▸ Since multiset count could be slow, we can use map to store the
frequency of a key instead of inserting multiple copies of they
same key into a multiset
22233577

Key 2 3 5 7
0.01s Mapped 3 2 1 2
Value

Advanced C++ STL 59

Frequency map
▸ Implement a frequency map that supports:
▹ Insert a number x
▹ Delete a number x
▹ Find the current size
▹ Find the smallest number
▹ Find the largest number
▹ Find the number of 'x's
▹ Find smallest element > x

Advanced C++ STL 60

Frequency map
▸ Let's assume that we never remove 22233577
numbers from the frequency map first Key 2 3 5 7
▸ To insert a number x Mapped 3 2 1 2
Value
insert 3
Note: when you access key x
using [], and if it does not exist,
222333577
an element with key x value 0 Key 2 3 5 7
is automatically inserted
Mapped 3 3 1 2
▸ Number of 'x's : Value

Advanced C++ STL 61

Frequency map
222333577
Key (first) 2 3 5 7
Mapped 3 3 1 2
Value (second)

▸ Find the smallest number freq.begin() freq.end()

freq.rbegin()
▸ Find the largest number

Advanced C++ STL 62

Frequency map
▸ We can use upper_bound to find the smallest number > x
Key (first) 2 3 5 7
Mapped 3 3 1 2
Value (second)

freq.upper_bound(10)
== freq.end()

Advanced C++ STL 63

Frequency map Key (first) 2 3 5 7
▸ To remove a number x Mapped 3 3 1 2
Value (second)
we need to subtract
remove 7
its frequency by 1
Key (first) 2 3 5 7
Mapped 3 3 1 1
▸ Also, we need to remove Value (second)
the key if there is no 'x's left remove 7
Key (first) 2 3 5
Mapped 3 3 1
Value (second)
▸ Faster:
Advanced C++ STL 64
bitset<L>
▸ Creates a container for storing L 0/1 (boolean) values
▸ The length L must be specified at declaration and is fixed

Input:
4
3 4 9 25
Output:
0 3 4 7 9 12 13 16 25 28 29 32 34 37 38 41

Advanced C++ STL 65

bitset<L> 0.89s

0.20s
20.8s

Advanced C++ STL 66

Iterator validity Note: simplified Read the docs for details

▸ Depending on the container, iterators may be invalidated

after an element is inserted/erased
▸ vector
▹ push_back: All iterators are invalidated if a reallocation occurs
▸ deque
▹ Insert / erase: All iterators are invalidated
▸ list
▹ Insert: All other validators remain valid
▹ Erase: Iterators to erased element(s) are invalidated
Advanced C++ STL 67
Iterator validity Note: simplified Read the docs for details

▸ set / map
▹ Insert: All validators remain valid
▹ Erase: Iterators to erased element(s) are invalidated

▸ unordered_set / unordered_map
▹ Insert: All iterators are invalidated if a rehash occurs
▹ Erase: Iterators to erased element(s) are invalidated
Advanced C++ STL 68
Iterator validity
▸ For all containers, iterators pointing to .end() will always
become invalid after a size change

Advanced C++ STL 69

shared_ptr
▸ Problem with raw pointers

Possible output:
0x16969d0
0x16969d0

▸ shared_ptr uses reference counting to manage object lifecycle

Class Constructor arguments

Advanced C++ STL 70
shared_ptr

Advanced C++ STL 71