Стайлгайд

Основные правила

Прежде, чем писать какой-либо код, обязательно прочитайте C++ Style Guide, на нашем курсе мы требуем полного выполнения Google C++ Style Guide с небольшими изменениями (касающимися нейминга и прочего; смотрите далее)

Какие пункты из Google C++ Style Guide наиболее важны:

Scoping
- Local Variables
- Static and Global Variables
Classes
Functions
- Parameter Ordering
- Write Short Functions
- Reference Arguments (с оговоркой про выходные параметры примитивных типов в п. 17)
Other C++ Features
Naming
Formatting

Ваша задача на этом курсе — написать наиболее простой, понятный, эффективный, читаемый и гибкий код среди тех, которые проходят ограничения по времени и по памяти. То есть в первую очередь должна быть правильной асимптотическая сложность, а потом сразу же думайте, как все сделать максимально просто.

Боритесь с дублированием кода.

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

Старайтесь писать аккуратно.

Удаляйте лишний, неиспользуемый, закомментированный код, удаляйте переменные и функции, которые вам на самом деле не нужны, остальные называйте понятно.

Синтаксис

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

Используйте 4 пробела для отступа. Данный размер отступа является наиболее распространенным, поэтому используйте его всюду для единообразия. 3-4 пробела также являются оптимальными размерами для отступа согласно NASA.
Вокруг всех бинарных операторов (=, ==, +, -, *, /, >, << и др.) должны быть пробелы с обеих сторон. Исключением являются операторы ., ->, ::.
После запятой должен быть пробел.
Между закрывающейся круглой скобкой и открывающейся фигурной должен быть пробел.
Не жадничайте с пустыми строками. Вставляйте всегда пустые строки между определениями глобальных функций, классов, констант, typedef'ов, include'ов, между объявлениями методов и функций, между реализациями функций, между объявлениями классов и реализациями функций и т.д.
Вставляйте пустые строки в код реализации функций, чтобы подчеркнуть разделение логических частей кода.
Не размещайте if, else, for, while и др. на одной строке со своим statement:
```
if (condition) statement;
else statement;
...
for (...) statement;
```
Это, во-первых, ухудшает читаемость кода. Вы можете вообще один из statement'ов не заметить или ошибочно решить, что он относится к if'у:
```
if (number % 2 == 0) std::cout << "Even\n"; even = true;
```
А во-вторых, при отладке debugger'ом невозможно понять, выполнив команду «Step Over», выполнилось или не выполнилось условие (или сколько итераций цикла прошло).
Также рекомендуется всегда обрамлять if, else, for, while фигурными скобками:
```
for (size_t index = 0; index < array.size(); ++index) {
    statement1;
    statement2;
    ...
}
```
```
for (auto number : array) {
    statement1;
    statement2;
    ...
}
```
даже если внутри только один statement.
```
if (number % 2 == 0) {
    std::cout << "Even\n";
}
```
Это более читаемо и безопасно. В варианте без скобок легко ошибиться, например, вот так:
```
if (number % 2 == 0)
    std::cout << "Even\n";
    even = true;
```
Легко подумать, что код even = true; тоже находится под if'ом.

Язык C++

Существуют разные языки программирования: C, C++, Java, Python и великое множество других. Между ними есть очевидные внешние сходства и различия: как написать цикл, как определить оператор, как создать класс. Однако основные их отличия кроются в принятых в них методах решения типовых задач и инструментах: если писать цикл по индексу, то какие должны быть его границы? если определить оператор, каков должен быть тип принимаемых аргументов и возвращаемого значения? если создавать класс, какие переменные-члены стоит в нем определять, какие методы, что следует вынести во внешние функции? На все эти вопросы можно дать разные ответы, и все они будут отчасти верными. Есть и общие рекомендации и конструкции, которые зарекомендовали себя за долгое время использования, как надежные и удобные, а также примеры, как делать не надо. Некоторые из них описаны в этом разделе.

#include <bits/stdc++.h> использовать нельзя.
Подробнее
1. Увеличивается время компиляции при подключении данного заголовочного файла. В случае стандартной библиотеки разницу во времени компиляции вы не увидите, но когда у вас будет большой проект, то это будет уже существенно влиять на время компиляции (чтобы она шла 3 минуты, а не 30).
2. Некоторые компиляторы не поддерживают данный заголовочный файл (такие, как MSVC, XCode и другие).
Подключайте только те библиотеки, которые вы используете.
Не подключайте C-шные библиотеки с помощью #include <название_библиотеки.h>.
Пример

