1. Using C++

The programming language used in this course is C++. If you haven’t used C++ before, it is recommended that you start with an online tutorial, such as this tutorial.

C++ is a large language, and many of its features are not needed in this course. For example, most topics related to memory handling and object-oriented programming are not needed. This chapter discusses some aspects of the C++ language that are relevant for this course.

Input and output

A convenient way to read input in C++ is to use the cin stream. For example, the following code first reads one string and then two integers:

string s;
cin >> s;

int x, y;
cin >> x >> y;

Each variable is assigned the next token in the input stream. Each token is separated by whitespace, such as spaces and newlines. For example, the code above supports all the input formats below.

aybabtu 42 1337

aybabtu
42 1337

aybabtu
  42
    1337

Similarly, the cout stream can be used to print values. For example, the following code prints the values of the variables:

string s = "aybabtu";
int x = 42, y = 1337;

cout << s << "\n";
cout << x << " ";
cout << y << "\n";

The output of the code is:

aybabtu
42 1337

Vectors and sorting

The C++ standard library includes many ready-made data structures and algorithms, such as vector (a resizable array) and sort (an efficient sorting function).

Creating a vector

To use a vector, we need to add the line #include <vector> at the beginning of our code. For example, the following code creates a vector numbers that contains values of type int and adds three elements to it:

vector<int> numbers;

numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);

We can also create a vector by giving its contents directly:

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

The size function tells us how many elements are in the vector:

cout << numbers.size() << "\n"; // 3

We can access and change the contents of a vector in the same way as an array. For example, the following code changes the first element of the vector:

vector<int> numbers = {1, 2, 3};
cout << numbers[0] << "\n"; // 1
numbers[0] = 5;
cout << numbers[0] << "\n"; // 5

Iterating over a vector

We can print the elements of a vector using a for loop like this:

vector<int> numbers = {1, 2, 3};
for (int i = 0; i < numbers.size(); i++) {
    cout << numbers[i] << " ";
}
cout << "\n";

We can also write the same code more simply like this:

vector<int> numbers = {1, 2, 3};
for (auto number : numbers) {
    cout << number << " ";
}
cout << "\n";

Sorting

To use sorting, we need to add the line #include <algorithm> at the beginning of our code. The following code creates a vector and then sorts its contents:

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

sort(numbers.begin(), numbers.end());

Here, begin and end point to the start and end of the vector. We can reverse the order like this:

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

sort(numbers.rbegin(), numbers.rend());

We can use the sort function in other situations too. For example, we can sort a string like this:

string s = "monkey";

sort(s.begin(), s.end());

Pairs

A pair lets us store two pieces of information as one element. For example, the following code creates a vector that contains pairs:

vector<pair<int, string>> pairs;

pairs.push_back({1, "monkey"});
pairs.push_back({2, "banana"});
pairs.push_back({3, "harpsichord"});

In this case, the first part of the pair is an int number, and the second part is a string. We can access the parts of a pair using first and second:

cout << pairs[0].first << "\n"; // 1
cout << pairs[0].second << "\n"; // monkey

When a vector contains pairs, they are sorted first by the first part and then by the second part. The following example shows this:

vector<pair<int,int>> pairs;

pairs.push_back({3, 5});
pairs.push_back({2, 8});
pairs.push_back({3, 2});

sort(pairs.begin(), pairs.end());

cout << pairs[0].first << " " << pairs[0].second << "\n"; // 2 8
cout << pairs[1].first << " " << pairs[1].second << "\n"; // 3 2
cout << pairs[2].first << " " << pairs[2].second << "\n"; // 3 5

More data structures

The C++ standard library includes ready-made implementations of common data structures, just like in other languages. Sets and maps are available, which are based on tree and hash structures.

Set

The C++ set structure is based on a balanced binary search tree, and its operations work in \(O(\log n)\) time. To use a set, we need the line #include <set> at the start of our code.

The following code creates a set, adds the numbers 3, 7, and 5 to it using the insert function, and then gets the number of elements with the size function.

set<int> numbers;

numbers.insert(3);
numbers.insert(7);
numbers.insert(5);

cout << numbers.size() << "\n"; // 3

The count function tells if a certain element is in the set. Because each element can only appear once in a set, the function always returns 0 or 1.

cout << numbers.count(5) << "\n"; // 1
cout << numbers.count(6) << "\n"; // 0

The erase function removes an element from the set:

numbers.insert(4);
cout << numbers.count(4) << "\n"; // 1

numbers.erase(4);
cout << numbers.count(4) << "\n"; // 0

Map

A map is a generalization of an array, containing a set of key-value pairs. The C++ map structure is based on a balanced binary search tree, and its operations work in \(O(\log n)\) time. To use a map, we need the line #include <map> at the start of our code.

For example, the following code creates a map where the keys are strings and the values are integers:

map<string, int> counts;

counts["monkey"] = 1;
counts["banana"] = 2;
counts["harpsichord"] = 3;

cout << counts["banana"] << "\n"; // 2

If we try to access a key that is not in the map, its default value is 0 or an empty value:

map<string, int> counts;

cout << counts["unknown"] << "\n"; // 0

Note that the above code also adds the key to the map with the default value.

Priority queue

A priority queue lets us add elements and then get or remove the smallest or largest element. The C++ priority_queue structure implements a priority queue, where by default we can get and remove the largest element. To use a priority queue, we need the line #include <queue> at the start of our code.

The following code shows how to use a priority queue:

priority_queue<int> numbers;

numbers.push(3);
numbers.push(7);
numbers.push(5);

cout << numbers.top() << "\n"; // 7

