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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показано 15 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Ввод и вывод ==
=== cin/cout работает медленнее scanf/printf ===
=== cin/cout работает медленнее scanf/printf ===
* [http://codeforces.ru/blog/entry/562 Codeforces — Ввод/вывод в C++]
* [http://codeforces.ru/blog/entry/562 Codeforces — Ввод/вывод в C++]
* [http://codeforces.ru/blog/entry/5217 Codeforces — Снова про ввод/вывод в C++]
* [http://codeforces.ru/blog/entry/5217 Codeforces — Снова про ввод/вывод в C++]
* [http://habrahabr.ru/post/246257/ Habrahabr — Насколько медленны iostreams?]
* [http://habrahabr.ru/post/246257/ Habrahabr — Насколько медленны iostreams?]
=== endl сбрасывает буфер вывода после перевода строки ===
* [http://codeforces.ru/contest/417/submission/6392130 #6392130] vs [http://codeforces.ru/contest/417/submission/10923857 #10923857]
=== Различные компиляторы по-разному округляют вещественные числа с последним дробным разрядом 5 ===
* [http://www.exploringbinary.com/inconsistent-rounding-of-printed-floating-point-numbers/ exploringbinary.com — Inconsistent Rounding of Printed Floating-Point Numbers]
* [http://ideone.com/I8kEuE ideone.com/I8kEuE]
=== Аккуратнее с %lld и %I64d: %lld предпочтительнее ===
* %lld некорректно работает в очень древних Visual C++, а также в GNU C++ (MinGW) под Windows XP (например, на acmp.ru).
* [http://ideone.com/kJ37fO %I64d некорректно работает в GNU C++ под Linux] (то есть почти везде).
* Codeforces: [http://codeforces.com/blog/entry/6727 1], [http://codeforces.com/blog/entry/7912 2]
* [http://discuss.codechef.com/questions/31014/difference-between-i64d-lld CodeChef]
== Вещественные числа ==


=== Вещественные числа нужно использовать с осторожностью; функции <math.h> работают с вещественными числами ===
=== Вещественные числа нужно использовать с осторожностью; функции <math.h> работают с вещественными числами ===
* [http://ideone.com/yBUC04 ideone.com/yBUC04]
* [http://ideone.com/4wnPS0 ideone.com/4wnPS0]
* [http://isocpp.org/wiki/faq/newbie#floating-point-arith isocpp.org &mdash; Why doesn’t my floating-point comparison work?]
* Макконнелл С. Совершенный код / С. Макконнелл. &mdash; М.: Русская редакция, 2010. &mdash; 896 с. &mdash; П. 12.3. &laquo;Числа с плавающей запятой&raquo;, с. 286
* Макконнелл С. Совершенный код / С. Макконнелл. &mdash; М.: Русская редакция, 2010. &mdash; 896 с. &mdash; П. 12.3. &laquo;Числа с плавающей запятой&raquo;, с. 286
* [http://codeforces.ru/blog/entry/17584 Codeforces &mdash; Weird bug with pow?]
* [http://codeforces.ru/blog/entry/17584 Codeforces &mdash; Weird bug with pow?]
* [http://codeforces.ru/blog/entry/6344 Codeforces &mdash; Работа с вещественными числами]
* [http://codeforces.ru/blog/entry/6344 Codeforces &mdash; Работа с вещественными числами]
=== Если не хватает точности double ===
# Меняем все double на long double;
# Меняем все вызовы cstdio (scanf/printf) на вызовы iostream (cin/cout);
# Добавляем l ко всем функциям cmath (sqrt -> sqrtl, atan2 -> atan2l);
# Сдаём под g++.
* [http://codeforces.com/contest/598/submission/14750380 #14750380] vs [http://codeforces.com/contest/598/submission/14750383 #14750383]
* [http://codeforces.com/contest/600/submission/14750408 #14750408] vs [http://codeforces.com/contest/600/submission/14750411 #14750411]
== Особенности функций ==
=== Метод .size() у контейнеров STL возвращает беззнаковое число ===
* [http://codeforces.ru/blog/entry/15782 Codeforces &mdash; Problem with GNU C++ compiler]
* [http://codeforces.ru/contest/385/submission/5789899 #5789899] vs [http://codeforces.ru/contest/385/submission/5798105 #5798105]
=== Метод .count() у multiset/multimap работает за линию от количества подсчитываемых элементов ===
* Актуально для multiset, unordered_multiset, multimap, unordered_multimap
=== В <ctype.h> функции классификации символов (такие как isupper()) могут возвращать не только 0 и 1 ===
* [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>ссылка на удаляемый элемент
|
|
|
|
|}
== Разное ==


=== В <math.h> Visual C++ уже заняты глобальные имена j0, j1, jn, y0, y1, yn ===
=== В <math.h> Visual C++ уже заняты глобальные имена j0, j1, jn, y0, y1, yn ===
* [http://acm.timus.ru/help.aspx?topic=cpp Timus &mdash; Как писать решения на C/C++] (Раздел &laquo;Особенности компилятора по сравнению с другими 32-битными компиляторами C/C++&raquo;)
* [http://acm.timus.ru/help.aspx?topic=cpp Timus &mdash; Как писать решения на C/C++] (Раздел &laquo;Особенности компилятора по сравнению с другими 32-битными компиляторами C/C++&raquo;)


=== Метод .size() у контейнеров STL возвращает беззнаковое число ===
=== Приоритетная очередь работает быстрее, чем сет ===
* [http://codeforces.ru/blog/entry/15782 Codeforces &mdash; Problem with GNU C++ compiler]
* Несмотря на равную асимптотику, приоритетная очередь имеет много меньшую константу, чем сет. Поэтому некоторые задачи можно сдать только с приоритетной очередью.
* [http://codeforces.ru/contest/385/submission/5789899 Codeforces &mdash; Submission #5789899]
 
=== Аккуратнее с map[key] = map.size() ===
* В результате при изначально пустом map значение map[key] может оказаться равным 1. Ситуацию [http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0145r1.pdf вроде как исправили в C++17].
* [http://blog.jayway.com/2015/09/08/undefined-behaviour-in-c-when-adding-to-map/ Unspecified behaviour in C++ when adding to map]
 
== Ссылки ==
* [https://codeforces.com/blog/entry/111217 codeforces.com — Common Mistakes in Competitive Programming and How to Avoid Them]

Текущая версия от 12:31, 22 марта 2023

Ввод и вывод

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()

Ссылки