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

Jul 03, 2018 01:32

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



В 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 res = minmax({ 2, 4, 8, 16, 32 });
cout << res.first << ' ' << res.second << endl; // 2 32

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

vector 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 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 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 m;
for (char ch : s) { m[ch] += 1; }
vector
char, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), [](pair const& a, pair 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
char, int>> v(m.rbegin(), m.rend());
stable_sort(v.begin(), v.end(), [](pair const& a, pair 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 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 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 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, : back_inserter, istream_iterator
Целый ряд функций предназначен для заполнения контейнеров элементами из какого-нибудь источника. Каждый раз, когда вы используете memset, в мире умирает котенок. Функции back_inserter и inserter создают итератор вставки, который вызывает push_back и insert соответственно у контейнера-аргумента при попытке записи по нему.

vector 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 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 v, w;
copy_n(istream_iterator(ss), n, back_inserter(v)); // v = {1, 2, 3, 4, 5}
copy(istream_iterator(ss), istream_iterator(), back_inserter(w)); // w = {1, 1, 2, 3, 5}
copy(w.begin(), w.end(), ostream_iterator(cout, ", ")); cout << endl; // 1, 1, 2, 3, 5,

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

vector w(istream_iterator(ss), istream_iterator());

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

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

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

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

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

vector 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 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 v1{2, 8, 16, 32};
vector v2{2, 4, 8};
vector 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 v1{10, 20, 30, 40};
vector v2{40, 50, 60, 70};
vector 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 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 : iteratorint> {
    int n;
    function pred;
    int_iterator(int n, function 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 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[

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

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

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

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

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

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

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

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

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

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

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

complex 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(0, 1);
}

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

stringstream ss("1 1\n1 4\n5 1");
double x, y;
ss >> x >> y; complex a(x, y);
ss >> x >> y; complex b(x, y);
ss >> x >> y; complex c(x, y);
complex 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)

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

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

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

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

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

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

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

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

: 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(t1 - t0).count() << endl; // 999
cout << chrono::duration(t1 - t0).count() << endl; // 0.999376

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

stringstream ss("6 5\n0 1\n0 2\n1 3\n1 4\n4 5");
int n, m;
ss >> n >> m;
vectorint>> 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)> dfs =
    [&adjlist, &time, &dfs](int v, int from, function 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
#define popcount __popcnt
#define popcount64 __popcnt64
#elif defined(__GNUC__)
#define popcount __builtin_popcount
#define popcount64 __builtin_popcountll
#endif

#if defined(_MSC_VER)
#include
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 в появился std::gcd, но раньше его не было. В GCC он был деталью реализации std::rotate, поэтому доступен под именем __gcd. В MSVC его можно взять в boost.

#if defined(_MSC_VER)
#include
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
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

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

Previous post Next post
Up
[]