3.4. Дополнительные замечания

3.4.1. Быстрый ввод-вывод

Стандартный ввод/вывод через iostream (т.е. с использованием cin/cout) по умолчанию работает медленно на больших данных. Если вам надо ввести, допустим, 100000 чисел, то с использованием cin такой ввод будет работать очень долго, скорее всего заметно больше секунды, и поэтому на большинстве наших задач вы получите time limit. Аналогично если вам надо выводить много данных. Это связано с двумя проблемами.

Во-первых, медленно работает endl. Поэтому не используйте endl вообще, используйте '\n'.

Примечание

Вывод в cout буферизуется, т.е. данные не сразу попадают на экран или на диск, а сначала собираются в большую строку («буфер»), и только когда их накопится достаточно много, ну или в конце работы программы, попадают на диск или на экран — дело в том, что реальный вывод данных работает медленно, намного быстрее сразу вывести строку из допустим 100000 символов, чем 10000 строк по 10 символов — и буферизация как раз это и делает. Но endl каждый раз сбрасывает буфер, реально выводя данные на экран или на диск, поэтому если вы выводите много чисел через endl, то это будет медленно.

Во-вторых, есть еще проблема синхронизации с stdio (не буду сейчас подробнее писать, что это значит). Чтобы эту проблему побороть, есть три способа:

  • Работать с файлами, а не с клавиатурой/экраном (когда это допустимо). У fstream таких проблем со скоростью работы нет.

  • Использовать для ввода/вывода конструкции в стиле C (scanf и printf из stdio.h), а не из iostream.

  • Написать в самом начале программы две магические строчки (их надо выучить наизусть):

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    

Лично я вам рекомендую использовать первый (работать с файлами) или последний (с магическими строками) вариант.

Еще раз: есть две проблемы: одна с endl, другая с синхронизацией stdio и iostream. Одна решается тем, что вы не используете endl, другая — вот одним из трех описанных выше способов. Вам надо решить обе проблемы, т.е. и не использовать endl, и как-то разобраться с синхронизацией. Типичная ошибка — написать в начале программы этот страшный код с sync_with_stdio, но выводить все равно через endl. Получите time limit exceeded все равно.

3.4.2. Установка стека

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

(То же самое может быть, если вы попробуете объявить очень много переменных — сотни тысяч, а то и больше — в одной функции, без всякой рекурсии, но это надо очень сильно постараться, например, использовать массивы в стиле С, а не C++. Поэтому вы намного чаще с этой проблемой будете сталкиваться именно в рекурсивных решениях.)

В GCC попросить большой размер стека из самой программы невозможно. Поэтому, чтобы ваш код работал на больших данных, надо сделать соответствующие настройки компиляции — в командную строку компилятора добавить параметр типа -Wl,--stack,64000000. Если вы компилируете вручную через командную строку, то указывайте этот параметр. Если компилируете через Code::Blocks, то найдите размер стека в настройках компиляции. На олимпиадах вам надо надеяться на то, что в тестирующей системе тоже будет установлен большой стек (т.е. будет добавлен нужный параметр компиляции); на нормальных олимпиадах жюри это всегда делает и указывает это в памятке в разделе со строками компиляции.

Примечание

Этот раздел относится только к компиляции и запуску программ под Windows. Под macOS используются чуть другию ключи GCC, а под Linux стек настраивается не при компиляции программы, а при запуске. Если ваши решения запускаются под Linux, то нужно отдельно уточнять размер стека. Типичный размер стека по умолчанию — 8 Мб.

А вот в Visual Studio можно установить необходимый размер стека прямо из программы примерно следующей конструкцией:

#pragma comment(linker, "/STACK:64000000")

Число 64000000 в обоих примерах выше — это необходимый вам размер стека в байтах (в примерах 64 миллиона байт, т.е. примерно 64 Мб). Размер стека можете посчитать в уме исходя из вашей программы (умножьте глубину рекурсии на размер памяти, требуемый на один уровень рекурсии — это примерно сколько памяти занимают все переменные на одном уровне, плюс 10-20 байт), а можете и подобрать опытным путем — 32-64 Мб обычно достаточно. Учитывайте еще, конечно, ограничение по памяти.

Довольно часто можно поставить размер стека, равный ограничению по памяти — неиспользуемый стек в программах на C++ обычно не учитывается как потребляемая память.

Примечание

Например, стека размером 8 Мб (как по умолчанию на Linux) на грани хватает на несложную рекурсию глубиной 100'000, а вот на глубину 1'000'000 точно не хватит.

