Advanced C++

for programming contests

This talk

Using the C++ standard library for programming contests

Prerequisite: Basic C++ (if statements, loops, functions)

Goal: Use existing data structures and algorithms to code faster and with less bugs.

Slides are used to show code. There will be a cheatsheet online.

About C++

Grader uses C++14. Check your compiler version with g++ --version

GCC 6: Automatically enabled
GCC 5 or lower: Compile with -std=c++14 or -std=c++11 or -std=c++0x.

Input/Output

Use cin and cout.

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int result = a + b;
    cout << result << '\n';
}

Arrays

Use std::vector

#include <vector>

vector<int> v(4); // v={0,0,0,0} v.size()==4
v.clear();        // v={}        v.size()==0
v.push_back(4);   // v={4},      v.size()==1
v.push_back(6);   // v={4,6},    v.size()==2
v.push_back(3);   // v={4,6,3},  v.size()==3
v.pop_back();     // v={4,6},    v.size()==2

Other lists:

vector<string>
vector<vector<int>>

Read n numbers

int n;
cin >> n;
vector<int> v(n);
for (int i=0; i<n; ++i)
  cin >> v[i];

Sets

Elements are always sorted

"Menge"/"ensemble"

#include <set>

set<int> s;              // s={},     s.size()==0
s.insert(3);             // s={3},    s.size()==1
s.insert(7);             // s={3, 7}, s.size()==2
bool has3 = s.count(3);  // true
bool has4 = s.count(4);  // false
s.erase(s.find(3));      // s={7}, s.size()==1

Associative Arrays

Key-value mapping, always sorted, has auto-insert

#include <map>

map<int, int> m; // m={},           m.size()==0
m[3] = 5;        // m={3: 5},       m.size()==1
m[7] = 2         // m={3: 5, 7: 2}, m.size()==2
int x = m[2];    // x=0, m={2: 0, 3: 6, 7: 2}, m.size()==3

Duplicates in a set

Q: How to store duplicates in a set<string>?

A1: map<string, int>

A2: multiset<string>

Duplicates in a map

Q: How to store duplicates in a map<string, char>?

A1: multimap<string, char>

A2: map<string, multiset<char>>

Container Overview

std::vector<T>
std::map<K,V>, std::set<T>
std::deque<T> (std::stack<T>, std::queue<T>)
std::priority_queue<T>

Do not use: std::list (more than 3× slower in almost any case).

Pairs and Tuples

pair<int, int> p(3, 4); // or {3,4}
// p.first == 3
// p.second == 4
int a, b;
tie(a, b) = p;
p = make_pair(1, 2); // p={1, 2}

tuple<int, int, int> t(1, 2, 3);
// get<0>(t) == 1
// get<1>(t) == 2
// get<2>(t) == 3
int a, b, c;
tie(a, b, c) = t;
t = make_tuple(4, 5, 6); // t={4, 5, 6}

Range-based for loop

vector<int> v{3,1,4,1,5};
for (int i : v)
  cout << i << '\n';
// prints 3 1 4 1 5

map<int, int> m;
m[3] = 5; m[7] = 2; m[1] = 3;
for (auto& p : m)
  cout << p.first << ' ' << p.second << '\n';
// prints 1 3, 3 5, 7 2

Iterators

More general pointers
container.begin(), container.end()
Dereferencing: *it = x
Incrementing: it++ und it += n
Comparison: it == it2

vector<int> v{5,2,3};
for (auto it=v.begin(); it!=v.end(); ++it)
  std::cout << *it << ' ';
// Output: 5 2 3

auto it=v.begin();
*it = 0;   // v={0,2,3}
it += 2;   // it points to 3
*it = 9;   // v={0,2,9}
*--it = 4; // v={0,2,9}

Algorithms

Do useful things with iterators!

Use algorithms

Algorithms work between two iterators: start and end (exclusively).

vector<int> v{5,4,3,2,1};
sort(v.begin(), v.begin()+2); // v={4,5,3,2,1}
sort(v.begin()+2, v.end());   // v={4,5,1,2,3}
sort(v.begin(), v.end());     // v={1,2,3,4,5}

bool func(int lhs, int rhs) {
 return make_pair(lhs&1, lhs >> 1) < make_pair(rhs&1, rhs >> 1);
}
sort(v.begin(), v.end(), func);
// v = ?

Minimum and Maximum

vector<int> v{3,1,4,1,5,9,2,6};
auto it = min_element(v.begin(), v.end());
// it==v.begin()+1, *it==1
it = max_element(v.begin(), v.end());
// it==v.begin()+5, *it==9
sort(v.begin(), v.end(), greater<int>());

Reverse

vector<int> v{3,1,4,1,5,9,2,6};
reverse(v.begin(), v.end());
v=={6,2,9,5,1,4,1,3}

Unique

vector<int> v{3,1,4,1,3,3};
sort(v.begin(), v.end());
// v=={1,1,3,3,3,4}
auto it=unique(v.begin(), v.end());
// v=={1,3,4,1,3,3}, it==v.begin()+3
v.erase(it, v.end());
// v=={1,3,4}

Input/Output revisited

#include <iostream>
int n;
cin >> n;
vector<int> v;
for (int i=0; i<n; ++i) {
  int x;
  cin >> x;
  v.push_back(x);
}
cout << n.size() << '\n';

Do not slow down your programs:

Avoid std::endl!
std::endl='\n'+std::flush and std::flush is slow, especially on our grader.

Use I/O Streams

Use the I/O streams instead of printf and scanf.

No bugs with wrong flags (%d but long long)
Change types easily (int -> long long)
Equally fast

Make it even faster:

// Turn off synchronization between cin/cout and scanf/printf
ios_base::sync_with_stdio(false);

// Disable automatic flush of cout when reading from cin
cin.tie(0);

Terminal Basics

Change directory:: cd <directory>
Show current directory:: pwd
Show files in directory (list):: ls

Compile

g++ -Wall -Wextra -g3 -ggdb3 -D_GLIBCXX_DEBUG x.cc -o x

-Wall -Wextra:: Enable warnings and extra warnings
-g3 -ggdb3:: Write debug informations for gdb.
-D_GLIBCXX_DEBUG:: Bound-checking for containers and iterators

If you have an old gcc, also add -std=c++11 or -std=c++14.

Testing

Input the sample file:

./prog <sample01.in

Input all sample files:

for f in *.in
do
  echo "-- $f --"
  ./prog <$f
done

Short:

for f in *.in; do echo "-- $f --"; ./prog <$f; done

Debugging

In case of a crash use gdb (Gnu DeBugger):

$ gdb prog
(gdb) run <sample01.in
(gdb) bt

printf-Debugging

Print state information:

for (int i=0; i<10; ++i) {
  cerr << "i=" << i << " sum=" << sum << '\n';
  sum += i;
}

Useful macro for debugging:

#define DEB(x) cerr << x << '\n'

for (int i=0; i<10; ++i) {
  DEB("i=" << i << " sum=" << sum);
  sum += i;
}

Before submitting: remove it at one place

#define DEB(x) // cerr << x << '\n'

Error prevention

Use std::assert.

#include <cassert>

void dfs(int n) {
  // n must not be visited
  assert(!graph[n].visited);

  graph[n].visited = true;
  for (int nb : graph[n].adj) {
    if (!graph[nb].visited)
      dfs(nb);
  }
}

Include everything

#include <bits/stdc++.h>

More informations

https://soi.ch/page/training

C++ reference: http://en.cppreference.com