Грабли: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 48: Строка 48:
=== В <ctype.h> функции классификации символов (такие как isupper()) могут возвращать не только 0 и 1 ===
=== В <ctype.h> функции классификации символов (такие как isupper()) могут возвращать не только 0 и 1 ===
* [http://ideone.com/GUKcBa ideone.com/GUKcBa]
* [http://ideone.com/GUKcBa ideone.com/GUKcBa]
=== Следите за инвалидацией итераторов, указателей и ссылок ===
{| class="wikitable"
|+ Что инвалидируется в худшем случае при вызове методов вставки и удаления
|
| insert
| erase
| push_back
| pop_back
| push_front
| pop_front
|-
| vector
| все итераторы (при реаллокации)<br>все указатели<br>все ссылки
| итераторы от места удаления до конца<br>указатели от места удаления до конца<br>ссылки от места удаления до конца
| все итераторы<br>все указатели<br>все ссылки
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
|
|
|-
| deque
| все итераторы (при вставке в начало/конец)
| все итераторы<br>все указатели<br>все ссылки
| все итераторы
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
| все итераторы
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
|-
| list
| (нет инвалидаций)
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
| (нет инвалидаций)
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
| (нет инвалидаций)
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
|-
| set
| (нет инвалидаций)
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
|
|
|
|
|-
| map
| (нет инвалидаций)
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
|
|
|
|
|-
| unordered_set
| все итераторы (при перехешировании)
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
|
|
|
|
|-
| unordered_map
| все итераторы (при перехешировании)
| итератор на удаляемый элемент<br>указатель на удаляемый элемент<br>ссылка на удаляемый элемент
|
|
|
|
|}


== Разное ==
== Разное ==

Версия от 16:48, 10 февраля 2021

Ввод и вывод

cin/cout работает медленнее scanf/printf

endl сбрасывает буфер вывода после перевода строки

Различные компиляторы по-разному округляют вещественные числа с последним дробным разрядом 5

Аккуратнее с %lld и %I64d: %lld предпочтительнее

Вещественные числа

Вещественные числа нужно использовать с осторожностью; функции <math.h> работают с вещественными числами

Если не хватает точности double

  1. Меняем все double на long double;
  2. Меняем все вызовы cstdio (scanf/printf) на вызовы iostream (cin/cout);
  3. Добавляем l ко всем функциям cmath (sqrt -> sqrtl, atan2 -> atan2l);
  4. Сдаём под g++.

Особенности функций

Метод .size() у контейнеров STL возвращает беззнаковое число

Метод .count() у multiset/multimap работает за линию от количества подсчитываемых элементов

  • Актуально для multiset, unordered_multiset, multimap, unordered_multimap

В <ctype.h> функции классификации символов (такие как isupper()) могут возвращать не только 0 и 1

Следите за инвалидацией итераторов, указателей и ссылок

Что инвалидируется в худшем случае при вызове методов вставки и удаления
insert erase push_back pop_back push_front pop_front
vector все итераторы (при реаллокации)
все указатели
все ссылки
итераторы от места удаления до конца
указатели от места удаления до конца
ссылки от места удаления до конца
все итераторы
все указатели
все ссылки
итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
deque все итераторы (при вставке в начало/конец) все итераторы
все указатели
все ссылки
все итераторы итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
все итераторы итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
list (нет инвалидаций) итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
(нет инвалидаций) итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
(нет инвалидаций) итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
set (нет инвалидаций) итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
map (нет инвалидаций) итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
unordered_set все итераторы (при перехешировании) итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент
unordered_map все итераторы (при перехешировании) итератор на удаляемый элемент
указатель на удаляемый элемент
ссылка на удаляемый элемент

Разное

В <math.h> Visual C++ уже заняты глобальные имена j0, j1, jn, y0, y1, yn

Приоритетная очередь работает быстрее, чем сет

  • Несмотря на равную асимптотику, приоритетная очередь имеет много меньшую константу, чем сет. Поэтому некоторые задачи можно сдать только с приоритетной очередью.

Аккуратнее с map[key] = map.size()