sharpc (sharpc) wrote,
sharpc
sharpc

Теормин по STL для СП, часть 2/2

Это продолжение части 1.


<algorithm>

В STL реализованы некоторые простые и часто используемые обобщенные алгоритмы. Обобщенные они потому, что им обычно без разницы, с каким контейнером они работают, они принимают пару итераторов.

min, max, minmax, max_element, min_element

Минимум, максимум, оба сразу:

cout << min(123, 456) << " " << min('a', 'b') << endl; // 123 a
cout << max(2.5, 2.6) << " " << max('k', 'o') << endl; // 2.6 o
pair<int, int> res = minmax({ 2, 4, 8, 16, 32 });
cout << res.first << ' ' << res.second << endl; // 2 32

Максимум в последовательности (аналогично min_element), возвращает итератор:

vector<int> v{1, 2, 3, 4, 5};
cout << max_element(v.begin(), v.end()) - v.begin() << endl; // индекс 4
cout << *max_element(v.begin(), v.end()) << endl; // значение 5

sort, предикат с tie, stable_sort, is_sorted

Сортировка:

vector<int> v{2342, 1231, 87978, 123, 789};
sort(v.begin(), v.end()); // 123 789 1231 2342 87978

в обратном порядке:

sort(v.rbegin(), v.rend()); // 87978 2342 1231 789 123

с предикатом для сравнения:

vector<int> v{-2, -1, 0, 1, 2, 3};
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
}); // 0 -1 1 -2 2 3

с предикатом для лексикографического сравнения (tie создает кортеж ссылок); пример сортирует буквы сначала по частотности (по убыванию), затем по коду символа (по возрастанию):

string s = "hello, world!";
map<char, int> m;
for (char ch : s) { m[ch] += 1; }
vector<pair<char, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), [](pair<char, int> const& a, pair<char, int> const& b) {
    return tie(-a.second, a.first) < tie(-b.second, b.first);
}); // {{'l', 3}, {'o', 2}, {' ', 1}, {'!', 1}, {',', 1}, {'d', 1}, {'e', 1}, {'h', 1}, {'r', 1}, {'w', 1}}

Стабильная сортировка не меняет исходный порядок равных с точки зрения предиката символов.

vector<pair<char, int>> v(m.rbegin(), m.rend());
stable_sort(v.begin(), v.end(), [](pair<char, int> const& a, pair<char, int> const& b) {
    return -a.second < -b.second;
}); // {{'l', 3}, {'o', 2}, {'w', 1}, {'r', 1}, {'h', 1}, {'e', 1}, {'d', 1}, {',', 1}, {'!', 1}, {' ', 1}}

Проверить, что последовательность уже отсортирована:

vector<int> v{1, 2, 3, 1};
cout << boolalpha << is_sorted(v.begin(), v.end()) << endl; // false
sort(v.begin(), v.end());
cout << boolalpha << is_sorted(v.begin(), v.end()) << endl; // true

sort/iota + next_permutation

Функция next_permutation позволяет перебирать перестановки (возвращая false, если текущая перестановка лексикографически максимальна). В СП, как правило, перебирают перестановки индексов, в этом случае исходная последовательность обычно создается iota. Если же нет, почти всегда следует сначала взять лексикографически минимальную перестановку объектов, использовав sort.

vector<int> v(4);
iota(v.begin(), v.end(), 1);
do {
    cout << v[0] << v[1] << v[2] << v[3] << endl;
} while (next_permutation(v.begin(), v.end()));
// 1234; 1243; 1324; 1342; 1423; 1432; 2134; 2143; 2314; 2341; 2413; 2431;
// 3124; 3142; 3214; 3241; 3412; 3421; 4123; 4132; 4213; 4231; 4312; 4321;

unique/remove/remove_if + .erase

