Lection.md

C++ и STL

Библиотеки

bits/stdc++.h

IO

ios_base::sync_with_stdio(0); - только если только cin/cout или только scanf/printf.

cin.tie(0); cout.tie(0);

int -> cin >> var/cout << var double -> scanf("%lf", &var) - если без sync_with_stdio string -> fgets(s, len, stdin)/printf("%s", s)

Время (hh:mm):

int h, m;
scanf("%d:%d", &h, &m);
printf("%02d:%02d", h, m);

cout.precision(10) - точность всего числа printf("%.6lf", ll)

std::endl = '\n' << std::flush

cout.width(3); cout << 1; // [  1]
cout << setw(5) << 2; // [    2]

// Таблица
for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
        cout << a[i][j] << " \n"[j == m - 1];
    }
}

while(cin >> x) { // До EOF
    // Обрабатываем x
}

Vector

vector<int> vector1;
vector1.back();

vector1.push_back(); -> vector1.emplace_back();
(push_back = create + std::move, emplace_back = create)

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

for(auto it = vector1.rbegin(); it != vector1.rend(); ++it)

for(auto &x : vector1) // изменения сохраняются
for(auto x : vector1) // измененяется копия
for(const auto &x : vector1)

vector< vector<int> > vector2;
vector<int> vector3[100]; // быстрее

vector1.shrink_to_fit();
int size = (int)vector1.size();

(int)x -> static_cast<int>(x)

vector<int> vector4;
vector4.reserve(199);
while(true) {
    vector4.assign(10, 0);
    vector4.resize(5);
    break;
}

vector<bool> vb; // меньше места
bool ab[10]; // быстрее

Set

set<int> set1 = {19, 10, 16};
set1.insert(x);
set1.emplace(x);
set1.extract() // move-конструктор

if(set1.count(x))
auto it = set1.find(16);
auto item = set1.lower_bound(16);

set1.merge(set2); // O(|set2|)

miltiset<int> multiset1;
multiset1.erase(multiset1.find(x)); // удалить 1 элемент
multiset1.erase(x); // удалить все элементы

Map

map<int, string> map1;
map1.insert({3, "sab"});
map1[5] = "sab";
auto st1 = map1[5];
auto a = map1.at(5);

map<string, int> map1;
vector<string> strings;
for(string s : strings) {
    ~~map1[s] = (int)map1.size();~~ // sequence points!!!!!!
}

Queue/deque

queue<int> queue1; // == deque
queue1.push(1);
queue1.front();
queue1.pop();

deque<int> deque1;
deque1.push_back();
deque1.push_front();
deque1.pop_back();
deque1.pop_front();

Tuple

// pair< int, pair<string, double> > быстрее
tuple<int, string, double> tuple1 = {1, "st", 2.0};
int x = get<0>(tuple1);
double xx = get<2>(tuple1);
int y = get<int>(tuple1);

Priority queue

priority_queue<int> queue2;
queue2.push(1);
queue2.pop();

Bitset

bitset<1000> bitset1;

bitset1.set(10);
bitset1[10] = true;

bitset1.reset(10);
bitset1[10] = false;

if(bitset1.test(10))
if(bitset1[10])

bitset1 <<= 10;

vector<int> weights;
bitset<100> can;
weights.emplace_back(10);
can.set(1);
for(int w: weights) {
    can |= can << w;
}
cout << can.test(6);

Algorithm

reverse(weights.begin(), weights.end());
auto it = find(weights.begin(), weights.end(), 5);
max_element(weights.begin(), weights.end());
lower_bound(weights.begin(), weights.end(), 5); // не для сета!!! O(N log N)

sort(weights.begin(), weights.end());
weights.resize(size_t(
    unique(weights.begin(), weights.end()) - weights.begin()
);

Permutations

while(next_permutation(weights.begin(), weights.end()))
prev_permutation

Misc

x = clamp(x, 4, 5); // x < 4 -> 4; x > 5 -> 5; else: x
iota(weights.begin(), weights.end(), 0); // 0 1 2 3 4 5 6 7...
nth_element(weights.begin(), weights.begin() + weights.size() / 2, weights.end()); // K-ая порядковая статистика

gcd(a, b);
lcm(a, b);
__builtin_popcount(a);

String

string string1;
string s = string1.substr(4, 1);

string str = "11";
int t = stoi(str);
string st = to_string(t);

stringstream stringstream1;
stringstream1 << 13;
string string1;
stringstream1 >> string1;

Rope

Вытаскиваем дерамиду по неявному ключу из недр С++

#include <ext/rope>
using namespace __gnu_cxx

rope<int> x;
auto s = x.substr(10, 4);
x.erase(10, 4);
x.insert(x.mutable_begin(), s);

Policy-based

C++ STL: Policy based data structures

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

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

ordered_set == set + find_by_order + order_of_key

ordered_set ordered_set1;
ordered_set1.insert(1);
ordered_set1.insert(7);
ordered_set1.insert(2);
ordered_set1.insert(3);
ordered_set1.insert(9);
ordered_set1.insert(5);
auto x = *ordered_set1.find_by_order(5); // -> 9
auto y = ordered_set1.order_of_key(7); // -> 4