Фишки C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

double get_time() {
    return clock() * 1.0 / CLOCKS_PER_SEC;
}

bool cmp(int x, int y) {
    return x % 3 < y % 3; // !!! Обязательно нужно возращаться false при равенстве! Это знак <
}

struct MyComparator {
    bool operator()(int x, int y) const {
        return x > y;
    }
};

int32_t main() {
    cerr << "\nsort, stable sort:\n";
    vector<int> to_sort = {1, 6, 2, 8, 4, 5}, to_sort2 = to_sort;
    sort(to_sort.begin(), to_sort.end());
    stable_sort(to_sort2.begin(), to_sort2.end()); // меньше сравнений (сложные структуры, интерактивки)
    debug(to_sort);
    debug(to_sort2);
    sort(to_sort.rbegin(), to_sort.rend());
    //sort(to_sort.begin(), to_sort.end(), greater<int>()); // поменять на это
    debug(to_sort);
    sort(to_sort.begin(), to_sort.end(), cmp); // написать функцию cmp
    debug(to_sort);
    sort(to_sort.begin(), to_sort.end(), [](int x, int y) {
        return x % 2 > y % 2;
    }); // можно использовать, если надо отсортировать пары одну координату по возрастанию, другую по убыванию, но без перемены знака
    debug(to_sort);
    // иногда надо написать возвращаемый параметр
    // тип:
    // auto lambda_function = [](int x, int y) -> bool { return x < y; };
    function<int(int, int)> mygcd = [&](int x, int y) -> int {
        if (x == 0) {
            return y;
        } else {
            return mygcd(y % x, x);
        }
    }; // рекурсия
    debug(mygcd(24, 30));

    cerr << "\nset with custom comparator:\n";
    set<int, MyComparator> q{1, 2, 3}; // написать компаратор
    debug(q);
    //set<int, cmp> q2{1, 2, 3}; // не работает
    auto lambda_cmp = [](int x, int y) { return x > y; };
    set<int, decltype(lambda_cmp)> q2(lambda_cmp);
    q2.insert(1);
    q2.insert(2);
    q2.insert(3);
    debug(q2);
    /* C++20
    auto lambda_cmp = [](int x, int y) { return x > y; };
    set<int, decltype(lambda_cmp)> q2;
    // или даже так:
    set<int, decltype([](int x, int y) { return x > y; })> q2;
    */

    cerr << "\nmin / max element:\n";
    vector<int> a = {1, 5, 2, 4, 7, 9, 8, 6};
    int min_pos = min_element(a.begin() + 1, a.begin() + 4) - a.begin(); // можно с компаратором
    debug(min_pos);
    int max_pos = max_element(a.begin() + 1, a.begin() + 4) - a.begin(); // можно с компаратором
    debug(max_pos);

    cerr << "\nnth element:\n";
    debug(a);
    nth_element(a.begin(), a.begin() + 3, a.end()); // можно с компаратором
    debug(a);

    cerr << "\nlower / upper bound, binary search:\n";
    sort(a.begin(), a.end());
    debug(a);
    int lb4 = lower_bound(a.begin(), a.end(), 4) - a.begin(); // можно с компаратором
    debug(lb4); // последний строго меньший -> lower - 1
    int ub4 = upper_bound(a.begin(), a.end(), 4) - a.begin(); // можно с компаратором
    debug(ub4); // последний не больший -> upper - 1
    debug(binary_search(a.begin(), a.end(), 3));

    cerr << "\nunique\n";
    vector<int> xs = {5, 1, 4, 1, 6, 1, 100, 4, 7};
    debug(xs);
    vector<int> b = xs;
    sort(b.begin(), b.end());
    debug(b);
    int last_pos = unique(b.begin(), b.end()) - b.begin();
    debug(b);
    debug(last_pos);
    b.resize(last_pos);
    for (int &x : xs) {
        x = lower_bound(b.begin(), b.end(), x) - b.begin();
    }
    debug(xs);

    b.resize(unique(b.begin(), b.end()) - b.begin()); // так короче

    cerr << "\nfill:\n";
    a.assign(10, 1);
    fill(a.begin() + 2, a.begin() + 7, 4);
    debug(a);
    int arr[10];
    fill(arr + 1, arr + 8, 7);
    for (int i = 0; i < 10; i++) {
        cerr << arr[i] << ' ';
    }
    cerr << endl;

    cerr << "\niota:\n";
    vector<int> heights = {6, 100, 1, 7, 12};
    vector<int> inds(heights.size());
    iota(inds.begin(), inds.end(), 0); // это не сокращение, это название греческой буквы йот
    sort(inds.begin(), inds.end(), [&](int i, int j) {
        return heights[i] < heights[j];
    });
    debug(heights);
    debug(inds);

    cerr << "\ncopy:\n";
    vector<int> from = {1, 2, 3, 4, 5, 6, 7};
    vector<int> to = {101, 102, 103, 104, 105, 106};
    copy(from.begin() + 3, from.end(), to.begin() + 2);
    debug(to);
    copy(to.begin(), to.end(), ostream_iterator<int>{cerr, " "});
    cerr << endl;

    cerr << "\nmerge:\n";
    a = {1, 2, 4, 4, 5, 7};
    debug(a);
    b = {1, 3, 5, 6, 8};
    debug(b);
    vector<int> c(a.size() + b.size());
    merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // можно с компаратором
    debug(c);

    c.clear();
    merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    debug(c);

    int n = 1e5;
    a.resize(n);
    b.resize(n);
    iota(a.begin(), a.end(), 0);
    iota(b.begin(), b.end(), 1);
    c.clear();
    double resize_before = get_time();
    vector<int> c1(a.size() + b.size());
    merge(a.begin(), a.end(), b.begin(), b.end(), c1.begin());
    double merge_resize_time = get_time() - resize_before;
    debug(merge_resize_time);
    double back_inserter_before = get_time();
    vector<int> c2;
    merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c2));
    double back_inserter_time = get_time() - back_inserter_before;
    debug(back_inserter_time);

    cerr << "\nreverse, rotate:\n";
    a = {1, 2, 3, 4, 5, 6, 7};
    debug(a);
    reverse(a.begin(), a.end());
    debug(a);
    reverse(a.rbegin(), a.rend()); // что будет?
    debug(a);
    rotate(a.begin(), a.begin() + 3, a.end());
    debug(a);

    cerr << "\nfind, count, find_if, count_if\n";
    a = {1, 7, 2, 8, 7, 2};
    int pos7 = find(a.begin(), a.end(), 7) - a.begin();
    debug(pos7);
    int cnt7 = count(a.begin(), a.end(), 7);
    debug(cnt7);
    int count_even = count_if(a.begin(), a.end(), [](int x) { return x % 2 == 0; });
    debug(count_even); // то же самое можно find_if

    cerr << "\nprev / next permutation:\n";
    a = {1, 3, 2};
    debug(a);
    next_permutation(a.begin(), a.end());
    debug(a);
    prev_permutation(a.begin(), a.end());
    debug(a);
    do {
        debug(a);
    } while (next_permutation(a.begin(), a.end()));

    cerr << "\npartial sum:\n";
    a = {1, 2, 3};
    debug(a);
    vector<int> pref(3);
    partial_sum(a.begin(), a.end(), pref.begin());
    debug(pref);
    pref.assign(4, 0);
    partial_sum(a.begin(), a.end(), pref.begin() + 1);
    debug(pref);

    cerr << "\nstructured binding declaration:\n";
    vector<vector<pair<int, int>>> g(5);
    g[0] = {{1, 100}, {3, 400}, {2, 77}};
    for (auto [u, w] : g[0]) {
        debug(u, w);
    }
    map<int, int> smth = {{1, 7}, {100000, 55}, {44, 3}};
    for (auto [key, value] : smth) {
        debug(key, value);
    }
    vector<array<int, 3>> points = {{1, 1, 0}, {7, 4, 1}, {-1, 8, 2}};
    for (auto [x, y, ind] : points) {
        debug(x, y, ind);
    }

    cerr << "\nstring find and substr:\n";
    string s = "abacabadabacab";
    debug(s);
    debug(s.substr(4, 5));
    debug(s.substr(0, s.find("dab")));
    debug(s.substr(s.find("dab")));

    // valarray
    // https://en.cppreference.com/w/cpp/numeric/valarray
    // https://codeforces.com/contest/1545/submission/122360101

    /*
    cerr << "\n<=> operator and default = operator:\n"; // C++20, codeforces
    struct Point {
        int x, y;
        bool operator==(const Point&) const = default;

        partial_ordering operator<=>(const Point& other) const { // или auto вместо partial_ordering
            if (x != other.x) {
                return x <=> other.x;
            } else {
                return y <=> other.y;
            }
        }
    };
    cout << (Point(1, 2) == Point(1, 2)) << ' ' << (Point(1, 2) == Point(1, 3)) << endl;
    cout << (Point(1, 2) < Point(1, 2)) << ' ' << (Point(1, 2) <= Point(1, 2)) << endl;
    cout << (Point(1, 2) > Point(0, 3)) << ' ' << (Point(1, 2) > Point(1, 4)) << endl;

    cerr << "\nssize:\n";
    vector<int> a = {1, 2, 3};
    for (int i = 0; i < a.size() - 4; i++) { // поменять потом на ssize(a)
        cout << a[i] << endl;
    }

    cerr << "\nstarts / ends with:\n";
    cout << (string("abacaba").starts_with("abac")) << endl; // поменять на caba
    cout << (string("abacaba").ends_with("caba")) << endl; // поменять на abac

    cerr << "\nset contains:\n";
    set<int> s{1, 2, 5};
    cout << s.contains(5) << ' ' << s.contains(4) << endl;

    cerr << "\nstring format:\n";
    int d = 23, m = 10, y = 2021;
    cout << format("{}:{}:{}", y, m, d) << endl; // пока не завезли
    */

    cerr << "\nbit functions:\n";
    debug(31 - __builtin_clz(6));
    debug(__builtin_ctz(6));
    debug(__builtin_popcount(6));
    debug(__builtin_popcountll(6));
    // popcount'у нужны прагмы. test_builtin_popcount.cpp -> codeforces

    // В C++20 теперь есть нормальные функции. нужно явно приводить к unsigned типу; все еще нужны прагмы для popcount
    // has_single_bit -> порверка, что степень двойки
    // bit_ceil -> ближайшая не меньшая степень двойки
    // bit_floor -> ближайшая не большая степень двойки
    // bit_width -> log + 1 (вместо 32 - __builtin_clz)
    // rotl, rotr -> циклический сдвиг битов вправо/влево на нужное количество позиций
    // countl_zero -> __builtin_clz
    // countr_zero -> __builtin_ctz