Пишите не так:
```
#include <math.h>
```
А так:
```
#include <cmath>
```
using namespace std; использовать нельзя.

Подробнее

Включать целый namespace опасно, так как из-за этого может возникнуть конфликт имен. Вследствие чего могут возникнуть нетривиальные ошибки компиляции/линковки, а если не повезет, то переменная из namespace может совпасть по названию с какой-то вашей переменной, про которую вы не помните ее область видимости, что приведет к еще более сложнонаходимым багам, хоть все и скомпилируется, но иногда вы будете использовать переменную, думая, что это ваша переменная, и в ней такое-то значение, а значение будет совсем другим. Если нужно использовать много раз std::vector, напишите using std::vector; если cout, то using std::cout; и т.д. Кроме того, включая namespace, вы нарушаете сам принцип использования namespace'ов.
Использовать массивы фиксированной длины int[], int* не рекомендуется — используйте вместо них std::vector<int>. Использование конкретных структур данных обуславливается темой контеста и требованиями к задаче.
Не используйте C-type строки char[] и char* - используйте вместо них std::string.
Не используйте ввод-вывод в стиле С через функции scanf, printf.

Подробнее

Используйте вместо них операторы >> и << у std::cin и std::cout соответственно. Если при этом в задаче большой размер ввода-вывода (от 100000 чисел), то необходимо использовать несколько дополнительных приемов, чтобы ваш ввод-вывод работал достаточно быстро, иначе вы можете получить Time Limit Exceeded. Эти приемы описаны ниже.
Пример на пункты 4 — 7:
```
#include <algorithm>
#include <string>
#include <vector>

using std::string;
using std::vector;

vector<string> input() {
    size_t rows;
    std::cin >> rows;
    vector<string> table;
    table.reserve(rows);
    for (size_t row = 0; row < rows; ++row) {
        string line;
        std::cin >> line;
        table.push_back(line);
    }
    return table;
}

vector<string> process(vector<string> table) {
    std::reverse(table.begin(), table.end());
    return table;
}

void output(const vector<string>& table) {
    for (const auto& row : table) {
        std::cout << row << std::endl;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    const auto& table = input();
    table = process(table);
    output(table);
    return 0;
}
```
Важно: По умолчанию для iostream включен режим совместимости с stdio, который позволяет одновременно использовать оба интерфейса для ввода/вывода. В этом режиме производительность std::cin и std::cout понижается в несколько раз.
Подробнее

Поэтому если размер ввода/вывода имеет порядок от 100000 чисел, вам надо будет отключить этот режим. Делать это надо до совершения каких-либо операций ввода-вывода, желательно первой же строкой в программе:
```
#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    ...
    return 0;
}
```
Также обратите внимание на то, что std::cout может работать слишком медленно, если вы выводите порядка 100000 чисел или более, и при этом у std::cout регулярно очищается буфер. Буфер очищается при каждом выводе std::endl, так что в случае большого вывода лучше выводить "\n" вместо std::endl. Также буфер std::cout очищается при каждом вводе через std::cin — это связано с тем, что при пользовательском вводе-выводе через обычный std::cin и std::cout в консоли необходимо перед тем, как запрашивать очередной ввод от пользователя, показать ему последний вывод перед этим, а значит и очистить буфер. Эта проблема для задач с большим выводом решается с помощью вызова std::cin.tie(nullptr); в самом начале программы. Выполнение всех этих рекомендаций приведет к тому, что ввод-вывод при помощи потоков std::cin и std::cout будет работать не медленнее ввода-вывода через printf и scanf на задачах с большим вводом-выводом. Подробнее см. здесь.
Если используется значение типа истина/ложь, то используйте тип bool, а не int.
Не используйте тип long.

Подробнее

Более стандартный тип — int, к нему у всех уже привыкли глаза, и long с теми же намерениями — просто смотрится странно. На 32-битных машинах оба типа являются 32-битными и ничем не отличаются, поэтому используйте int вместо long. Если вам нужен 64-битный тип, придется воспользоваться типом int64_t.
При прочих равных, используйте преинкремент ++i, а не постинкремент i++. Это полезная привычка. В случае int'ов это все равно, но если у вас будет в коде сложный итератор, то в процессе постинкремента создается его копия в памяти, что может создать вам неожиданные тормоза и повышенное использование памяти, а догадаться о том, что вся проблема — в коротком выражении it++ — будет сложно.
main должен заканчиваться return 0;, в противном случае на некоторых компиляторах программа может завершиться с ненулевым кодом возврата, что в свою очередь приводит к Runtime error в тестирующей системе.
Вставляйте слово const везде, где только это возможно по смыслу.