Обобщенные алгоритмы умеют переставлять местами элементы, но не умеют их удалять, за это отвечает сам контейнер. Алгоритм unique ищет не первые повторяющиеся элементы и переставляет их в конец. Чтобы unique давал действительно уникальные элементы, последовательность сначала надо отсортировать. Алгоритмы remove/remove_if переставляют в конец определенное значение или значения, удовлетворяющие предикату. Они возвращают итератор на начало этого конца, который можно использовать для его удаления методом erase контейнера.

vector<int> v = {1, 1, 2, 3, 3, 3, 1, 1, 2, 2};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // 1 2 3
v.erase(remove_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
}), v.end()); // 1 3

reverse

Обратить элементы последовательного контейнера:

string s = "desserts";
reverse(s.begin(), s.end());
cout << s << endl; // stressed

fill, copy, copy_n, <iterator>: back_inserter, istream_iterator

Целый ряд функций предназначен для заполнения контейнеров элементами из какого-нибудь источника. Каждый раз, когда вы используете memset, в мире умирает котенок. Функции back_inserter и inserter создают итератор вставки, который вызывает push_back и insert соответственно у контейнера-аргумента при попытке записи по нему.

vector<int> a(5); // {0, 0, 0, 0, 0}
fill(a.begin() + 1, a.end(), -1); // {0, -1, -1, -1, -1}
copy(a.begin(), a.begin() + 2, a.begin() + 2); // {0, -1, 0, -1, -1}
vector<int> b;
copy_n(a.rbegin(), 3, back_inserter(b)); // {-1, -1, 0}

В целях универсальности STL содержит класс итератора (только для чтения или только для записи) для потоков ввода-вывода. Дефолтный конструктор istream_iterator позволяет дочитать до EOF.

stringstream ss("5\n1 2 3 4 5\n1 1 2 3 5");
int n;
ss >> n;
vector<int> v, w;
copy_n(istream_iterator<int>(ss), n, back_inserter(v)); // v = {1, 2, 3, 4, 5}
copy(istream_iterator<int>(ss), istream_iterator<int>(), back_inserter(w)); // w = {1, 1, 2, 3, 5}
copy(w.begin(), w.end(), ostream_iterator<int>(cout, ", ")); cout << endl; // 1, 1, 2, 3, 5,

most vexing parse

Редко, но может встретиться неприятная неоднозначность (так называемый most vexing parse), когда программист думает, что w это объявление переменной, принимающей в конструктор два объекта, а компилятор, что это прототип функции.

vector<int> w(istream_iterator<int>(ss), istream_iterator<int>());

MSVC выдает варнинг вида

warning C4930: prototyped function not called (was a variable definition intended?)

Убедить компилятор, что это объявление переменной, можно скобками.

stringstream ss("1 2 3 4 5");
vector<int> w((istream_iterator<int>(ss)), istream_iterator<int>());
copy(w.begin(), w.end(), ostream_iterator<int>(cout, "_")); // 1_2_3_4_5_

find, find_if, count, count_if

Алгоритмы find/find_if позволяют найти в последовательности первое значение, равное заданному или удовлетворяющее предикату, а count/count_if посчитать, сколько таких всего.

vector<int> v{0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
cout << find(v.begin(), v.end(), 8) - v.begin() << endl; // позиция 6
cout << *find_if(v.begin(), v.end(), [](int i) { return i > 10; }) << endl; // 13
cout << count(v.begin(), v.end(), 1) << endl; // 2
cout << count_if(v.begin(), v.end(), [](int i) { return i % 2 == 0; }) << endl; // 4

search

Алгоритм search расширяет string::find на произвольные последовательности.

vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6};
auto seq = {3, 5};
cout << search(v.begin(), v.end(), seq.begin(), seq.end()) - v.begin() << endl; // 9

includes, set_union, set_intersection, set_difference, set_symmetric_difference

Теоретико-множественные операции вычисляются над сортированными отрезками (чаще всего в векторах, потому что оверхед ниже).

Включение:

