- Регистрация
- 30 Май 2018
- Сообщения
- 30
- Реакции
- 33
Знать специфику языка, на котором пишешь, всегда полезно. Чем большим количеством особенностей языка владеет разработчик, тем осознанней его код при прочих равных условиях. В данной теме рассмотрены интересные приёмы и трюки для C++.
[!] Стоит отметить, что статья в первую очередь будет полезна для олимпиадного программирования. В продакшне некоторые из этих приёмов могут не оценить. [!]
Общие хитрости для C++
1. Макрос
При отладке кода
2. Другие полезные макросы:
3. Не бойтесь использовать
Порой что-нибудь вроде
4. В качестве наиболее точного значения числа π можно использовать
5. Никогда не используйте
6. Для double-бесконечности хорошей идеей будет использовать
7. Существует встроенная функция для нахождения наибольшего общего делителя двух чисел. Это функция
8. Почти всё о манипуляциях с битами — как установить бит, обнулить бит, быстро умножить/разделить на 2 и т.д. — можно найти
.
9. Не используйте
10. Вместо
11. Всегда компилируйте код с флагом
[!] В олимпиадном программировании оценивается время работы программы на тестирующем сервере, флаги компиляции на котором задаются огранизаторами олимпиады и обычно уже включают флаг -O2. [!]
12. Стандартные объекты ввода и вывода C++
13. Не стесняйтесь использовать глобальные переменные. Максимальный размер массива, объявленного в функции
[!] Ограничение на размер массива, объявленного внутри функции, возникает из-за того, что память, выделяемая операционной системой под стек, ограничена. [!]
[!] Стоит отметить, что статья в первую очередь будет полезна для олимпиадного программирования. В продакшне некоторые из этих приёмов могут не оценить. [!]
Общие хитрости для C++
1. Макрос
watch
— один из самых полезных приёмов.
C++:
#define watch(x) cout << (#x) << " is " << (x) << endl
watch(переменная)
выведет имя переменной и её значение.2. Другие полезные макросы:
C++:
#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))
typedef
.
C++:
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.[!] Ограничение на размер массива, объявленного внутри функции, возникает из-за того, что память, выделяемая операционной системой под стек, ограничена. [!]