Подробнее

Если какая-то переменная по сути меняться в функции не должна, она должна быть const. Если метод класса не меняет при вызове содержимое класса, он должен быть const-методом. Таким образом вы обезопасите себя от многих глупых ошибок: они отловятся еще на этапе компиляции.

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

Подробнее

Если какие-то входные или выходные данные в задаче используют индексацию с единицы, лучше в функции ввода, соответственно вывода, переведите индексацию из одной системы в другую, а везде внутри программы, помимо функций ввода и вывода пользуйтесь индексацией с нуля. Весь язык C++ так спроектирован, что индексация с нуля гораздо удобнее, а как только вы начинаете использовать индексацию с единицы, становится неудобно, появляются вычитания единицы из переменных по всему коду и т.д.
Задумывайтесь о переполнениях типов. Если у вас есть две переменные типа int, значение каждой равно миллиону, и вы их перемножаете, то тип переполнится (максимальное значение — \(2^{31} - 1\)), и вы получите неправильный результат. Необходимо перед перемножением привести обе переменные к 64-битному типу int64_t. Если у вас есть две int переменные со значением два миллиарда и вы их складываете, — тоже произойдет переполнение, тоже нужно предварительно приводить к int64_t.
Не вычитайте никогда просто так ничего из container.size(), где container — какой-нибудь контейнер из STL.
Подробнее

Например, vector.size() возвращает беззнаковый size_t (который обычно просто синоним для unsigned long), и если вы будете из него вычитать, то можете легко получить переполнение. Например, если вектор пустой, а вы вычитаете единицу, чтобы узнать последний элемент, или вектор состоит только из одного элемента, а вы вычитаете 2, чтобы узнать предпоследний элемент, и т.д. Всегда приводите результат вызова size() к int'у, если вам совершенно необходимо вычесть из size(), либо постарайтесь переписать сравнение без операции вычитания. При этом в самом распространенном случае, когда вам нужно написать цикл for, проходящий по всем элементам, кроме, скажем, последних десяти, надо просто писать не так
```
// Wrong! If container.size() < 10, you'll get an infinite cycle.
// This code won't compile with the -Werror flag.
for (int index = 0; index < container.size() - 10; ++index) {
    ...
}
```
В этом цикле, если, к примеру, container.size() == 5, то вы получаете реально цикл
```
// Note that 4294967291 > MAX_INT, so the cycle is infinite
for (int index = 0; index < 4294967291; ++index) {
    ...
}
```
А пишите лучше всегда так
```
// Correct: size_t and adding instead of subtracting
for (size_t index = 0; index + 10 < container.size(); ++index) {
    ...
}
```
ну или хотя бы так
```
// Correct: casted to int
for (int index = 0; index < static_cast<int>(container.size()) - 10; ++index) {
    ...
}
```
Соответственно, если вам нужно вызвать функцию, в которую вы должны передать индекс первого и последнего элемента вектора, то делайте это так:
```
someFunction(0, static_cast<int>(container.size()) - 1)
```
По-хорошему, здесь надо бы еще проверять, что в контейнере что-то есть, но к int'у приводить надо в любом случае, иначе появляются неочевидные баги.
Не пользуйтесь макросами для определения констант.
Подробнее

Макросы — это очень опасная и неудобная вещь. Их раскрывает специальный препроцессор, который начинает работать еще до компилятора C++, и он ничего не знает о самом языке. Все конструкции раскрываются буквально. В связи с этим есть множество возможных неочевидных побочных эффектов, а у компилятора нет возможности выполнить проверку типов, константность и т.д. Читайте более подробно об этом в книге Майерса «Effective C++».