vector<int> v1{2, 8, 16, 32};
vector<int> v2{2, 4, 8};
vector<int> v3{8, 16};
cout << boolalpha << includes(v1.begin(), v1.end(), v2.begin(), v2.end()); // false
cout << boolalpha << includes(v1.begin(), v1.end(), v3.begin(), v3.end()); // true

объединение, пересечение, разность, симметрическая разность (требуют итератор для записи результата):

vector<int> v1{10, 20, 30, 40};
vector<int> v2{40, 50, 60, 70};
vector<int> res0111, res0001, res0100, res0110;

set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0111));
// 10 20 30 40 50 60 70
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0001));
// 40
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0100));
// 10 20 30
set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0110));
// 10 20 30 50 60 70

lower_bound/upper_bound

Целочисленный бинарный поиск ищет в отсортированном по возрастанию отрезке (в векторе за O(logN)) отрезок [begin, end[, содержащий это значение.

vector<int> v{1, 1, 1, 1, 2, 2, 2, 3, 3, 4};
cout << "2 in [" <<
    lower_bound(v.begin(), v.end(), 2) - v.begin() << "; " <<
    upper_bound(v.begin(), v.end(), 2) - v.begin() << "[" << endl; // 2 in [4; 7[

Если хочется вычислять «элементы» на лету по «индексу», можно использовать собственный класс итератора.

struct int_iterator : iterator<random_access_iterator_tag, int> {
    int n;
    function<int(int)> pred;
    int_iterator(int n, function<int(int)> pred) : n(n), pred(pred) { }
    int operator * () const { return pred(n); }
    operator int () const { return n; }
    int_iterator& operator ++ () { return *this += 1; }
    int_iterator& operator += (int rhs) { n += rhs; return *this; }
};
function<int(int)> pred = [](int x) {
    if (x < 100500) { return -1; }
    if (x > 100600) { return 1; }
    return 0;
};
int_iterator it_begin(0, pred), it_end(1000000, pred);
cout << "[" <<
    lower_bound(it_begin, it_end, 0) << ", " <<
    upper_bound(it_begin, it_end, 0) << "[" << endl; // [100500, 100601[

<iterator>: begin(cont), end(cont), size(cont)

Вместо методов контейнеров .begin()/.end()/.size() можно использовать глобальные функции begin(cont)/end(cont)/size(cont), которые поддерживают еще и C-массивы и C-строки.

cout << size("abcde") << endl; // 6 потому что nullchar

<numeric>: accumulate, partial_sum, iota

Сумма отрезка, заданного парой итераторов. Тип возвращаемого значения задается начальным значением суммы (суммируйте vector<int64_t> в 0LL).

vector<int> v{1, 2, 3, 4};
cout << accumulate(v.begin(), v.end(), 0) << endl; // 10

Префиксные суммы:

vector<int> v{1, 2, 3, 4, 5}, res(5);
partial_sum(v.begin(), v.end(), res.begin()); // 1 3 6 10 15

Генерация последовательных значений (префиксным ++):

vector<int> v(5);
iota(v.begin(), v.end(), -2); // -2 -1 0 1 2

<cmath>

Математических функций много, приведено популярное в СП и неочевидное подмножество.

hypot, atan2, pi = atan(1) * 4

L2-расстояние (гипотенуза прямоугольного треугольника), точнее, но медленнее наивного метода:

cout << hypot(4, 3) << endl; // 5

Выражение atan2(y, x) считает угол направления на (x,y) в ]−π, +π], арктангенс y/x, учитывающий знаки и не боящийся деления на 0:

cout << atan2(10, -10) << " radians" << endl; // 2.35619

Пи до сих пор нет в стандарте. Вместо использования компилятороспецифичных макросов или вбивания ручками можно использовать

double const pi = atan(1) * 4; // 3.1415926535897931
cout << setprecision(20) << pi << " " // 3.141592653589793116
    << nexttoward(pi, 3.0) << " "  // 3.1415926535897926719
    << nextafter(pi, 4.0) << endl; // 3.1415926535897935601

round, floor, ceil

Округление к ближайшему целому вниз (антье вниз):