Поэтому если вы пишете на MSVS, то всегда явно устанавливайте размер стека. Если пишете на g++ в code::blocks, то для локального запуска настройте в настройках code::blocks; и надейтесь, что в тестирующей системе жюри это нормально настроит (по-нормальному это должно быть видно в памятке участника). Если пишете на g++ и компилируете из командной строки вручную, то добавляйте нужный параметр и, опять-таки, надейтесь на жюри. Если вдруг жюри не настроило стек на g++, но при этом предоставляет возможность отправки под MSVS, то добавьте магическую MSVS-строчку и отправляйте под MSVS, даже если вы пишете под g++.

3.4.3. Порядок вычислений

Язык C++, в отличие от питона, не гарантирует никакого порядка вычислений внутри выражений. Не путайте с приоритетами операций — выражение 2 + 2 * 2 + 20 всегда будет вычислено в 26. Однако в следующей программе есть проблема:

#include <iostream>

using namespace std;

int a = 0;

int next_a() {
    a++;
    return a;
}

int main() {
    cout << 10 * a + next_a() << endl;
    return 0;
}

Несмотря на то, что у меня на компьютере эта программа выводит 1, такое поведение не гарантируется. В тестирующей системе легко может быть выведено 11, если компилятор решит, что быстрее будет сначала вызвать next_a(), а потом уже считать значение из a. Это зависит от множества факторов и невозможно предугадать, что будет на самом деле. Например, если я заменю 10 * a + next_a() на a + next_a(), то мой компилятор действительно начнёт сначала вычислять next_a() и у меня на компьютере будет выведено 2, а не 1.

Аналогичная проблема может возникнуть при выводе на экран или вызове функций, в том числе стандартных:

#include <iostream>

using namespace std;

int a = 0;

int next_a() {
    a++;
    return a;
}

int subtract(int x, int y) {
    return x - y;
}

int main() {
    cout << next_a() << next_a() << endl;  // Может вывести как 12, так и 21.
    cout << subtract(next_a(), next_a()) << endl;  // Может вывести как 3-4 == -1, так 4-3 == 1.
    cout << subtract(next_a(), next_a()) << ' ' << next_a() << endl;  // Есть шесть вариантов выполнения.
    return 0;
}

В последней строчке с выводом компилятор может вызывать next_a() в любом порядке. Например, слева направо (тогда получим -1 7), справа налево (тогда получим 1 5), так и вообще вперемешку: сначала самый левый, потом самый правый, потом центральный (тогда получим -2 6). У меня на компьютере получается 1 7: сначала вычисляется центральный, потом левый, а потом правый.

Разумеется, точка с запятой полностью отделяет друг от друга команды: если у вас написано foo(); bar();, то всегда сначала вызовется foo(), а потом bar().

Примечание

В стандартах C++11, C++14 есть и более жуткий и сложный пример (в стандарте C++17 его убрали). Например, пусть вы написали v[0] = foo();, а функция foo() внутри себя делает v.push_back(10). Тогда компилятор может сначала запомнить, где в памяти лежит v[0], а потом вызвать foo(). При операции v.push_back(10) массив переедет в другое место в памяти, а потом компилятор запишет результат foo() не в массив, а непонятно куда. Это будет неопределённое поведение, с этого момента программа может вести себя вообще как угодно.

Есть два исключения: логические операторы и инициализация при помощи фигурных скобочек.

Логические операторы вычисляются «лениво» слева-направо, как и в паскале или питоне: в выражении i < v.size() && v[i] == 0 сначала будет проверено условие i < v.size(), и только если оно истинно — программа посмотрит в элемент массива v с номером i. Так гарантируется, что выхода за границу массива не будет.

Похожим образом работает логический оператор «или»: success || foo() сначала проверит значение логической переменной success, а foo() запустит только если success == false.

Инициализация фигурными скобочками обычно используется с массивами или другими структурами данных. Например, в следующей программе три считанных числа гарантированно окажутся в a[0], a[1], a[2], ровно в таком порядке:

#include <iostream>
#include <vector>

using namespace std;

int read_int() {
    int x;
    cin >> x;
    return x;
}

int main() {
    vector<int> v = {read_int(), read_int(), read_int()};
}

Примечание

На самом деле, в стандарте C++17 в некоторых выражениях зафиксирован порядок вычислений: слева-направо вычисляются выражения при вводе через >> и выводе через << . При присваивании через =, += и похожие операторы сначала вычисляется часть справа, а потом часть слева. Есть и несколько других случаев, но они вам, скорее всего, не встретятся.