Итак, неправильный вариант:
```
#define MAX_LENGTH 100000  // Wrong! Don't use macros!
```
Правильный вариант:
```
constexpr int kMaxLength = 100'000;  // Correct
```
Входные параметры передавайте в функцию по константной ссылке; по ссылке — чтобы они лишний раз не копировались, по константной — чтобы вы не могли их случайно изменить. Не забывайте про const! Выходные параметры передавайте в функции по указателю — чтобы вы могли их изменить; по указателю, а не по ссылке, — чтобы вы могли в месте вызова отличить входные параметры от выходных по амперсанду перед именем переменной. Размещайте входные параметры перед выходными в списке параметров функции или метода. Аргументы примитивных типов следует передавать в функции по-другому. Входные параметры типов int, char, bool, double передавайте по значению. Они будут копироваться, но это так же почти бесплатно, как и в случае ссылок или указателей. При этом вы не сможете их изменить изнутри функции, что и нужно, т.к. это входные параметры. Если вам нужны эти типы как выходные параметры функции, лучше передавайте их по ссылке, т.к. иначе легко внутри функции перепутать указатель на переменную с самой переменной, и сделать совсем не то, что вы собирались.
Примеры:
```
void input(std::vector<Point>* sequence, int& points_to_cover);

void findMaximumsInSlidingWindow(
    const std::vector<int>& sequence, 
    const std::string& shifts, 
    vector<int>* maximums);

double findMinimumCoveringCircleRadius(
    const std::vector<Point>& points, 
    int points_to_cover);
```
Примеры вызовов:
```
std::vector<int> sequence;
int points_to_cover;
input(&sequence, points_to_cover);
...
...
std::vector<int> sequence;
std::string shifts;
input(&sequence, &shifts);
std::vector<int> maximums;
findMaximumsInSlidingWindow(sequence, shifts, &maximums);
...
...
double min_radius = findMinimumCoveringRadius(points, points_to_cover);
```
Обратите внимание на амперсанды & перед переменными, в которые записывается результат вызова функции. Если функция возвращает одну величину, пусть она делает это по значению. Это столь же быстро, зато удобнее в месте вызова. Пример:
```
std::vector<int> readNumbers(std::istream& input_stream = std::cin) {
    size_t sequence_length;
    input_stream >> sequence_length;
    std::vector<int> numbers(sequence_length);
    for (size_t i = 0; i < numbers.size(); ++i) {
        input_stream >> numbers[i];
    }
    return numbers;
}

int main() {
    std::vector<int> first_sequence = readNumbers();
    std::vector<int> second_sequence = readNumbers();
    ...
}
```
Лишнего копирования в этом месте не возникнет. Дело в том, что эта операция настолько часто встречается, что компиляторы научились ее распознавать и генерировать эффективный код для нее. Технология называется return value optimization, известна также под своей аббревиатурой RVO. Можно и следует по умолчанию считать, что она есть и исправно работает, и писать код так, чтобы им было удобнее пользоваться. Чтобы узнать об этом более подробно, поищите в вашем любимом поисковике ее описание по названию. Если переданный на вход параметр для выполнения алгоритма необходимо изменять, — это не означает, что параметр автоматически становится выходным параметром. Если целью алгоритма не является менять входной параметр, то изменять этот параметр функция не должна: пользователь алгоритма этого не ожидает, и будет очень не рад такому побочному эффекту. Кроме того, если просто передать параметр по ссылке и поменять его внутри, то пользователь даже не будет догадываться о том, что переданные им данные будут изменены. Появляющиеся вследствие таких побочных эффектов баги очень тяжело искать. Соответственно, в таких ситуациях есть два решения: передавать параметр по значению или передавать как обычно по константной ссылке, а внутри функции копировать и изменять уже копию. Первый вариант (передавать по значению) обычно предпочтителен. Т.к. объект передается по значению, его можно менять внутри функции в процессе работы алгоритма (например, сортировать, если это вектор), при этом объект не изменится в месте вызова функции. При копировании аргумента, переданного по константной ссылке, в функции появляется два одинаковых по смыслу объекта, что может привести к путанице и использованию одного из них вместо другого, кроме того, копировать приходится вручную, тогда как при передаче объекта по значению копия делается автоматически, без написания дополнительного кода. Пример:
```
std::vector<int> unique(std::vector<int> numbers) {
    // here we sort a copy of given numbers,
    // so that the user does not lose his data
    std::sort(numbers.begin(), numbers.end());
    numbers.erase(
        std::unique(numbers.begin(), numbers.end()),
        numbers.end());
    return numbers;
}
```
Разделяйте использование class и struct: классом должна быть любая сущность, которая содержит в себе логику, тогда как структура — это набор данных, объединенных в один объект. В классе все переменные-члены должны быть приватными, для доступа к ним делайте аксессоры, в структуре все переменные должны быть публичными, нетривиальных методов быть не должно.
Пример
```
struct Point {
    double x, y;
};

// Compares first by x-coordinate, then by y-coordinate
bool operator<(const Point& first, const Point& second) {
    if (first.x != second.x) {
        return first.x < second.x;
    }
    return first.y < second.y;
}

class Path {
public:
    Path(double time, double average_speed)
        : time_(time), average_speed_(average_speed)
    {}
    
    double time() const {
        return time_;
    }
    
    double averageSpeed() const {
        return average_speed_;
    }
    
    double distance() const {
        return time_ * average_speed_;
    }

private:
    double time_;
    double average_speed_;
};
```
От структуры точки нам ничего не требуется, поэтому она состоит только из двух публичных полей. Метод compare добавлять нельзя, задача сравнения решается определением внешнего оператора <. Если нужно, например, запретить изменять координаты (устанавливать их только при создании точки), то ее нужно делать классом с двумя get-аксессорами. В классе Path хранятся две величины, а получать требуется три. Если бы time и average_speed были публичными переменными, то доступ к значениям скорости и времени происходил бы как path.time и path.average_speed, а доступ к пройденному расстоянию — как path.distance(). Для нахождения расстояния приходится добавлять скобки, то есть всегда приходится помнить о том, что расстояние — это метод, а время и скорость — переменные. Если по какой-то причине (например, недостаточная точность) в будущем хранимые переменные нужно будет поменять и перейти к системе (время, расстояние), то в нашем случае с приватными переменными лишь изменится реализация методов, сохранив интерфейс класса. В случае же с публичными переменными придется изменять интерфейс класса, что немедленно влечет изменение всего кода, который его использует. Хранить все три величины переменными категорически нельзя: если время было равно 1, то действие path.time = 0.0 нарушит инвариант time * speed == distance, что приведет к совершенно непредсказуемым последствиям. Итак, если вам нужно хранить данные под общим именем, вам подойдет структура; во всех остальных случаях создавайте полноценный класс только с приватными переменными-членами.
Старайтесь не использовать по возможности динамическое выделение памяти (с помощью new и malloc):
Почему
если вы будете его использовать, вам необходимо будет заботиться и об «уборке мусора», т.е. освобождении памяти. Правильный, безопасный способ это делать — не очень простой и не входит в материалы курса. Кроме того, вызов new довольно медленный, поэтому если очень много раз это сделать, то можете не влезть в Time limit. Если вам интересно, как правильно управлять динамической памятью, читайте книгу Майерса «Effective C++» или наберите в поисковике «RAII».
При использовании vector имейте в виду, что у него есть удобные методы: различные конструкторы, позволяющие задать размер и значение элемента вектора по умолчанию, операторы присваивания, сравнения (лексикографического) и оператор swap.
Примеры:

