Написать пост

Полезные приёмы и хитрости C++

Аватар Никита Прияцелюк

Знать особенности языка, на котором пишешь, всегда полезно. Особенно это касается олимпиадного программирования, где знание хитрого приёма может принести вам победу. Перевели подборку таких приёмов для C++.

Обложка поста Полезные приёмы и хитрости C++

Знать специфику языка, на котором пишешь, всегда полезно. Чем большим количеством особенностей языка владеет разработчик, тем осознанней его код при прочих равных условиях. В материале рассмотрены интересные приёмы и трюки для C++.

Прим. перев. Стоит отметить, что статья в первую очередь будет полезна для олимпиадного программирования. В продакшне некоторые из этих приёмов могут не оценить.

Общие хитрости для C++

1. Макрос watch — один из самых полезных приёмов.

			#define watch(x) cout << (#x) << " is " << (x) << endl
		

При отладке кода watch(переменная) выведет имя переменной и её значение.

2. Другие полезные макросы:

			#define pow2(x) ((x)*(x))
#define mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
		
Смотрите также: Макросы в Си: когда и зачем?

3. Не бойтесь использовать typedef.

			typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
		

Порой что-нибудь вроде set<pair<long long, pair<int, pair<int, int>>>> можно заменить на set<pair<ll, iii>>.

4. В качестве наиболее точного значения числа π можно использовать const double pi = 2 * acos(0.0). Желательно использовать именно такой вариант, если иное значение не указано в условии задания.

5. Никогда не используйте INT_MAX в качестве бесконечности для целых чисел.  В некоторых алгоритмах, например, Флойда–Уоршелла, используются значения вроде ∞+w,  что приведёт к переполнению при использовании INT_MAX.  Вместо этого лучше использовать int oo = 0x3f3f3f3f, поскольку:

  • Это число достаточно большое для задач, связанных с целыми числами;
  • 2 * oo не приведёт к переполнению;
  • Все байты равны, поэтому вы без проблем можете использовать memset(array, oo, sizeof(array));
  • Его довольно легко запомнить.

Однако будьте осторожны:  не используйте 0x3f3f3f3f для long long, так как в таком случае фокус уже не пройдёт, и вы потом потратите кучу времени на поиск ошибки.

6. Для double-бесконечности хорошей идеей будет использовать double inf = 1.0/0.0, поскольку именно так представлено значение бесконечности. У вас не будет переполнения, если вы напишете что-нибудь вроде 2*inf, так как 2*inf равно inf.

7. Существует встроенная функция для нахождения наибольшего общего делителя двух чисел. Это функция __gcd, доступная в заголовочном файле algorithm. Подробней можно почитать здесь.

8. Почти всё о манипуляциях с битами — как установить бит, обнулить бит, быстро умножить/разделить на 2 и т.д. — можно найти здесь и здесь.

9. Не используйте 1 << x, если x может быть больше 31, так как это неопределённое поведение может привести совсем не к тому результату, который вы ожидаете. Сначала приведите 1 к long long: 1ll << x.

10. Вместо if(условие) x++ вы можете написать x += условие. Спецификация C не гарантирует, что true равно 1, но в соревновательном программировании можно предположить, что это сработает.

11. Всегда компилируйте код с флагом -O2. Ваш алгоритм может тратить слишком много времени на работу, однако компилятор сделает свою оптимизационную магию, и вы уложитесь в нужное время.

Прим. перев. В олимпиадном программировании оценивается время работы программы на тестирующем сервере, флаги компиляции на котором задаются огранизаторами олимпиады и обычно уже включают флаг -O2.

12. Стандартные объекты ввода и вывода C++ cin и cout по умолчанию работают быстро. Но их работу замедляет синхронизация с буферами C. Поэтому, если в начале кода написать ios::sync_with_stdio(false), то  cin и cout будут работать так же быстро, как и  printf и scanf, которые вы, однако, больше не сможете использовать.

13. Не стесняйтесь использовать глобальные переменные. Максимальный размер массива, объявленного в функции main, может быть порядка 106, в то время как размер глобального массива может быть порядка 107.

Прим.перев. Ограничение на размер массива, объявленного внутри функции, возникает из-за того, что память, выделяемая операционной системой под стек, ограничена.

Хитрости для GCC

1. Если вы используете GCC, вы можете написать #include <bits/stdc++.h> для импортирования всех стандартных библиотек.

2. GCC имеет встроенные функции для  проведения определённых манипуляций с битами за постоянное время. Например, __builtin_popcount вычисляет общее количество установленных битов заданного целого числа (для long long используйте __builtin_popcountll).

			#define count_ones __builtin_popcountl
// count_ones(9) равно 2
		

Есть множество других встроенных функций, прочитать про которые можно здесь.

Хитрости для C++11

C++11 привнёс некоторые обновления и пару классных вещей. Почти все компиляторы установили эту версию по умолчанию, но если в вашем случае это не так, то используйте флаг -std=c++11 для компиляции.

Прим. перев. В новых версиях GCC по умолчанию включён более новый стандарт C++14, который включает в себя все возможности C++11.

1. В заголовочном файле numeric есть полезная функция std::iota. Она заполняет std::vector (или какой-нибудь контейнер) увеличивающимися значениями, начиная с x. Например, iota(v.begin(), v.end(), x).

2. Вам больше не нужно использовать _pair. Вместо этого вы можете написать ii p = {1, 2} или, например, iii p = {1, {2, 3}}.

Примечание Иногда {a, b} работает не так, как вы ожидаете . Например, этот код выведет то, что должен:

			int main(void) {
	if (make_pair(0,0) < make_pair(1,1))
		printf("It works\n");
}
		

Этот код, с другой стороны, не скомпилируется. Дело в том, что в результате инициализации списка просто инициализируются объекты. Вы не можете использовать их без контекста. Больше подробностей здесь.

			int main(void) {
	if ({0,0} < {1,1})
		printf("It works\n");
}
		

3. Ключевое слово auto позволяет не указывать явно тип переменной, если вы объявляете и инициализируете её в одном месте. Например, вместо int i = 10 вы можете написать auto i = 10, поскольку компилятор знает, что у i тот же тип, что и у 10. Само собой, без инициализации переменной это не сработает.

4. В С++11 появилась такая классная штука, как цикл for, основанный на диапазоне. Например, вам не придётся писать for (int i = 0; i < v.size(); i++), потому что теперь есть for (auto &e : v). За подробностями сюда.

Он очень полезен при обходе std::set или std::map:

			set<int> s = {1, 2, 3};
for (auto e : s) cout << i << " ";
cout << endl;
		

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

5. Вы можете написать функцию, которая будет возвращать два и более значений, с помощью std::tuple и std::tie.

			tuple<int, string> f(void) {
	return {485, "Hello"};
}
 
int main(void) {
	int a;
	string b;
	tie(a, b) = f();
}
		

Уже знали все эти хитрости и думаете, что вы эксперт в С++? Тогда пройдите наш тест и подтвердите это.

C++
38698