cout << floor(2.7) << " " << floor(-2.5) << endl; // 2 -3

вверх:

cout << ceil(2.7) << " " << ceil(-2.5) << endl; // 3 -2

к ближайшему (полуцелые дальше от 0):

cout << round(2.7) << " " << round(-2.5) << endl; // 3 -3

abs

Абсолютное значение:

cout << abs(-10) << endl; // 10

<complex>

Комплексные числа в СП могут сократить некоторые 2D геометрические вычисления. Например, генерацию смещений координат на квадратной сетке к 4-соседям

complex<int> dir(1, 0);
for (int i = 0; i < 4; ++i) {
    cout << dir << " " << dir.real() << " + " << dir.imag() << "j" << endl;
    // (1,0) 1 + 0j; (0, 1) 0 + 1j; (-1, 0) -1 + 0j; (0, -1) 0 + -1j
    dir *= complex<int>(0, 1);
}

или площадь треугольника.

stringstream ss("1 1\n1 4\n5 1");
double x, y;
ss >> x >> y; complex<double> a(x, y);
ss >> x >> y; complex<double> b(x, y);
ss >> x >> y; complex<double> c(x, y);
complex<double> A = b - a, B = c - a;
double S = abs((conj(A) * B).imag()) / 2.0;
cout << S << endl; // 6

Не забывайте, что в военное время значение синуса может достигать четырех.

cout << sin(1.570796327 - 2.063437069i) << endl; // (4,7.94362e-10)

<limits>: numeric_limits<int>::max()

Для всяких INF-значений вместо прикинутых на глаз чисел вроде 100500 можно использовать максимальные и минимальные значения типа.

cout << numeric_limits<int64_t>::min() << endl; // -9223372036854775808
cout << numeric_limits<int64_t>::max() << endl; //  9223372036854775807

<random>

ГПСЧ редко используется в СП, но иногда рандомизированное решение сложно зачелленджить. По дефолту C++ использует mt19937.

default_random_engine generator;
generator.seed(0);
uniform_real_distribution<double> distribution(0.0, 1.0); // аналогично uniform_int_distribution<int>
double rnd = distribution(generator);
cout << rnd << endl; // 0.592845

<utility>: swap

Обменять объекты местами:

int x = 5, y = 3;
swap(x, y);
cout << x << " " << y << endl; // 3 5

<bitset>

Битовое значение известного размера может быть удобно вывести, используя bitset.

cout << bitset<10>(777) << endl; // 1100001001

<chrono>: std::chrono::high_resolution_clock::now()

Точно замерить время:

auto t0 = chrono::high_resolution_clock::now();
this_thread::sleep_for(1.0s);
auto t1 = chrono::high_resolution_clock::now();
cout << chrono::duration_cast<chrono::milliseconds>(t1 - t0).count() << endl; // 999
cout << chrono::duration<double>(t1 - t0).count() << endl; // 0.999376

<functional>

С появлением в C++11 лямбда-функций стало очень удобно писать каллбаки. Чтобы их сохранять в переменные или принимать в функции, полезно использовать шаблон function.

stringstream ss("6 5\n0 1\n0 2\n1 3\n1 4\n4 5");
int n, m;
ss >> n >> m;
vector<vector<int>> adjlist(n);
for (int i = 0; i < m; ++i) {
    int a, b;
    ss >> a >> b;
    adjlist[a].push_back(b);
    adjlist[b].push_back(a);
}

int time = 0;
function<void(int, int, function<void(int, int)>)> dfs =
    [&adjlist, &time, &dfs](int v, int from, function<void(int, int)> enter) {
        enter(v, time++);
        for (int nn : adjlist[v]) {
            if (nn != from) {
                dfs(nn, v, enter);
            }
        }
        time++;
    };

dfs(0, -1, [](int v, int time) {
    cout << "Entered " << v << " at time " << time << endl;
});
/*
Entered 0 at time 0
Entered 1 at time 1
Entered 3 at time 2
Entered 4 at time 4
Entered 5 at time 5
Entered 2 at time 9
*/