Создание двумерного вектора размером rows * columns, заполненного значением 100:
```
std::vector<std::vector<int>> cache(
    rows,
    std::vector<int>(columns, 100));
```
Перестановка двух векторов местами без копирования всего содержимого:
```
std::vector<int> first(1000000, 1);
std::vector<int> second(2000000, 2);
first.swap(second);
```
Здесь меняются местами реально два внутренних указателя int*, что значительно эффективнее, чем копирование векторов целиком, особенно если они большого размера.
Обратите внимание, что для взятия модуля вещественного числа (float, double) необходимо пользоваться функцией fabs, а не abs. При этом в Microsoft Visual Studio сделана перегрузка abs, которая работает и для вещественных чисел даже если вы не подключили заголовочный файл с ней напрямую. Однако на сервере при этом будет abs(-2.75) != 2.75.

В общем же случае стоит отметить, что в C++ существует 2 версии abs:
- в cmath, определенная для вещественных чисел (float, double и long double).
- в cstdlib, определенная для целых чисел (int, long и long long).
Распространенная ошибка состоит в том, что подключается cmath и используется abs оттуда, что приводит к приведению целых типов в double, что в свою очередь может приводить к ошибкам округления при вызове abs(long long).

Поэтому общее правило следующее:
- для взятия модуля вещественного числа необходимо подключить cmath и использовать fabs.
- для взятия модуля целого числа необходимо подключить cstdlib и использовать abs.
Если вы пользуетесь стандартом c++11(c++0x), то для генерации (псевдо)случайных чисел рекомендуется использовать заголовок random с генератором псевдослучайных чисел std::mt19937 и распределениями:
```
std::uniform_int_distribution
std::uniform_real_distribution
```
и другими, если понадобятся.
Подробнее

