# 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`):
```cpp
int h, m;
scanf("%d:%d", &h, &m);
printf("%02d:%02d", h, m);
```

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

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

```cpp
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

```cpp
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

```cpp
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

```cpp
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

```cpp
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

```cpp
// 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

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

## Bitset

```cpp
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

```cpp
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

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

## Misc

```cpp
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

```cpp
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

[Вытаскиваем дерамиду по неявному ключу из недр С++](http://codeforces.com/blog/entry/10355)

```cpp
#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](http://codeforces.com/blog/entry/11080?locale=ru)

```cpp
#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
```