При этом порядок вычисления аргументов функции всё ещё не уточнён: subtract(next_a(), next_a()) в примере выше может вернуть как +1, так и -1 даже в C++17.

3.4.4. Undefined behavior

(Это довольно продвинутая тема, для начального изучения не особо нужная, но в целом иметь представление об undefined behavior надо.)

Неопределенное поведение, undefined behavior, сокращенно UB — это довольно необычная (по сравнению с другими языками) особенность C++. Смысл в том, что в определенных ситуациях (например, при выходе за пределы массива) программа на C++ имеет право делать что угодно — работать правильно, молча выдать неправильный ответ, не выдать ответа вообще, упасть с ошибкой, зависнуть, отформатировать жесткий диск и т.д. Стандарт C++ никак не определяет, что должна делать программа в таком случае, а наоборот, разрешает компиляторам делать такой исполняемый код, какой им удобнее — и, соответственно, вы не можете никак контролировать, как себя в этой ситуации будет вести программа.

Таких ситуаций довольно много, но в простейших программах вы скорее всего будете встречаться только с четырьмя — во-первых, использование непроинициализированной переменной, во-вторых, выход за пределы массива (в том числе строки), в-третьих, переполнение знаковых целых чисел (знаковых — т.е. тех, которые не unsigned), и в-четвертых, попытка два раза изменить одну и ту же переменную в пределах одной и той же команды.

Пример последнего случая — знаменитая запись i = i++ + ++i;. Здесь переменная i меняется три раза: за счет присваивания, за счет i++ и за счет ++i, при этом язык C++ не указывает, в каком порядке должны производиться эти изменения, поэтому это undefined behavior.

Примечание

Стандарт работает по принципу «что не разрешено — то неопределённое поведение». Так что несмотря на то, что в некоторых случаях действительно явно записано, что поведение в таком-то случае не определено, часто некоторый случай в стандарте просто не описан. Из-за этого до сих пор не существует никакого полного перечня неопределённого поведения, хотя подвижки в эту сторону были. Если вы любите длинные тексты и крайние случаи, то можете взглянуть на P1705 — предложение включить в стандарт хотя бы частичный список UB отдельным приложением.

Основное, что надо понимать про UB — это то, что поведение действительно не определено. Компилятор сделает такой исполняемый код, как ему удобнее, и результат будет зависеть от огромного количества параметров (конкретной версии компилятора и его опций, ОС, в которой работает программа, процессора, на котором она работает, в конце концов, от того, какие еще программы запущены параллельно с вашей или были запущены до нее), поэтому пытаться предсказывать результат бессмысленно. Максимум, что можно — попытаться как-то объяснить тот результат, который таки получится, но и это не всегда. В частности, на вопрос «чему будет равно i после i = i++ + ++i;» единственный верный ответ — «это undefined behavior, точка».

То, что я написал выше — это классические объяснение UB, но возможно оно не до конца понятно. Полезно на это посмотреть еще вот с какой стороны. Когда компилятор компилирует вашу программу, он исходит из некоторых предположений, которые необходимы для того, чтобы ваша программа работала. Например, он обязательно должен понимать, на каком процессоре будет запущена ваша программа, ну или хотя бы какие фичи этот процессор будет поддерживать — поэтому если вы скомпилируете программу с одними предположениями о процессоре, а потом запустите на процессоре, который таких фич не поддерживает, то понятно, что программа может повести себя странно — может отработать корректно, может выдать неверный ответ, вылететь и т.д. — ясно, что это не вина компилятора.

Точно также компилятор исходит из некоторых предположений про вашу программу. Например, он предполагает, что в вашей программе невозможен выход за пределы массива. Он может даже заметить, что в каком-то конкретном месте возможен выход за пределы массива, но компилятор понадеется на вас, на программиста — он подумает, что вам как автору программы известно что-то, за счет чего выхода за пределы массива там никогда не будет (возможно, компилятор недопонял какую-нибудь хитрую логику в вашей программе, которая гарантирует, что выхода за пределы массива не будет; или может быть просто соответствующие входные данные просто недопустимы и т.д.). И соответственно компилятор формирует исполняемый код, предполагая, что выхода за пределы массива не бывает. Ну а тогда если выход все-таки случился, то программа, как и в случае с неправильным процессором, может вести себя странно, причем нет никаких гарантий на то, как конкретно она себя поведет. То есть изначально может показаться, что UB — это компилятор специально делает такую подлянку программисту, но нет. Наоборот, UB — это результат того, что в программе случилось то, чего с точки зрения компилятора никогда не должно быть, на что компилятор в принципе не рассчитывал.