В противном случае, имейте в виду, что значение RAND_MAX — ограничение сверху на значения, выдаваемые функцией rand(),— отличается в разных компиляторах. Тщательно изучите, какое значение данной границы в вашем компиляторе, а какое — в компиляторе в автоматической системе (компилятор вы выбираете при сдаче задания). Подходит ли вам такое ограничение сверху, или нужно построить на базе функции rand() алгоритм, позволяющий возвращать случайные числа, равномерно распределенные в более широком диапазоне, чем [0, RAND_MAX - 1]? При использовании схемы, предложенной стандартом c++11|(c++0x), следует обратить внимание на то, где создавать генератор. Каждый алгоритм должен использовать собственный генератор, чтобы добиться независимой работы всех алгоритмов. Например, два алгоритма, использующих случайность, должны работать одинаково, вне зависимости от порядка их вызовов. Такой независимости сложно добиться при использовании функции rand(). Например, если вы хотите реализовать рандомизированный алгоритм сортировки, то нужно создать генератор внутри внешней функции, которую и будет вызывать пользователь, и передать его во внутреннюю, где будет реализована вся логика сортировки:
```
#include <random>

template <class Iterator>
void sort(Iterator begin, Iterator end) {
    std::mt19937 generator;
    quickSort(begin, end, generator);
}
template <class Iterator, class RandomGenerator>
void quickSort(Iterator begin, Iterator end, RandomGenerator& generator) {
    ...
}
```
В большинстве случаев нельзя сравнивать числа типа float и double просто операторами <, >, <=, >=, ==:
Почему

При вычислениях в вещественных типах накапливается погрешность, вследствие чего равные по сути числа, вычисленные с помощью разной последовательности действий, могут получить различные значения в типах float и double, и даже a < b может измениться на b < a. Погрешность вычислений можно оценить, используя точные знания о том, как именно выполняются арифметические операции, а также как происходят вычисления в используемых вами функциях. Обычно делать этого точно не нужно, т.к. точность типа double позволяет хранить 15-16 знаков, а требуемая в задаче точность обычно порядка \(10^{-6}\) или \(10^{-9}\), но не меньше. Однако для того, чтобы корректно сравнивать числа, следует использовать порог сравнения. Примеры:
```
const double kComparisonThreshold = 1e-8;

bool less(double first, double second) {
    return first < second - kComparisonThreshold;
}

bool lessOrEqual(double first, double second) {
    return first < second + kComparisonThreshold;
}

bool equal(double first, double second) {
    return fabs(first - second) < kComparisonThreshold;
}
```
Для своих типов (классов, структур), если объекты типа необходимо сравнивать между собой, реализуйте всегда operator< и не реализуйте остальные операторы сравнения (operator<=, operator>, operator>=):
Почему

Через operator< выражаются все остальные, и общепринятая конвенция — реализовывать только сравнение на «меньше». В противном случае, дублируется код, а работа различных операторов может оказаться несогласованной. Точно так же, общая конвенция, — что сортировка объектов по умолчанию делается по возрастанию, и в качестве компаратора передается функция сравнения на «меньше». Это правило необходимо соблюдать, чтобы вашу программу было легко понимать другим программистам.
Не используйте std::pair (за исключением случая, описанного ниже).

Подробнее

Причина в том, что в месте использования объекта pair невозможно понять, что кроется за полем first, а что — за полем second. Это абстрактные названия, которые могут означать что угодно, а в месте использования никаких указаний на это нет. Даже если в месте определения переменной указать, что в ней хранится в first и second, при чтении придется постоянно возвращаться к месту определения переменной, чтобы разобраться в коде и убедиться, в частности, что first и second нигде не перепутаны местами — часто встречающаяся ошибка! Исключением являются небольшие участки кода (помещающиеся на один экран), в рамках которых создается из имеющихся объектов pair, далее удобно используется для какой-нибудь операции (например, сортировка), и затем все pair обратно «расшифровываются» в новые объекты и более не используются. Это может быть удобно для сортировки по вторичному параметру, т.к. для pair есть оператор сравнения по умолчанию, который сравнивает сначала по first, затем по second. При этом код легко понять, т.к. pair определен и используется в одном очень локальном куске кода, который можно охватить взглядом целиком.

Организация кода

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

