C++: новое и хорошо забытое старое

Стандарты

• Исходный стандарт — C++98
• C++11 (он же C++0x)
  • Флаги компиляции --std=gnu++0x, --std=c++0x, --std=c++11
• C++14 (C++1y): --std=c++1y, --std=c++14
• C++17 (C++1z): --std=c++1z, --std=c++17
• C++2a — в процессе

Ускорение потоков

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  return 0;
}
        

Ускорение потоков

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  return 0;
}
        

Сортировка по убыванию

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

• rbegin и rend — обратные итераторы

Выход за границы вектора

vector<int> v(5);  // вектор размера 5
v[5] = 8;  // может произойти что угодно
v.at(5) = 8;  // вылетит исключение
        

Квадратные скобки для словарей

map<string, int> m;
string key = "some key";
m[key]++;  // добавляет ключ, если его не было
m.at(key)++;  // если ключа нет,
              // вылетит исключение
        

Поиск во множестве или словаре

set<int> numbers;
if (numbers.find(1) == numbers.end()) {
  numbers.insert(1);
}
if (numbers.count(1) == 0) {  // просто короче
  numbers.insert(1);
}
        

Множество, упорядоченное по убыванию

#include <functional>
        
set<int, greater<int> > numbers;
        

Алгоритм partition_point — обобщённый двоичный поиск

#include <algorithm>
        
bool IsEven(int x) { return x % 2 == 0; }
        
vector<int>::iterator it = partition_point(
    v.begin(), v.end(), IsEven);

• [v.begin(), it) — чётные числа
• [it, v.end()) — нечётные

Алгоритм partition_point
с auto и лямбдой

#include <algorithm>
        
