peltorator

Фишки C++

Oct 23rd, 2021
604
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. double get_time() {
  7.     return clock() * 1.0 / CLOCKS_PER_SEC;
  8. }
  9.  
  10. bool cmp(int x, int y) {
  11.     return x % 3 < y % 3; // !!! Обязательно нужно возращаться false при равенстве! Это знак <
  12. }
  13.  
  14. struct MyComparator {
  15.     bool operator()(int x, int y) const {
  16.         return x > y;
  17.     }
  18. };
  19.  
  20. int32_t main() {
  21.     cerr << "\nsort, stable sort:\n";
  22.     vector<int> to_sort = {1, 6, 2, 8, 4, 5}, to_sort2 = to_sort;
  23.     sort(to_sort.begin(), to_sort.end());
  24.     stable_sort(to_sort2.begin(), to_sort2.end()); // меньше сравнений (сложные структуры, интерактивки)
  25.     debug(to_sort);
  26.     debug(to_sort2);
  27.     sort(to_sort.rbegin(), to_sort.rend());
  28.     //sort(to_sort.begin(), to_sort.end(), greater<int>()); // поменять на это
  29.     debug(to_sort);
  30.     sort(to_sort.begin(), to_sort.end(), cmp); // написать функцию cmp
  31.     debug(to_sort);
  32.     sort(to_sort.begin(), to_sort.end(), [](int x, int y) {
  33.         return x % 2 > y % 2;
  34.     }); // можно использовать, если надо отсортировать пары одну координату по возрастанию, другую по убыванию, но без перемены знака
  35.     debug(to_sort);
  36.     // иногда надо написать возвращаемый параметр
  37.     // тип:
  38.     // auto lambda_function = [](int x, int y) -> bool { return x < y; };
  39.     function<int(int, int)> mygcd = [&](int x, int y) -> int {
  40.         if (x == 0) {
  41.             return y;
  42.         } else {
  43.             return mygcd(y % x, x);
  44.         }
  45.     }; // рекурсия
  46.     debug(mygcd(24, 30));
  47.  
  48.     cerr << "\nset with custom comparator:\n";
  49.     set<int, MyComparator> q{1, 2, 3}; // написать компаратор
  50.     debug(q);
  51.     //set<int, cmp> q2{1, 2, 3}; // не работает
  52.     auto lambda_cmp = [](int x, int y) { return x > y; };
  53.     set<int, decltype(lambda_cmp)> q2(lambda_cmp);
  54.     q2.insert(1);
  55.     q2.insert(2);
  56.     q2.insert(3);
  57.     debug(q2);
  58.     /* C++20
  59.     auto lambda_cmp = [](int x, int y) { return x > y; };
  60.     set<int, decltype(lambda_cmp)> q2;
  61.     // или даже так:
  62.     set<int, decltype([](int x, int y) { return x > y; })> q2;
  63.     */
  64.  
  65.     cerr << "\nmin / max element:\n";
  66.     vector<int> a = {1, 5, 2, 4, 7, 9, 8, 6};
  67.     int min_pos = min_element(a.begin() + 1, a.begin() + 4) - a.begin(); // можно с компаратором
  68.     debug(min_pos);
  69.     int max_pos = max_element(a.begin() + 1, a.begin() + 4) - a.begin(); // можно с компаратором
  70.     debug(max_pos);
  71.  
  72.     cerr << "\nnth element:\n";
  73.     debug(a);
  74.     nth_element(a.begin(), a.begin() + 3, a.end()); // можно с компаратором
  75.     debug(a);
  76.  
  77.     cerr << "\nlower / upper bound, binary search:\n";
  78.     sort(a.begin(), a.end());
  79.     debug(a);
  80.     int lb4 = lower_bound(a.begin(), a.end(), 4) - a.begin(); // можно с компаратором
  81.     debug(lb4); // последний строго меньший -> lower - 1
  82.     int ub4 = upper_bound(a.begin(), a.end(), 4) - a.begin(); // можно с компаратором
  83.     debug(ub4); // последний не больший -> upper - 1
  84.     debug(binary_search(a.begin(), a.end(), 3));
  85.  
  86.     cerr << "\nunique\n";
  87.     vector<int> xs = {5, 1, 4, 1, 6, 1, 100, 4, 7};
  88.     debug(xs);
  89.     vector<int> b = xs;
  90.     sort(b.begin(), b.end());
  91.     debug(b);
  92.     int last_pos = unique(b.begin(), b.end()) - b.begin();
  93.     debug(b);
  94.     debug(last_pos);
  95.     b.resize(last_pos);
  96.     for (int &x : xs) {
  97.         x = lower_bound(b.begin(), b.end(), x) - b.begin();
  98.     }
  99.     debug(xs);
  100.  
  101.     b.resize(unique(b.begin(), b.end()) - b.begin()); // так короче
  102.  
  103.     cerr << "\nfill:\n";
  104.     a.assign(10, 1);
  105.     fill(a.begin() + 2, a.begin() + 7, 4);
  106.     debug(a);
  107.     int arr[10];
  108.     fill(arr + 1, arr + 8, 7);
  109.     for (int i = 0; i < 10; i++) {
  110.         cerr << arr[i] << ' ';
  111.     }
  112.     cerr << endl;
  113.  
  114.     cerr << "\niota:\n";
  115.     vector<int> heights = {6, 100, 1, 7, 12};
  116.     vector<int> inds(heights.size());
  117.     iota(inds.begin(), inds.end(), 0); // это не сокращение, это название греческой буквы йот
  118.     sort(inds.begin(), inds.end(), [&](int i, int j) {
  119.         return heights[i] < heights[j];
  120.     });
  121.     debug(heights);
  122.     debug(inds);
  123.  
  124.     cerr << "\ncopy:\n";
  125.     vector<int> from = {1, 2, 3, 4, 5, 6, 7};
  126.     vector<int> to = {101, 102, 103, 104, 105, 106};
  127.     copy(from.begin() + 3, from.end(), to.begin() + 2);
  128.     debug(to);
  129.     copy(to.begin(), to.end(), ostream_iterator<int>{cerr, " "});
  130.     cerr << endl;
  131.  
  132.     cerr << "\nmerge:\n";
  133.     a = {1, 2, 4, 4, 5, 7};
  134.     debug(a);
  135.     b = {1, 3, 5, 6, 8};
  136.     debug(b);
  137.     vector<int> c(a.size() + b.size());
  138.     merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // можно с компаратором
  139.     debug(c);
  140.  
  141.     c.clear();
  142.     merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
  143.     debug(c);
  144.  
  145.     int n = 1e5;
  146.     a.resize(n);
  147.     b.resize(n);
  148.     iota(a.begin(), a.end(), 0);
  149.     iota(b.begin(), b.end(), 1);
  150.     c.clear();
  151.     double resize_before = get_time();
  152.     vector<int> c1(a.size() + b.size());
  153.     merge(a.begin(), a.end(), b.begin(), b.end(), c1.begin());
  154.     double merge_resize_time = get_time() - resize_before;
  155.     debug(merge_resize_time);
  156.     double back_inserter_before = get_time();
  157.     vector<int> c2;
  158.     merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c2));
  159.     double back_inserter_time = get_time() - back_inserter_before;
  160.     debug(back_inserter_time);
  161.  
  162.     cerr << "\nreverse, rotate:\n";
  163.     a = {1, 2, 3, 4, 5, 6, 7};
  164.     debug(a);
  165.     reverse(a.begin(), a.end());
  166.     debug(a);
  167.     reverse(a.rbegin(), a.rend()); // что будет?
  168.     debug(a);
  169.     rotate(a.begin(), a.begin() + 3, a.end());
  170.     debug(a);
  171.  
  172.     cerr << "\nfind, count, find_if, count_if\n";
  173.     a = {1, 7, 2, 8, 7, 2};
  174.     int pos7 = find(a.begin(), a.end(), 7) - a.begin();
  175.     debug(pos7);
  176.     int cnt7 = count(a.begin(), a.end(), 7);
  177.     debug(cnt7);
  178.     int count_even = count_if(a.begin(), a.end(), [](int x) { return x % 2 == 0; });
  179.     debug(count_even); // то же самое можно find_if
  180.  
  181.     cerr << "\nprev / next permutation:\n";
  182.     a = {1, 3, 2};
  183.     debug(a);
  184.     next_permutation(a.begin(), a.end());
  185.     debug(a);
  186.     prev_permutation(a.begin(), a.end());
  187.     debug(a);
  188.     do {
  189.         debug(a);
  190.     } while (next_permutation(a.begin(), a.end()));
  191.  
  192.     cerr << "\npartial sum:\n";
  193.     a = {1, 2, 3};
  194.     debug(a);
  195.     vector<int> pref(3);
  196.     partial_sum(a.begin(), a.end(), pref.begin());
  197.     debug(pref);
  198.     pref.assign(4, 0);
  199.     partial_sum(a.begin(), a.end(), pref.begin() + 1);
  200.     debug(pref);
  201.  
  202.     cerr << "\nstructured binding declaration:\n";
  203.     vector<vector<pair<int, int>>> g(5);
  204.     g[0] = {{1, 100}, {3, 400}, {2, 77}};
  205.     for (auto [u, w] : g[0]) {
  206.         debug(u, w);
  207.     }
  208.     map<int, int> smth = {{1, 7}, {100000, 55}, {44, 3}};
  209.     for (auto [key, value] : smth) {
  210.         debug(key, value);
  211.     }
  212.     vector<array<int, 3>> points = {{1, 1, 0}, {7, 4, 1}, {-1, 8, 2}};
  213.     for (auto [x, y, ind] : points) {
  214.         debug(x, y, ind);
  215.     }
  216.  
  217.     cerr << "\nstring find and substr:\n";
  218.     string s = "abacabadabacab";
  219.     debug(s);
  220.     debug(s.substr(4, 5));
  221.     debug(s.substr(0, s.find("dab")));
  222.     debug(s.substr(s.find("dab")));
  223.  
  224.     // valarray
  225.     // https://en.cppreference.com/w/cpp/numeric/valarray
  226.     // https://codeforces.com/contest/1545/submission/122360101
  227.  
  228.     /*
  229.     cerr << "\n<=> operator and default = operator:\n"; // C++20, codeforces
  230.     struct Point {
  231.         int x, y;
  232.         bool operator==(const Point&) const = default;
  233.  
  234.         partial_ordering operator<=>(const Point& other) const { // или auto вместо partial_ordering
  235.             if (x != other.x) {
  236.                 return x <=> other.x;
  237.             } else {
  238.                 return y <=> other.y;
  239.             }
  240.         }
  241.     };
  242.     cout << (Point(1, 2) == Point(1, 2)) << ' ' << (Point(1, 2) == Point(1, 3)) << endl;
  243.     cout << (Point(1, 2) < Point(1, 2)) << ' ' << (Point(1, 2) <= Point(1, 2)) << endl;
  244.     cout << (Point(1, 2) > Point(0, 3)) << ' ' << (Point(1, 2) > Point(1, 4)) << endl;
  245.  
  246.     cerr << "\nssize:\n";
  247.     vector<int> a = {1, 2, 3};
  248.     for (int i = 0; i < a.size() - 4; i++) { // поменять потом на ssize(a)
  249.         cout << a[i] << endl;
  250.     }
  251.  
  252.     cerr << "\nstarts / ends with:\n";
  253.     cout << (string("abacaba").starts_with("abac")) << endl; // поменять на caba
  254.     cout << (string("abacaba").ends_with("caba")) << endl; // поменять на abac
  255.  
  256.     cerr << "\nset contains:\n";
  257.     set<int> s{1, 2, 5};
  258.     cout << s.contains(5) << ' ' << s.contains(4) << endl;
  259.  
  260.     cerr << "\nstring format:\n";
  261.     int d = 23, m = 10, y = 2021;
  262.     cout << format("{}:{}:{}", y, m, d) << endl; // пока не завезли
  263.     */
  264.  
  265.     cerr << "\nbit functions:\n";
  266.     debug(31 - __builtin_clz(6));
  267.     debug(__builtin_ctz(6));
  268.     debug(__builtin_popcount(6));
  269.     debug(__builtin_popcountll(6));
  270.     // popcount'у нужны прагмы. test_builtin_popcount.cpp -> codeforces
  271.  
  272.     // В C++20 теперь есть нормальные функции. нужно явно приводить к unsigned типу; все еще нужны прагмы для popcount
  273.     // has_single_bit -> порверка, что степень двойки
  274.     // bit_ceil -> ближайшая не меньшая степень двойки
  275.     // bit_floor -> ближайшая не большая степень двойки
  276.     // bit_width -> log + 1 (вместо 32 - __builtin_clz)
  277.     // rotl, rotr -> циклический сдвиг битов вправо/влево на нужное количество позиций
  278.     // countl_zero -> __builtin_clz
  279.     // countr_zero -> __builtin_ctz
  280.    
  281.  
RAW Paste Data