Compiler-specific: __builtin_popcount, __builtin_clz, __builtin_ctz, __gcd, __int128

В СП часто бывают полезны интринсики, считающие одним ассемблерным опкодом число установленных бит в числе (popcount), число нулей в бинарной записи числа слева (clz — count leading zeroes) и справа (ctz — count trailing zeroes). Интринсики компиляторо-специфичны, здесь приведены реализации для MSVC и GCC.

#if defined(_MSC_VER)
#include <intrin.h>
#define popcount __popcnt
#define popcount64 __popcnt64
#elif defined(__GNUC__)
#define popcount __builtin_popcount
#define popcount64 __builtin_popcountll
#endif

#if defined(_MSC_VER)
#include <intrin.h>
int clz(uint32_t x) { unsigned long result = -1; _BitScanReverse(&result, x); return 31 - result; }
int ctz(uint32_t x) { unsigned long result = -1; _BitScanForward(&result, x); return result; }
int clz64(uint64_t x) { unsigned long result = -1; _BitScanReverse64(&result, x); return 63 - result; }
int ctz64(uint64_t x) { unsigned long result = -1; _BitScanForward64(&result, x); return result; }
#elif defined(__GNUC__)
#define clz __builtin_clz
#define ctz __builtin_ctz
#define clz64 __builtin_clzll
#define ctz64 __builtin_ctzll
#endif

uint64_t num = 0x000000F000000000ULL;
cout << "popcount: " << popcount64(num) << endl; // 4
cout << "leading 0s: " <<  clz64(num) << " trailing: " << ctz64(num) << endl; // 24 36

uint32_t num2 = 0x000F0000;
cout << "popcount: " << popcount(num2) << endl; // 4
cout << "leading 0s: " << clz(num2) << " trailing: " << ctz(num2) << endl; // 12 16

В С++17 в <numeric> появился std::gcd, но раньше его не было. В GCC он был деталью реализации std::rotate, поэтому доступен под именем __gcd. В MSVC его можно взять в boost.

#if defined(_MSC_VER)
#include <boost/math/common_factor.hpp>
using boost::math::gcd;
#elif defined(__GNUC__)
#define gcd __gcd
#endif

cout << gcd(2983479376572795LL, 29837483726583645LL) << endl; // 15

В 64-битном GCC существует расширение компилятора __int128, в MSVC его тоже придется брать из boost.

#if defined(_MSC_VER)
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::int128_t int128_t;
#elif defined(__GNUC__)
typedef __int128 int128_t;
#endif

int128_t result = int128_t(2983479376572795LL) * 29837483726583645LL;
cout << int(result % 1000000007) << endl; // 493398412


Tags: #define, #elif, #endif, #if, #include, олимпиады, программирование
Subscribe

  • О всемогуществе CAS

    Шел 2016 год, а Maple и Mathematica все еще не могли посчитать Какие еще столь же простые примеры есть?

  • Шпаргалка

    ∪ ∩ — union, i ntersection; ∨ ∧ — Vel (латинское «или»), And; ∃ ∀ — Exists, for All. Уве, наа! Еще?

  • Хорошие новости всем шрифтолюбам

    В MathJax 2.3 beta (самая популярная библиотека для клиентского рендеринга математических формул) появилась поддержка шрифта Neo-Euler, который…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments

  • О всемогуществе CAS

    Шел 2016 год, а Maple и Mathematica все еще не могли посчитать Какие еще столь же простые примеры есть?

  • Шпаргалка

    ∪ ∩ — union, i ntersection; ∨ ∧ — Vel (латинское «или»), And; ∃ ∀ — Exists, for All. Уве, наа! Еще?

  • Хорошие новости всем шрифтолюбам

    В MathJax 2.3 beta (самая популярная библиотека для клиентского рендеринга математических формул) появилась поддержка шрифта Neo-Euler, который…