У каждой переменной должна быть одна-единственная явная цель. Никогда не создавайте переменных tmp, выполняющих несколько разных вспомогательных функций во всем коде. Используйте переменную только с одной целью. Переменные, в названии которых используется tmp или temp, почти всегда либо бессмысленные и ненужные, либо неправильно названы.
Объявляйте переменные как можно ближе к месту их первого использования. Старайтесь сразу же инициализировать переменные. Если переменная используется только внутри функции, она должна быть локальной для функции. Если только внутри цикла, она должна быть локальной для цикла. Никогда не делайте глобальных переменных. Локальные переменные блока предпочтительнее по сравнению с локальными переменными функции, локальные переменные функции — по сравнению с переменными-членами класса, а последние — по сравнению с глобальными переменными. Стремитесь сократить «время жизни» каждой переменной: чем меньше время жизни переменных, тем меньше переменных приходится одновременно держать в голове при чтении и написании кода. Исследования показывают, что человек может эффективно держать в памяти не более 5-7 переменных одновременно. Большее количество неизбежно приводит к ошибкам.
Разделяйте программу на ввод, решение и вывод, это делает ваш код более модульным. Способы ввода и вывода часто меняются. У нас используются стандартные потоки и определенный описанный формат, в следующий раз те же данные могут быть записаны в файле или в базе данных в другом формате, затем они же могут поставляться уже в виде переменных в более сложной программе, которая использует ваш алгоритм в качестве подпрограммы. Записывайте вход в отдельные переменные и результат работы — в отдельные. Для их заполнения и вывода напишите отдельные функции. В частности, ваш код становится легче тестируемым, что является важным свойством. Вы можете написать альтернативное решение и сравнить его с вашим, можете запустить стресс-тест. Вообще это две принципиально разные области ответственности: ввод-вывод и преобразование данных. Не смешивайте в одном классе или функции несколько разных областей ответственности: один класс отвечает ровно за одну область. Иначе он разрастается, становится слишком сложным, а две разные области ответственности начинают быть слишком сильно связанными. Это плохо, потому что чем более независимы разные части программы, тем меньше поводов для ошибок и тем проще тестировать части программы по отдельности.
Никогда не используйте «магические константы» в коде. Если у вас где-то в коде встречаются, например, 'a' и 'z', означающие минимальный и максимальный символ алфавита, то их надо заменить на именованные константы. Например так:
```
const char kMinLetter = 'a';
const char kMaxLetter = 'z';
...

for (char letter = kMinLetter; letter <= kMaxLetter; ++letter) {
    ...
}
...
```
Пишите комментарии только по делу. В идеальном случае лучше обходиться вообще без них — ваш код прокомментирует сам себя. Конечно, так редко удается, поэтому комментарии к классам и функциям бывают полезными. Не нужно оправдывать плохое имя (см. следующий раздел) подробным комментарием. Если у вас встречается объявление вида
```
int n;  // number of balls in the bucket
```
то нужно заменить его на int number_of_balls; или int numBallsInBucket; в зависимости от принятого стиля, от того, бывают ли шары не в корзине, и от контекста. Писать комментарий следует над тем, к чему он относится. Комментарии в конце строки значительно удлиняют ее, поэтому ухудшают читаемость. При этом желательно, чтобы строка влезала в 100 символов, а зачастую бывает жесткое ограничение по длине строки (как в нашей системе проверки). Если вы все же пользуетесь комментарием в конце строки, то отделяйте его двумя пробелами от кода. Если вы решили снабдить свой код подробными комментариями, указывайте в них то, что будет интересно читающему. Для класса это описание того, для чего класс нужен, как им пользоваться. Для функции и метода — что они делают, что возвращают, что принимают на вход, какие исключения могут бросать. Вот пример хорошего комментария к функции.
```
/* Applies per symbol transformation to string.
* input[i] is transformed into transform[input[i]].
* If transform map doesn't contain input[i] and default_symbol isn't null,
*   input[i] is transformed to default_symbol.
* If transform map doesn't contain input[i] and default_symbol == 0,
*   function throws TransformError.
*/
string transformString(
    const std::string& input,
    const std::map<char, char>& transform,
    const char default_symbol);
```

Имена

У каждой создаваемой сущности в коде есть имя. Сперва автор, а впоследствии, и все читающие код ассоциируют имена с сущностями, которые они обозначают. Чтобы в каждый момент точно понимать, что в переменной хранится, чтобы быть уверенным в том, что вызов функции вернет ожидаемое значение, имена нужно давать осмысленные и грамотно определенные.