Примечание

Помимо неопределённого поведения также существует неуточнённое (unspecified) поведение, однако под UB обычно подразумевается именно первое. Типичный пример неуточнённого поведения (про который я уже писал выше) — стандарт не уточняет, в каком порядке следует вызывать функции при вычислении выражения foo() + bar() или в каком порядке вычислять аргументы при вызове buz(foo(), bar()). В отличие от UB, неуточнённое поведение какие-то гарантии про поведение программы даёт. Например, в таких выражениях и foo() и bar() будут вычислены хотя бы в каком-то порядке, компилятор не имеет права выкинуть вычисление одной из этих функций или вызвать ее два раза (а вот в случае undefined behavior компилятор может сделать вообще что угодно).

Обратите внимание, что пример с i++ + ++i — это именно неопределённое поведение, оно явно указано в стандарте, тут проблема именно в том, что оба слагаемых модифицируют одну и ту же переменную.

Иногда кажется, что последствия UB можно легко предсказать. Действительно, ну и пусть в программе выход за пределы массива, например, когда читаете элемент массива (не записываете данные в память, а читаете, для простоты). Казалось бы, ну и что, там за пределами массива все равно есть какая-то память, программа просто прочитает какое-то число, которое там записано, и будет с ним работать… Но нет. Дело еще в том, что современные компиляторы применяют очень серьезные оптимизации. И если компилятор видит, что он может применить какую-нибудь оптимизацию так, что она будет корректна во всех случаях, кроме тех, когда получается UB, то компилятор имеет полное право ее применять. И он может наоптимизировать так, что это уже будет не просто чтение памяти за пределами массива, а что-нибудь совем другое.

Классический пример — следующая программа:

#include <iostream>

int table[4] = {2, 4, 6, 8};

bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

int main() {
    for (int i = 0; i < 10; i++) {
        std::cout << i << " " << exists_in_table(i) << std::endl;
    }
    return 0;
}

(Здесь конструкция int table[4] = {2, 4, 6, 8}; — это массив в стиле C. Не надо его использовать в реальных программах, но тут для иллюстрации UB он нужен. С vector такого простого примера не получается.)

Функция exists_in_table пытается проверить, есть ли число v в массиве. Но в функции ошибка: выход за пределы массива при i==4, т.е. функция сравнивает v с числами, которые есть в массиве, и плюс делает одно лишнее сравнение с числом за пределами массива. Казалось бы, как такая функция будет себя вести? Она, понятно, вернет true для чисел 2, 4, 6, 8, ну и казалось бы еще вернет true для какого-нибудь еще числа, которому повезло лежать в памяти сразу после массива, а для остальных чисел вернет false. Но нет! Если скомпилировать программу с включенными оптимизациями, то функция будет возвращать true для любого вообще числа (ну и программа на экран выведет столбец единичек). Потому что компилятор увидел, что функция может или вернуть true (если v равно 2, 4, 6 или 8), или в функции случится UB. Т.е. на всех корректных путях функция возвращает true. А тогда зачем вообще делать какие-то проверки, давайте возвращать true всегда…

В общем, тема UB тесно связана с темой оптимизаций: компилятор делает оптимизации в предположении что UB невозможно, а если потом оказывается, что UB все-таки случится, то оптимизации могут повести себя совершенно непредсказуемо.

Ну и наконец — я выше писал, что в результате UB программа может отформатировать ваш жесткий диск. Конечно, просто так такого не случится. Но чисто теоретически это возможно, хотя и надо специально очень тщательно постараться. Конечно, если задаться такой целью, то возможно написать специальную хитрую программу, которая в результате UB отформатирует жесткий диск (хотя и не очень понятно, зачем так стараться — ясно, что намеренно отформатировать жесткий диск из программы можно и без всякого UB :) ). Но что хуже — если ваша программа принимает какие-то входные данные (как обычно и бывает), и в программе есть UB, то чисто теоретически злобный хакер может подобрать специальные хитрые входные данные, в результате которых UB сработает так, что программа отформатирует ваш жесткий диск. И это уже достаточно реально; конкретно форматировать жесткий диск современные хакеры вряд ли будут, а вот утечка персональных данных из-за UB — это вполне бывает (в качестве простейшего, но широко известного, примера, см. уязвимость Heartbleed).

У меня есть видео про undefined behavior, если хотите, можете посмотреть его.