numbers.pop();
cout << numbers.top() << "\n"; // 5

Note that in C++, the priority queue by default gives us the largest element, unlike in some other languages.

Iterators

An iterator is a variable that points to an element in a data structure. The begin iterator points to the first element, and the end iterator points to the position after the last element. We can access the element pointed to by an iterator using *, and we can move the iterator with ++ and --.

For example, the following code prints all elements in a set using an iterator. Since a set keeps the elements in order, the elements are printed from smallest to largest.

set<int> numbers = {2, 3, 5, 7};

auto it = numbers.begin();
while (it != numbers.end()) {
    cout << *it << "\n";
    it++;
}

This code prints the smallest and largest element in the set:

set<int> numbers = {2, 3, 5, 7};

auto min_it = numbers.begin();
auto max_it = numbers.end(); max_it--;

cout << *min_it << " " << *max_it << "\n"; // 2 7

The find function gives an iterator to a specific element. The lower_bound function gives an iterator to the smallest element that is at least as large as the given value. The upper_bound function gives an iterator to the smallest element that is greater than the given value. If the element does not exist, these functions give the end iterator.

The following code finds an iterator to the element 5:

auto it = numbers.find(5);

if (it == numbers.end()) {
    // element not found
}

The following code prints the smallest element that is at least 5, and the smallest element that is greater than 5:

set<int> numbers = {2, 3, 5, 7};

cout << *numbers.lower_bound(5) << "\n"; // 5
cout << *numbers.upper_bound(5) << "\n"; // 7

Repeated elements in a set

We cannot add the same element more than once to a set:

set<int> numbers;

numbers.insert(5);
numbers.insert(5);
numbers.insert(5);

cout << numbers.count(5) << "\n"; // 1

However, this is possible with a multiset, which is like a set but allows repeated elements:

multiset<int> numbers;

numbers.insert(5);
numbers.insert(5);
numbers.insert(5);

cout << numbers.count(5) << "\n"; // 3

Note that in a multiset, the count function takes \(O(\log n + k)\) time, where \(k\) is the number of repeated elements.

The erase function removes all occurrences of an element from the multiset:

multiset<int> numbers;

numbers.insert(5);
numbers.insert(5);
numbers.insert(5);

cout << numbers.count(5) << "\n"; // 3

numbers.erase(5);
cout << numbers.count(5) << "\n"; // 0

However, we can remove a single occurrence like this:

multiset<int> numbers;

numbers.insert(5);
numbers.insert(5);
numbers.insert(5);

cout << numbers.count(5) << "\n"; // 3

numbers.erase(numbers.find(5));
cout << numbers.count(5) << "\n"; // 2

In this case, we give the iterator to the element you want to remove.

Pairs in a set

Sometimes it is useful to create a set where the elements are pairs. For example, the following code does this:

set<pair<int, int>> pairs;

pairs.insert({3, 5});
pairs.insert({6, 1});
pairs.insert({3, 4});

The pairs are ordered in the set, first by the first member and then by the second member:

auto it = pairs.lower_bound({4, 2});
cout << it->first << " " << it->second << "\n"; // 6 1

Indexed set

When using the g++ compiler, we can also create a special data structure called an indexed set, which is not part of the standard library:

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

The resulting data structure is like a set, but it has two useful extra functions that work in \(O(\log n)\) time. The find_by_order function gives an iterator to the element at a certain position in the order. The order_of_key function tells the position in the order of a certain element (or where it would be if it is not in the set).

indexed_set numbers;

numbers.insert(2);
numbers.insert(3);
numbers.insert(7);
numbers.insert(9);

auto it = numbers.find_by_order(2);
cout << *it << "\n"; // 7

cout << numbers.order_of_key(7) << "\n"; // 2
cout << numbers.order_of_key(6) << "\n"; // 2
cout << numbers.order_of_key(8) << "\n"; // 3

Good to know

Copying

An important difference between C++ and many other languages is that in C++, assignment copies the contents of a data structure, while in other languages only a reference is copied. The following code shows this:

vector<int> a, b;

a.push_back(1);
a.push_back(2);
a.push_back(3);

b = a;
b[0] = 5;

cout << a[0] << "\n"; // 1
cout << b[0] << "\n"; // 5

Because assignment copies the contents, changing the first element of vector b does not affect vector a, and the data structures are separate.

Similarly, in the following code, the contents of the vector are copied in the function call, and the original vector in the main code is not modified.

void test(vector<int> v) {
    v[0] = 5;
    cout << v[0] << "\n"; // 5
}

vector<int> v = {1, 2, 3};
cout << v[0] << "\n"; // 1
test(v);
cout << v[0] << "\n"; // 1

In the following code, the function parameter v is a reference (note the &), which means that the contents are not copied. This makes the function call more efficient, but the original vector in the main code is modified.

void test(vector<int> &v) {
    v[0] = 5;
    cout << v[0] << "\n"; // 5
}

vector<int> v = {1, 2, 3};
cout << v[0] << "\n"; // 1
test(v);
cout << v[0] << "\n"; // 5

Runtime checks

C++ doesn’t do many runtime checks that most programming languages do. For example, consider the following code:

vector<int> v(3);
v[3] = 5;

This code doesn’t work correctly because the vector has three elements (with indices 0, 1, 2) but the code writes a value to index 3. The result may be that the code writes a value to a memory location that is not allocated for the vector. This can lead to strange bugs that are difficult to track down.

In general, C++ data structures assume that the programmer knows what they are doing. It is possible to read and write values outside the allocated memory area, access an element from an empty data structure, or use an invalid iterator to access a data structure.