Это продолжение
части 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