auto it = partition_point(
    v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

• [v.begin(), it) — чётные числа
• [it, v.end()) — нечётные

Пересечение множеств

#include <algorithm>
        
set<int> a = {6, 3, 9};
set<int> b = {9, 6, 1};
vector<int> res(a.size());
res.erase(
    set_intersection(a.begin(), a.end(),
                     b.begin(), b.end(),
                     res.begin()),
    res.end());

Пересечение множеств с back_inserter

#include <iterator>
        
set<int> a = {6, 3, 9};
set<int> b = {9, 6, 1};
vector<int> res;
set_intersection(a.begin(), a.end(),
                 b.begin(), b.end(),
                 back_inserter(res));

Пересечение множеств с inserter

#include <iterator>
        
set<int> a = {6, 3, 9};
set<int> b = {9, 6, 1};
set<int> res;
set_intersection(a.begin(), a.end(),
                 b.begin(), b.end(),
                 inserter(res, res.end()));

bitset — битовые маски

• #include <bitset>
• bitset<100> m; — битовая маска из 100 бит
• Проверка i-го бита: m[i]
• Изменение i-го бита: m.set(i, false)
• Проверка всех бит: m.all(), m.any(), m.none(), m.count()
• Операции: m >>= 2, m1 & m2, ~m
• Преобразование к строке: m.to_string()

Шаблоны

template <typename T>
T avg(T x, T y) {
  return (x + y) / 2;  // или x + (y - x) / 2
}

int a = avg(8, 20);
double b = avg(5.1, 7.9);

Списки инициализации конструкторов

class Graph {
 public:
  Graph(int vertex_count)
      : adjacency_lists(vertex_count) {
  }
 private:
  vector<vector<int> > adjacency_lists; 
};

Закрывающие угловые скобки без пробела

vector<vector<int>> v;
map<string, pair<double, double>> v;

Целочисленные типы фиксированного размера

• #include <cstdint>
• int64_t: [−2⁶³, 2⁶³), uint64_t: [0, 2⁶⁴)
• int32_t: [−2³¹, 2³¹), uint32_t: [0, 2³²)
• int16_t: [−2¹⁵, 2¹⁵), uint16_t: [0, 2¹⁶)
• int8_t: [−2⁷, 2⁷), uint8_t: [0, 2⁸)
  • Чем он лучше char?

using вместо typedef

using It = vector<string>::const_iterator;
It it = v.begin();

template <typename V>
using SMap = map<string, V>;
SMap<int> m;  // map<string, int>

auto при инициализации переменных

auto it = v.begin();
        
for (auto it = v.rbegin();
     it != v.rend(); ++it) {
  cout << *it << " ";
}

{} для создания объектов

struct Date {
  int year, month, day;
};
        
vector<Date> dates;
dates.push_back({2017, 7, 24});

{} для создания вектора, словаря и пр.

vector<int> numbers = {1, 6, 3};
set<string> words = {"first", "second"};
map<int, string> = {
    {1, "first"},
    {2, "second"},
    {3, "third"}
};

range-based for

vector<string> v = {"first", "second"};
set<int> s = {7, 1, 5};

for (int x : s) { /* ... */ }
for (auto x : s) { /* ... */ }
for (const string& x : v) { /* ... */ }
for (const auto& x : v) { /* ... */ }
for (int x : {1, 2, 3}) { /* ... */ }

Методы emplace_back и emplace

string text;
vector<string> parts;
set<string> parts_set;
        
auto it = find(text.begin(), text.end(), ' ');
parts.emplace_back(text.begin(), it);
parts_set.emplace(text.begin(), it);

Сравнение структур с помощью кортежей

struct Date {
  int year, month, day;
};

bool operator<(const Date& lhs,
               const Date& rhs) {
  return tie(lhs.year, lhs.month, lhs.day) <
      tie(rhs.year, rhs.month, rhs.day);
}

Лямбда-функции

struct Date {
  int year, month, day;
};

vector<Date> dates = {{17, 7, 22}, {17, 8, 2}};
auto it = find_if(dates.begin(), dates.end(),
                  [](const Date& date) {
                    return date.month == 8;
                  });
// Нашли первую дату августа

Лямбда-функции: захват

set<int> good_numbers = ReadGoodNumbers();
vector<int> numbers = {7, 1, 9, 2, 0};
partition(numbers.begin(), numbers.end(),
          [&good_numbers](int x) {
            return good_numbers.count(x) == 1;
          });
partition(numbers.begin(), numbers.end(),
          [&](int x) {
            return good_numbers.count(x) == 1;
          });

unordered-контейнеры

• Множество и словарь на основе хеш-таблиц
• Сложность поиска и вставки — O(1)

#include <unordered_map>
        
unordered_map<string, int> numbers;
numbers["first"] = 1;
numbers["second"] = 2;

unordered-контейнеры для своих типов

bool operator==(const Date& lhs,
                const Date& rhs) {
	return lhs.year == rhs.year &&
        lhs.month == rhs.month &&
        lhs.day == rhs.day;
}

unordered-контейнеры для своих типов

struct DateHasher {
  size_t operator()(const Date& date) const {
    size_t hash = date.year * 13 + date.month;
    return hash * 32 + date.day;
  }
};

unordered_set<Date, DateHasher> dates;

Преобразование строки к числу и наоборот

#include <string>
        
string s = to_string(89);
int x = stoi("89");

• К другим типам конвертируют
  stoll, stoull, stod

Новый enum — enum class

enum class Query : uint8_t {
  Add, Remove, Swap
};

// Query query = Add;
//     — нельзя, надо Query::Add
// uint8_t query = Query::Add;
//     — нельзя, нужен тип Query

Новый enum — enum class

enum class Query : uint8_t {
  Add, Remove, Swap
};

void ProcessQuery(vector<int>& numbers,
                  Query query, int param);
                  
ProcessQuery(numbers, Query::Add, 9);

Значения по умолчанию для полей

struct Date {
  int day;
  int month = 8;
  int year = 2017;
};

Date date = {11};  // 11.8.2017

move: семантика перемещения

#include <utility>

vector<vector<int>> adjacency_lists;
vector<int> adjacent_vertices;
// заполняем adjacent_vertices
adjacency_lists.push_back(
    move(adjacent_vertices));
// в adjacent_vertices теперь,
// скорее всего, пусто

Генерация случайных чисел

#include <random>

mt19937 gen;  // можно с seed

uniform_int_distribution<int> distr(1, 10);
cout << distr(gen) << endl;

Умные указатели: зачем?

struct TreeNode {
  TreeNode* parent;
  TreeNode* left_child;
  TreeNode* right_child;
};

• При создании вершины выделяется память: node.left_child = new Node();
• Освобождение памяти — delete обходом в глубину

Умные указатели

#include <memory>
        
struct TreeNode {
  TreeNode* parent;
  shared_ptr<TreeNode> left_child;
  shared_ptr<TreeNode> right_child;
};
node.left_child = make_shared<Node>();
node.left_child = node.left_child->right_child;
node.left_child->right_child.reset();

Умные указатели

#include <memory>
        
struct TreeNode {
  TreeNode* parent;
  unique_ptr<TreeNode> left_child;
  unique_ptr<TreeNode> right_child;
};
node.left_child.reset(new TreeNode());
node.left_child =
    move(node.left_child->right_child);

Делегирующие конструкторы

class Graph {
 public:
  Graph(int vertex_count)
      : adjacency_lists(vertex_count) {}
  Graph(int vertex_count,
        const vector<Edge>& edges)
      : Graph(vertex_count) {
    // ...
  }
};

Variadic templates

Print(5, "a", false);  // Хотим писать так 
        
void Print() { cout << endl; }

template <typename Arg1, typename... Args>
void Print(const Arg1& arg1,
           const Args&... args) {
  cout << arg1 << " ";
  Print(args...);
}