Имена переменных должны быть длинными и понятными. Каждый раз, когда вы пишете одно-двух-буквенное название переменной или используете что-то вроде cur, должно возникать неприятное чувство. Единственное место, где можно позволить себе однобуквенные переменные, — в качестве счетчика в очень коротком for'е без вложенных циклов. И то, у вас должны быть серьезные опасения, когда вы это делаете, вы должны делать это осознанно. Иначе можно легко допустить ошибку с индексами, например перепутать i с j, что происходит постоянно, если называть так переменные. Искать такую ошибку вы будете несколько часов или дней. Даже если в описании задачи есть названия R и L, это не значит, что в программе нужно их так называть. Стиль математического текста очень сильно отличается от стиля кода программы. В математическом тексте есть очень много слов, описывающих формулы и то, что в них происходит. В самих формулах ценится краткость. В коде же наоборот, слов, описывающих происходящее, практически нет. Код должен описывать сам себя, названиями переменных, методов и классов. Поэтому названия должны быть очень прозрачными. Не должно быть нужно возвращаться и смотреть вверх в объявление переменной или смотреть на ее инициализацию, чтобы понять, что она в себе содержит. Никогда не называйте переменные something1 и something2, так как очень легко ошибиться и попасть по соседней клавише, тем самым очень легко сделать баг, а искать его будет тяжело. Используйте something_first и something_second или что-нибудь еще. Как выбрать понятное название переменной? Сперва нужно описать переменную на английском (так чтобы из описания было понятно, что хранит переменная), а далее выбирать название исходя из соображений компромисса между длиной и понятностью. (3-5 слов в названии — это нормально).
Все, что относится к именам переменных, относится и к именам функций, классов и методов. Кроме того, в названиях методов (функций) обязательно должен быть глагол, описывающий действие, которое выполняет метод. Это действие должно быть одно. У каждой функции должна быть одна ясная цель. Если вы понимаете, что не можете придумать название функции без слова And (например, readFromFileAndSort), значит, функция выполняет две разные цели, и скорее всего, ее нужно разбить на несколько меньших функций (readFromFile и sort), и из внешней вызывать подряд внутренние.
Не сокращайте слова в названиях. Это ухудшает читаемость кода, а также делает невозможным поиск по нему. Не нужно сокращать index до ind или idx, current — до cur и т.д. Единственное исключение — общепринятые сокращения типа Http и т.д.
Выделяйте названия приватных членов классов, это позволяет отличить их от аргументов методов. Наиболее распространенными способами являются подчеркивание в конце: name_, — или префикс m_: m_name. Начинать имя переменной с подчеркивания не принято; следует помнить о том, что имена, начинающиеся на два подчеркивания или подчеркивание и заглавную букву, зарезервированы стандартом, и использовать их нельзя.

Продвинутые замечания

Не оптимизируйте преждевременно. Ваш алгоритм должен иметь правильную асимптотическую сложность, чтобы иметь шансы пройти в Time limit. Он должен правильно работать, чтобы не получить Wrong answer. Это два основных тезиса. Не нужно оптимизировать с целью ускорить программу в константу раз, если это хоть сколько-нибудь усложняет код. Старайтесь сделать свое изначальное решение максимально простым. Оптимизировать нужно только после того, как вы четко замерили время работы программы, убедились, что оно слишком большое, определили, какая именно функция создает узкое место. Даже суперпрофессионалы не берутся заранее предсказывать узкие места системы: в наше время, когда компиляторы умеют делать сумасшедшие оптимизации, это практически невозможно предугадать. Поэтому профессионалы и не пытаются делать это заранее и оптимизировать что-либо заранее. Сначала измерьте, найдите узкое место, а потом уже пытайтесь его оптимизировать. Все вышесказанное относится к выносу переменных из цикла для ускорения, к перебору не до n, а до n / 2 и т.д. — не нужно ничего из этого сделать. Напишите максимально простое решение, добейтесь правильной его работы, и если вдруг после этого оно окажется слишком медленным — только тогда оптимизируйте. Ваша задача в программах, которые вы пишете на этом курсе, — написать наиболее простой, понятный, читаемый и гибкий код, среди тех, которые проходят в ограничения по времени и памяти. Помните об этом и не оптимизируйте, жертвуя простотой и удобством.

Algorithms and Data Structures