Это первая глава черновика книги PragmatiC++ — о прагматичном и «понятном через год» C++. Исходный текст главы открыт на GitHub.
Обобщения
Представьте на минуту, что C++ — это не набор странных ключевых слов и ошибок линковки, а всего лишь ещё один способ поговорить о мире вокруг нас: о людях, числах, цветах, событиях и котах. Мы привыкли думать о программировании как о чём‑то сугубо техническом, где важно запомнить синтаксис, расставить точки с запятой и "угадать", чего сейчас хочет компилятор.
Но если задать себе вопрос «а чем вообще оперирует программа?», внезапно выясняется, что за всеми этими int, struct и template прячутся довольно простые и понятные идеи: вещи, их свойства, группы похожих вещей и правила, по которым одни вещи превращаются в другие.
И попробовав объяснить, что такое объекты, типы и прочие фундаментальные понятия информатики, неизбежно приходится выходить за рамки чисто технического языка и говорить о более общих категориях идей, с которыми человечество работает уже тысячи лет, и именно здесь нам пригодятся слова «сущность», «вид» и «род».
Абстрактные и конкретные сущности
Когда философы и логики говорят об абстрактных сущностях, они имеют в виду индивидуальные вещи, которые не существуют в пространстве и времени так, как существуют стол, человек или компьютер, а как нечто неизменное: например, число 13 или сам по себе синий цвет не родились в какой‑то момент и не "умирают" через какое‑то время, это не объекты физического мира, а идеи, с которыми мы работаем в голове и в математике.
Конкретная сущность, наоборот, всегда привязана к истории, к моменту появления и моменту исчезновения: Сократ когда‑то родился и когда‑то умер, любая страна как политическая сущность была создана в определённую дату, и хотя страна продолжает существовать, вполне понятно, что когда‑то её не будет или она может радикально измениться.
Атрибуты и идентичность
При этом говорить можно не только о самих сущностях, но и об их атрибутах — это соответствие между конкретной сущностью и абстрактной сущностью, которое описывает какое‑то свойство: цвет глаз Сократа можно описать как конкретный пример абстрактного цвета, число земель Германии — как конкретное значение абстрактного натурального числа.
Если мы в какой‑то момент делаем "снимок" конкретной сущности, фиксируем полную совокупность её атрибутов здесь и сейчас, мы понимаем, что со временем отдельные атрибуты могут меняться, а вот идентичность остаётся, и именно идентичность, это очень примитивное, но глубокое чувство "это всё ещё он", позволяет нам говорить, что человек, страна или объект программы продолжают быть собой, хотя их свойства меняются.
Виды и роды
Дальше возникает необходимость каким‑то образом группировать сущности, и здесь на сцену выходят понятия вида и рода, причём каждая из этих категорий тоже бывает абстрактной и конкретной, и когда мы говорим об абстрактном виде, мы описываем общие свойства целого семейства абстрактных сущностей.
Так, вид "натуральное число" охватывает все отдельные числа 0, 1, 2, 3 и так далее (ноль может не попадать в натуральные числа и рассматриваться как пустое множество), вид "цвет" — все возможные оттенки от тёмно‑синего до ярко‑оранжевого, и мы можем рассуждать о них как о чём‑то общем, не привязываясь к конкретному экземпляру.
Конкретный вид, напротив, описывает набор атрибутов для семейства конкретных сущностей: когда мы говорим "человек", мы имеем в виду конкретный вид, который включает всех людей с определённым набором характеристик вроде биологии, сознания и т.п., когда говорим "части света", мы описываем конкретный вид, который включает Европу, Америку или Азию, у каждого из которых есть границы, население, площадь и другие атрибуты. Они различны как сущности, но в пределах вида "человек" или "часть света" мы можем говорить о повторяющихся структурных свойствах и моделировать их в коде как объекты одного типа данных.
Функции как правила
Важную роль в этой картине играет понятие функции, и здесь математическое определение почти дословно переезжает в программирование: функция — это правило, которое некоторому набору абстрактных сущностей, называемых аргументами и принадлежащих определённым видам, сопоставляет другую абстрактную сущность, называемую результатом, принадлежащую, возможно, другому виду.
Классический пример из математики — функция следования, которая каждому натуральному числу сопоставляет следующее за ним число, функция "n → n + 1" в терминах натурального вида; другой пример более образный — функция смешивания цветов, которая двум аргументам вида "цвет" сопоставляет третий цвет как результат их смешения, и если вы когда‑нибудь писали код, который по двум Color возвращает новый Color, вы фактически реализовывали именно такую функцию.
В программировании мы живём внутри этого определения: любой вызов функции в C++ — это применение правила к аргументам, которые являются конкретными "слепками" абстрактных сущностей, и результатом становится новый объект, который тоже можно рассматривать как конкретное воплощение абстрактной сущности определённого вида.
// Вид: натуральное число
using Natural = unsigned int;
// Функция следования: n → n + 1
// Правило, которое каждому Natural сопоставляет следующий Natural
Natural successor(Natural n) {
return n + 1;
}Роды как обобщения видов
Если подняться на следующий уровень абстракции и поговорить о родАх, то они позволяют говорить не только о конкретных значениях или даже видах, но и о больших классах понятий.
Абстрактно – род — это способ описать множество разных абстрактных видов, которые сходны в каком‑то отношении: например, род "число" включает такие виды как "натуральное число", "целое число", "вещественное число", каждый из которых имеет свои правила существования, но мы можем рассуждать о них как о числе вообще, не уточняя вид; род "бинарный оператор" включает в себя и арифметические операции сложения и умножения, и логические операции "и", "или", и побитовые операции, но все они подчиняются общей схеме "берём два аргумента и получаем результат".
Конкретный род, в свою очередь, описывает набор разных конкретных видов, сходных по каким‑то признакам: "млекопитающее" описывает разные конкретные виды вроде человека, кошки и кита, "двуногое" описывает другую классификацию, которая включает людей, птиц и, возможно, некоторых вымышленных существ, и одну и ту же сущность.
// Род: шаблон - правило над видами
// Это уже уровень "родов": Pair<T, U> -- не конкретный вид,
// а правило, которое двум видам сопоставляет новый вид
template<typename T, typename U>
struct Pair {
T first;
U second;
};
// Функция, работающая на уровне рода: для любого вида T
// возвращает пару из двух элементов этого вида
template<typename T>
Pair<T, T> make_pair_of(T a, T b) {
return {a, b};
}Сократа можно одновременно рассматривать как экземпляр вида "человек" и как представителя родов "млекопитающее" и "двуногое" и важно понимать, что любая сущность принадлежит ровно одному виду, который задает правила ее построения или существования, но может принадлежать многим родам, каждый из которых описывает только один аспект её свойств, и ровно так же в программировании: объект одного конкретного типа может реализовывать множество интерфейсов или концептов, каждый из которых подчеркивает только часть его поведения.
Типы в C++ как виды
Если перекинуть мостик от этой философской картины мира к нашему миру компиляторов и C++, то можно увидеть, что тип в языке играет роль как конкретного вида, так и абстрактного вида, в зависимости от уровня, на котором мы смотрим.
С точки зрения программы – класс:
struct Person {
std::string name;
int age;
};задаёт вид "человек в нашей модели", определяя набор атрибутов, которые мы выбрали существенными: имя и возраст, а объект:
Person p{"Socrat", 70};— это конкретная сущность, один человек в нашей программе, имеющий свои значения атрибутов на текущий момент времени.
С точки зрения теории типов в компиляторе "тип" ближе к абстрактному виду: компилятор работает не с конкретным p, а с множеством всех возможных значений типа Person, знает их размер, структуру, правила копирования и разрушения, и проверяет, корректно ли вы применяете функции (в нашем смысле — правила) к сущностям соответствующих видов, то есть не передаете ли вы в функцию, ожидающую double, объект std::string, и наоборот.
Эволюция представления типов в компиляторах
Исторически разные компиляторы по‑разному реализовывали эту модель на уровне внутреннего представления программ, но концептуальная картина всегда была похожей: во внутренних структурах данных компилятора есть сущности, которые соответствуют абстрактным видам и родам — это узлы дерева типов, таблицы информации о классах, функциях и шаблонах; есть сущности, которые соответствуют конкретным сущностям — это переменные, объекты, временные значения, которые появляются и исчезают при выполнении программы; и есть функции, которые в виде промежуточного представления (IR, intermediate representation) превращаются в набор правил преобразования одних значений в другие.
В ранних компиляторах вроде cfront многие из этих вещей были закодированы в текстовом C‑коде, получающемся на выходе транслятора, и понятия вида и рода существовали только в голове автора и в его дизайне. По мере развития GCC, Clang и MSVC появились всё более сложные системы типов и проверки, которые формализуют эти категории и позволяют, например, на уровне IR LLVM говорить о типе как о чётко определённом "виде" значений, для которого можно проверять эквивалентность, совместимость и допустимость тех или иных операций.
┌───────────────────────────────────────────────────────────────────────┐
│ cfront (1983-1993) - Трансляция в C │
├───────────────────────────────────────────────────────────────────────┤
│ C++ код: Вывод cfront (C код): │
│ ┌─────────────────────┐ ┌──────────────────────────┐ │
│ │ struct Person { │ │ struct Person { │ │
│ │ string name; │ → │ struct string name; │ │
│ │ int age; │ │ int age; │ │
│ │ │ │ }; │ │
│ │ void greet(); │ │ │ │
│ │ }; │ │ void Person_greet( │ │
│ │ │ │ struct Person* this │ │
│ │ Person p; │ │ ) { ... } │ │
│ │ p.greet(); │ │ │ │
│ └─────────────────────┘ │ struct Person p; │ │
│ │ Person_greet(&p); │ │
│ └──────────────────────────┘ │
│ Информация о типах: │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ • Существует только в голове программиста и в │ │
│ │ комментариях к коду │ │
│ │ • C компилятор видит только struct Person │ │
│ │ • Методы → обычные функции с this* │ │
│ │ • Проверка типов минимальная (только на уровне C) │ │
│ └──────────────────────────────────────────────────────────┘ │
└───────────────────────────────────────────────────────────────────────┘
┌───────────────────────────────────────────────────────────────────────┐
│ GCC/Clang (2000+) - Формальная система типов │
├───────────────────────────────────────────────────────────────────────┤
│ C++ код → AST → Type System → LLVM IR → Machine Code │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ C++ Source │ → │ AST │ → │ IR │ │
│ ├──────────────┤ ├──────────────┤ ├──────────────┤ │
│ │ struct Person│ │ RecordDecl │ │ %Person = │ │
│ │ { │ │ name: │ │ type { │ │
│ │ string name│ │ FieldDecl │ │ %string, │ │
│ │ int age; │ │ Type: │ │ i32 │ │
│ │ }; │ │ string │ │ } │ │
│ │ │ │ age: │ │ │ │
│ │ Person p; │ │ FieldDecl │ │ %p = alloca │ │
│ │ p.greet(); │ │ Type: int│ │ %Person │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ Информация о типах хранится в структурах данных компилятора: │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ Type Database: │ │
│ │ ┌──────────────────────────────────────────────────────┐ │ │
│ │ │ Type: Person │ │ │
│ │ │ ├─ Size: 32 bytes │ │ │
│ │ │ ├─ Alignment: 8 │ │ │
│ │ │ ├─ Members: │ │ │
│ │ │ │ ├─ name: string at offset 0 │ │ │
│ │ │ │ └─ age: int32 at offset 24 │ │ │
│ │ │ ├─ Methods: │ │ │
│ │ │ │ └─ greet(): void │ │ │
│ │ │ ├─ Copy Constructor: auto-generated │ │ │
│ │ │ ├─ Destructor: calls ~string() │ │ │
│ │ │ └─ Move semantics: auto-generated │ │ │
│ │ └──────────────────────────────────────────────────────┘ │ │
│ │ │ │
│ │ Проверки: │ │
│ │ • greet(Person) ← alice:Person OK │ │
│ │ • greet(Person) ← x:double ERROR │ │
│ │ • person.name ← "text" OK (string = char*) │ │
│ │ • person.age ← "text" ERROR (int ≠ char*) │ │
│ └────────────────────────────────────────────────────────────┘ │
└───────────────────────────────────────────────────────────────────────┘Значения
Когда вы запускаете программу и смотрите на память с точки зрения процессора, то никакого C++, никаких типов и даже никаких чисел там нет, а есть только длинные последовательности нулей и единиц. Процессор, не знает, что такое «целое число 42», «вещественное 3.14» или «символ 'A'»: для него всё это лишь разные способы интерпретировать одни и те же биты.
Пока у нас нет интерпретации этих данных, мы видим просто нули и единицы, как последовательность битов, а всё остальное, как результат соглашения между программистом, компилятором и архитектурой о том, как эти биты понимать.
Тип значения как мост
Тип значения в этом контексте можно представить как мост между абстрактным миром математических сущностей и очень конкретным миром битовых последовательностей, где с одной стороны, у нас есть вид абстрактных вещей (в виде целых чисел или рациональных чисел), а с другой стороны, есть множество всех возможных битовых строк нужной длины, и тип значения говорит, какие именно битовые строки мы считаем корректными представлениями сущностей данного вида, а какие нет.
Если у нас есть конкретная сущность, скажем, целое число «минус пять», то набор битов, которым мы её кодируем в памяти, называется представлением этой сущности, а сама сущность, то есть число как математический объект, является интерпретацией этих данных. Когда мы говорим "значение", мы имеем в виду данные вместе с их интерпретацией: не просто "32 бита 1111…", а "это 32-битное знаковое целое в дополнительном коде со значением -5" или "это пара 32-битных целых, интерпретируемых как числитель и знаменатель рационального числа".
Корректность представления
Например, обычный int на многих платформах — это 32 бита в дополнительном коде (two's complement), где битовый набор 0x00000001 интерпретируется как число 1, а 0xFFFFFFFF как -1. Рациональное число можно представить как конкатенацию двух таких 32-битных целых, но важно понимать, что не всякая последовательность битов является осмысленным представлением для произвольного типа значения. Можно говорить, что данные корректно сформированы относительно типа, если они действительно представляют какую-то абстрактную сущность этого вида.
Любая 32-битная последовательность, если мы договорились интерпретировать её как целое в дополнительном коде (two's complement), будет корректно сформированной: каждый битовый набор соответствует какому-то целому от минимального до максимального. Но если мы берём тип "вещественное число в смысле математического представления" и пытаемся интерпретировать произвольное значение IEEE 754, то, встретив NaN, мы сталкиваемся с битами, которые по стандарту IEEE 754 означают "Not a Number", и с точки зрения чистой математики они не являются корректно сформированным представлением вещественного числа, хотя как элемент типа "machine float" они вполне легальны.
Именно поэтому в языке C++ стандарт так различает "битовый набор NaN" и "значение типа double" как абстрактные сущности, поэтому компилятор и процессор физически умеют хранить и передавать NaN не испытывая каких-то проблем, но математические функции для NaN могут быть не определены.
// Каждый из этих битовых наборов осмыслен как int
uint32_t bits1 = 0x00000001u;
uint32_t bits2 = 0xFFFFFFFFu;
int32_t a, b;
std::memcpy(&a, &bits1, 4); // 1
std::memcpy(&b, &bits2, 4); // -1 (дополнительный код)Полнота и частичность типов
Дальше возникает вопрос: насколько полно наш тип значения покрывает соответствующий абстрактный вид. Если тип представляет только часть возможных сущностей, мы называем его "собственно частичным"; если же каждую абстрактную сущность этого вида можно выразить значением данного типа, то тип полон.
Хороший пример собственно частичного типа — обычный int, который представляет только конечный диапазон целых чисел, хотя множество математических целых бесконечно; тип bool, напротив, полон для вида логических значений, потому что любые абстрактные "истина" и "ложь" однозначно отображаются в два возможных значения: true и false.
Исторически компиляторы по-разному ограничивали диапазон int: на 16-битных системах это были диапазоны порядка -32768…32767, на 32-битных и 64-битных — значительно шире, но во всех случаях int оставался частичным представлением абстрактного вида "целое число", и программистам приходилось помнить о переполнении и о том, что далеко не каждое математическое выражение имеет корректное представление в этом типе.
y = nan
y + 1 = nan
y * 0 = nan
y == y = 0
sqrt(-1) = nanУникальность представления
Отдельная и очень важная для практики тема — уникальность представления, то есть вопрос о том, соответствует ли каждой абстрактной сущности не более одного значения данного типа. Если у нас тип логического значения, реализованный как байт, где ноль — ложь, а любое ненулевое значение трактуется как истина, то представление не уникально: и 0x01, и 0xFF, и 0x7F интерпретируются как true, и равенство по смыслу не совпадает с равенством по битовому содержимому.
Тип, представляющий целое число в виде "знаковый бит плюс модуль", тоже не имеет уникального представления нуля, потому что и "+0", и "-0" оказываются разными битовыми наборами с одинаковой интерпретацией.
Формат дополнительного кода (two's complement), наоборот, имеет уникальное представление: каждое целое в допустимом диапазоне кодируется ровно одним набором битов, и ноль не имеет варианта "+0"/"-0". Компиляторы и процессоры любят такие типы с уникальным представлением, потому что операция равенства для них тривиально реализуется как побитовое сравнение, а оптимизатор может применять массу приёмов, основываясь на том, что замена равного на равное сохраняет и биты, и смысл.
Неоднозначность представления
Но бывает и наоборот: иногда мы сознательно выбираем представление без уникальности или даже с неоднозначностью, если одно и то же значение может иметь более одной интерпретации, то есть по битам нельзя однозначно восстановить абстрактную сущность без дополнительного контекста.
Пример, который любят приводить, — календарный год, закодированный двумя десятичными цифрами: "42" может означать 1942, 2042 или ещё какой‑то год в зависимости от века; здесь одна и та же последовательность данных допускает несколько интерпретаций, и тип сам по себе неоднозначен. В повседневной работе это проявляется, когда вы храните даты без явного указания часового пояса — биты занимают меньше места, вычисления идут быстрее, но равенство по битам перестаёт гарантировать равенство по смыслу, и в обратную сторону, равные по смыслу сущности могут иметь разные представления.
Два вида равенства
Чтобы аккуратно различать эти ситуации, удобно различать два вида равенства: равенство как совпадение интерпретаций и "представительное" равенство как дословное совпадение битовых последовательностей. Два значения одного типа равны, если они описывают одну и ту же абстрактную сущность; они представительно равны, если последовательности нулей и единиц в их памяти идентичны.
Если у типа есть уникальное представление, то равенство по смыслу автоматически влечёт равенство по битам, потому что для каждой сущности существует только одно законное представление. Если тип не является неоднозначным, то есть каждая битовая последовательность соответствует не более чем одной сущности, то наоборот, представительное равенство влечёт равенство по смыслу: одинаковые биты — одинаковая сущность.
Именно поэтому для типов вроде обычного int в дополнительном коде (two's complement) или double (за исключением NaN) компиляторы спокойно реализуют оператор == как либо прямое сравнение битов, либо как одну-две машинные инструкции сравнения, и оптимизатор может заменять сравнение на более дешёвые проверки, не боясь нарушить семантику.
Компромиссы в представлении
Но в реальной жизни мы часто сталкиваемся с типами, где уникальность представления сознательно нарушена ради эффективности операций создания и преобразования значений. Рациональные числа, хранящиеся как пары целых числителя и знаменателя без автоматического сокращения дроби, — классический пример: 1/2 и 2/4 представляют одну и ту же абстрактную сущность, но имеют разные представительные формы, и чтобы проверить их равенство по смыслу, нужно либо привести обе дроби к несократимому виду, либо перемножить и сравнить произведения, что намного дороже простого сравнения двух пар битовых узоров.
// Полный тип для ограниченного вида
// Если вид сам конечен -- тип может быть полным.
// Масть карты: ровно 4 сущности, ровно 4 значения enum.
enum class Suit { Clubs, Diamonds, Hearts, Spades };
// Неуникальное представление
struct Rational {
int64_t num; // числитель
int64_t den; // знаменатель (> 0)
bool naive_eq(...) // быстрая наивная реализация
bool normalized_eq(...) // медленная проверка с нормализацией
bool cross_eq(...) // медленная проверка с перемножением
};
auto a = Rational::make(1, 2); // 1/2
auto b = Rational::make(2, 4); // 2/4 -- та же абстрактная сущность
cout<<"1/2 naive_eq 2/4:"<<a.naive_eq(b)<<"\n"; // 0 -- неверно!
cout<<"1/2 normalized_eq 2/4:"<<a.normalized_eq(b)<<"\n"; // 1
cout<<"1/2 cross_eq 2/4:"<<a.cross_eq(b)<< "\n"; // 1Аналогично, конечные множества можно хранить как неотсортированные списки элементов, где проверка равенства множеств требует сортировки и удаления дубликатов, прежде чем можно будет сравнивать элемент за элементом. В таких ситуациях проектировщик представления сознательно идёт на то, чтобы удешевить создание и модификацию значений за счёт удорожания проверки равенства, если последняя считается редкой операцией. Исторически во многих стандартных библиотеках можно найти следы таких компромиссов: от старых реализаций std::set и std::multiset, где сравнение значений было дешевым, но операции вставки дороже, до экспериментальных структур вроде хеш‑множества, где, наоборот, операции вставки и проверки принадлежности оптимизировались за счёт более сложной схемы равенства и хеширования.
// Представление 1: Неотсортированный список
// Быстрая вставка O(1), медленное сравнение O(n log n)
struct UnsortedSet {
std::vector<int> elements;
// Вставка - O(1), просто добавляем в конец
void insert(int x) {
elements.push_back(x);
}
// Равенство - O(n log n), нужно сортировать
bool operator==(const UnsortedSet& other) const {
// Копируем и сортируем для сравнения
auto a = elements;
auto b = other.elements;
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
// Удаляем дубликаты
a.erase(std::unique(a.begin(), a.end()), a.end());
b.erase(std::unique(b.begin(), b.end()), b.end());
return a == b;
}
};
// Представление 2: Отсортированный список (без дубликатов)
// Медленная вставка O(n), быстрое сравнение O(n)
struct SortedSet {
std::vector<int> elements; // Всегда отсортирован!
// Вставка - O(n), нужно поддерживать порядок
void insert(int x) {
auto it = std::lower_bound(elements.begin(), elements.end(), x);
if (it == elements.end() || *it != x) {
elements.insert(it, x); // O(n) из-за сдвига элементов
}
}
// Равенство - O(n), просто сравниваем поэлементно
bool operator==(const SortedSet& other) const {
return elements == other.elements; // Линейное сравнение
}
};Неразрешимость поведенческого равенства
Иногда, реализовать "настоящее" поведенческое равенство слишком дорого или даже теоретически невозможно: если вы представляете вычислимую функцию как некоторый кусок кода или структуру данных, описывающую алгоритм, то понятие "две функции равны, если они дают одинаковый результат на всех возможных аргументах" оказывается неисчислимым.
В общем случае невозможно алгоритмически проверить, что два произвольных алгоритма ведут себя одинаково на всей области определения и тогда на практике приходится довольствоваться более слабым понятием равенства — сравнением представлений, когда два значения считаются равными, только если их битовые образы совпадают, что соответствует тому, что это просто один и тот же объект в памяти или точная копия. Если вернуться к функциям, то можно сказать так – компьютеры реализуют математические функции над абстрактными сущностями через конкретные процедуры над значениями, то есть над битами плюс их интерпретацией.
Независимость от адресов
Хотя значения живут в памяти и имеют адреса, корректно реализованная функция должна вести себя так, будто ей безразлично, по каким адресам лежат аргументы, и интересоваться только их содержанием как значений, и если мы скопируем значение в другое место, результат применения функции к старой и новой копии должен быть одинаков.
Когда мы говорим, что функция определена на типе значений и является регулярной, мы имеем в виду, что она "уважает" равенство: если заменить аргумент на любое другое равное ему значение, результат функции не изменится. Большинство привычных числовых функций, таких как sin, cos, + или *, при аккуратной реализации и настройке режима округления ведут себя именно так: если два double действительно представляют одно и то же вещественное число, то результат сложения или умножения с любыми третьими аргументами будет равен по смыслу.
С точки зрения теории типов и оптимизатора компилятора это очень важное замечание, потому что такие функции позволяют применять подстановку, то есть заменять выражения на равные им без изменения поведения программы, а нерегулярные функции этого не допускают, потому что внутри них выбор результата может зависеть от того, каким именно битовым образом записано значение.
double pos_zero = 0.0;
double neg_zero = -0.0;
cout<<"\n+0.0 == -0.0:"<<(pos_zero == neg_zero)<<"\n";
// 1 -- равны по ==
cout<<"signbit(+0.0):"<<std::signbit(pos_zero)<<"\n";
// 0
cout<<"signbit(-0.0):"<<std::signbit(neg_zero)<<"\n";
// 1 -- разный результат!
// signbit нарушает регулярность:
// заменили равное на равное, но результат изменилсяПроблемы оптимизации с плавающей точкой
В истории компиляторов для C++ это различие многократно всплывало в дискуссиях о допустимых оптимизациях: можно ли, например, переупорядочивать вычисления с плавающей точкой или заменять выражения на эквивалентные с математической точки зрения, если формат IEEE 754 и наличие NaN, бесконечностей и тонкостей с округлением делают многие привычные тождества, вроде ассоциативности сложения, ложными.
float a = 1e15, b = -1e15, c = 1.5;
float left = (a + b) + c; // (1e15 - 1e15) + 1.5 = 0 + 1.5 = 1.5
float right = a + (b + c); // 1e15 + (-1e15 + 1.5) -- потеря точности
std::cout << "\n(a+b)+c = " << left << "\n"; // 1.5
std::cout << "a+(b+c) = " << right << "\n"; // может отличаться!
std::cout << "Равны: " << (left == right) << "\n";
// С -ffast-math компилятор мог переставить и получить иной результат
// Вывод:
// (a+b)+c = 1.5
// a+(b+c) = 0
// Равны: 0Комитет стандарта и разработчики компиляторов искали баланс между желанием агрессивно оптимизировать код и необходимостью сохранить корректность для тех функций и типов, которые программист считает регулярными, и в результате появились режимы вроде -ffast-math в GCC и Clang, которые сознательно ослабляют гарантию регулярности ради производительности.
В итоге при проектировании представления любого типа значений две задачи неизбежно идут рука об руку: нужно решить, какое равенство вы хотите иметь — битовое или поведенческое, с уникальным представлением или без — и какие функции над этим типом вы хотите оставить регулярными, чтобы компилятор и вы сами могли безопасно применять закон "подставь равное вместо равного". В языке C++ это проявляется в самых разных местах, от выбора формата чисел и строк до дизайна классов-оберток и контейнеров, и компиляторы, эволюционируя от простых однопроходных трансляторов до современных многоступенчатых оптимизаторов, всё больше опираются на эти свойства типов, чтобы генерировать быстрый и при этом корректный код.
Объекты
Когда мы в программировании произносим слово «объект», очень легко сразу прыгнуть к классам, методам и всякой ООП‑атрибутике, хотя на самом деле всё начинается гораздо ниже — с самой памяти и того, как в ней живут биты. Представьте себе память как большое поле ячеек, где каждая ячейка имеет адрес и содержимое: адрес и содержимое (длина данных) — тоже число, и чтобы прочитать слово по адресу, процессор выполняет операцию чтения, load, а чтобы изменить связь между адресом и содержимым, он делает запись, store. В современных машинах роль такой памяти играют области в оперативной памяти, а на уровне хранения на диске ту же модель реализуют блоки (логические области хранения) на SSD или HDD, только с другими задержками и правилами работы, но принцип тот же: есть адрес, есть содержимое, есть операции чтения и записи.
Объект как договор
На этом фоне объект можно понять как договор между программистом, компилятором и машиной: это способ представить конкретную сущность из нашего предметного мира в виде значения, живущего в памяти. У каждого объекта есть состояние, и это состояние — просто значение некоторого типа значений. Если объект описывает, скажем, сотрудника, то его состояние в текущий момент — это "снимок" всех атрибутов, которые мы решили хранить: имя, зарплата, идентификатор отдела.
Это состояние может меняться во времени, и именно этим объект отличается от простого значения, потому что значение само по себе, как математическое представление, неизменно, а объект способен в разные моменты времени иметь разные значения. Чтобы хранить своё состояние, объект владеет набором ресурсов — это могут быть слова памяти в куче, записи в файле, элементы в базе данных; в простейшем случае это просто несколько байтов подряд в динамической памяти.
Array of Structures vs Structure of Arrays
// ============================================
// Вариант 1: Array of Structures (AoS)
// Классическое представление - данные объекта лежат рядом
// ============================================
struct Complex_AoS {
double real;
double imag;
};
void example_aos() {
std::vector<Complex_AoS> numbers = {
{1.0, 2.0}, // первое комплексное число
{3.0, 4.0}, // второе
{5.0, 6.0} // третье
};
// Обращение естественное - всё рядом
std::cout << "AoS: " << numbers[1].real << " + "
<< numbers[1].imag << "i\n";
}===================================================================
ARRAY OF STRUCTURES (AoS) - классическое представление
===================================================================
Память (байты идут подряд):
┌─────────────────┬─────────────────┬─────────────────┐
│ Complex[0] │ Complex[1] │ Complex[2] │
├────────┬────────┼────────┬────────┼────────┬────────┤
│ real: │ imag: │ real: │ imag: │ real: │ imag: │
│ 1.0 │ 2.0 │ 3.0 │ 4.0 │ 5.0 │ 6.0 │
└────────┴────────┴────────┴────────┴────────┴────────┘
0x1000 0x1010 0x1020 0x1030При этом надо понимать, что хотя мы логически думаем о значении объекта как о непрерывной последовательности нулей и единиц, физически ресурсы, в которых эти биты хранятся, не обязаны идти подряд: классический пример — комплексное число как пара double, реальная и мнимая часть, которые в памяти могут лежать рядом, а могут быть разнесены по разным структурам или массивам, и всё равно интерпретация будет собирать их в одно логическое целое. Если мы вручную перешли от массива структур {re, im}[] к двум отдельным массивам re[] и im[], то поля одного логического объекта физические живут в разных регионах памяти, являясь одним объектом, только по соглашению об интерпретации.
// ============================================
// Вариант 2: Structure of Arrays (SoA)
// Данные одного логического объекта разнесены по памяти
// ============================================
struct ComplexArray_SoA {
std::vector<double> real; // все реальные части подряд
std::vector<double> imag; // все мнимые части подряд
size_t size() const { return real.size(); }
// Логический "объект" с индексом i - это пара (real[i], imag[i])
// но физически они живут в разных массивах
struct ComplexRef {
double& re;
double& im;
ComplexRef(double& r, double& i) : re(r), im(i) {}
// Ведёт себя как объект, но данные не рядом!
void print() const {
std::cout << re << " + " << im << "i\n";
}
};
ComplexRef operator[](size_t i) {
return ComplexRef(real[i], imag[i]);
}
};
void example_soa() {
ComplexArray_SoA numbers;
numbers.real = {1.0, 3.0, 5.0};
numbers.imag = {2.0, 4.0, 6.0};
// Обращение к "объекту" с индексом 1
// Физически поля в разных местах, логически - один объект
std::cout << "SoA: ";
numbers[1].print();
}===================================================================
STRUCTURE OF ARRAYS (SoA) - разнесённое представление
===================================================================
Память (массивы в разных местах):
Массив real[] (все реальные части):
┌────────┬────────┬────────┐
│ 1.0 │ 3.0 │ 5.0 │ ← real[0], real[1], real[2]
└────────┴────────┴────────┘
0x2000 0x2008 0x2010
Массив imag[] (все мнимые части):
┌────────┬────────┬────────┐
│ 2.0 │ 4.0 │ 6.0 │ ← imag[0], imag[1], imag[2]
└────────┴────────┴────────┘
0x3000 0x3008 0x3010
Логический объект Complex[1] = {real[1], imag[1]}
= {3.0 из 0x2008, 4.0 из 0x3008}В распределённых системах ресурсы одного логического объекта могут вообще оказаться в разных видах памяти — часть в оперативке, часть на диске или в удаленном хранилище, но обычно при описании объекта мы подразумеваем один процесс, одно адресное пространство, уникальный начальный адрес и фиксированные смещения до всех его частей.
Тип объекта
Тип объекта в такой картине мира — это шаблон того, как мы храним и меняем значения в памяти и можно сказать, что для каждого типа объекта существует соответствующий тип значения, который описывает все допустимые состояния объектов этого типа.
Если мы договорились, что наш объект — это 32‑битное знаковое целое в формате дополнительного кода с порядком байтов little‑endian и выравниванием по границе 4 байта, то мы тем самым задали конкретный тип объекта: компилятор знает, какой размер у него в байтах, где он может располагаться в памяти, какие инструкции процессора использовать для загрузки и записи, а тип значения для этого объекта — это множество всех целых чисел в допустимом диапазоне.
Любой конкретный объект "int" в программе принадлежит этому типу объекта: его состояние — это некоторое конкретное значение, а его физическая реализация — это набор байтов в памяти, к которым компилятор обращается по известному смещению от начального адреса. Важный момент, который полезно осознать при первых попытках писать код – что значения и объекты взаимодополняющие, но принципиально разные по ролям.
Значения vs объекты
Значения как математические сущности неизменны и не зависят от того, как мы их закодировали в памяти; вы можете записать число 42 на бумаге, передать его устно, отправить по сети в виде текста или в виде двоичного формата — само значение от этого не изменится.
Объекты, наоборот, привязаны к конкретной машине и реализации: у них есть адрес, набор байтов, механика изменения, и они могут переходить из одного состояния в другое в течение жизни программы.
Но тем не менее состояние любого объекта в конкретный момент всегда можно описать значением: вы можете взять объект std::string, посмотреть на его логическое значение как последовательность символов, записать её на бумагу или сериализовать в JSON — это и будет "снимок" состояния объекта.
Когда мы обсуждаем равенство объектов, мы чаще всего хотим говорить именно о равенстве их состояний как значений, абстрагируясь от того, что один std::string хранит свои данные в одном участке памяти, а другой — в другом. Такой взгляд особенно важен в чисто функциональных языках, где вообще нет изменяемых объектов, а есть только значения и функции, но и в C++ он позволяет отделить "что" от "как" и не привязывать всё к конкретным адресам.
Почему мы используем объекты?
Во‑первых, объекты очень естественно моделируют изменяемые конкретные сущности реального мира: запись о сотруднике в базе данных, объект персонажа в игре, состояние окна в GUI — всё это конструкции, которые меняются по мере работы программы, и объект с изменяемым состоянием описывает их близко к реальности.
Во‑вторых, даже когда нас интересуют чисто абстрактные значения, вроде квадратного корня числа или решения системы линейных уравнений, мы почти всегда реализуем эти функции через алгоритмы, которые используют изменяемую память: итерационные методы, накопление промежуточных сумм и т.п., и объекты в этом смысле служат мощным инструментом для реализации функций над значениями.
В‑третьих, если смотреть совсем фундаментально, то универсальная модель вычислений по Тьюрингу подразумевает машину с памятью, и реальный компьютер — это именно такая машина, поэтому любые практические реализации вычислений всё равно сводятся к манипулированию объектами в памяти, даже если на уровне языка это замаскировано под "чистые функции".
Свойства типов объектов
Часть свойств для типов значений, переносится и на типы объектов. Если значение корректно сформировано — то есть его двоичное представление допустимо для выбранного типа — то и объект с таким состоянием корректен; если тип значений собственно частичен, представляя только часть возможных абстрактных сущностей (как int по отношению ко всем целым), то и тип объектов, реализующий этот int, будет частичным; если тип значений обладает уникальным представлением, как two's complement для целых, то и для объектов этого типа равенство по смыслу можно реализовать через сравнение байтов, что исторически очень важно для оптимизации, потому что компиляторы вроде GCC и Clang умеют сводить сравнение объектов POD‑типов к простому memcmp, когда знают, что представление уникально и нет "дыр" с неинициализированными битами, или пойти дальше и заменить memcmp на прямое сравнение регистров или векторные инструкции, но следует помнить, что чистый перенос operator== → memcmp для структур с возможным паддингом ведет к потенциальным багам.
Понятие идентичности
Отдельного разговора заслуживает идентичность объектов, потому что в реальном мире конкретные сущности обладают идентичностью и Сократ останется Сократом независимо от того, перекрасил ли он волосы, сменил адрес или умер, а государство остаётся тем же государством, даже если меняет флаг или конституцию или размер населения.
Чтобы отразить это в программе, объекты, представляющие конкретные сущности, нуждаются в своём определении идентичности, которая отделена от текущего состояния. Удобный способ ввести такую идентичность — это токен идентичности, уникальное значение, которое выражает "кто это", а не "в каком он сейчас состоянии". Таким токеном может быть, например, адрес объекта в памяти, индекс в массиве, где он хранится, или табельный номер сотрудника в кадровой системе и проверяя равенство токенов идентичности, мы фактически проверяем тождественность объектов: один и тот же объект или разные.
На протяжении жизни программы конкретный объект может менять свои токены идентичности, потому что его могут переместить в другой участок памяти или переложить из одного контейнера в другой, или назначить ему новый идентификатор, но логическая идентичность сохраняется, если мы поддерживаем сопоставление между "старым" и "новым" токеном.
Равенство vs тождественность
Наконец, стоит провести чёткую линию между равенством объектов и их тождественностью. Два объекта одного и того же типа равны, если их состояния равны как значения: два std::string, оба содержащие "hello", равны, даже если лежат в разных местах памяти и имеют разные внутренние буферы; два вектора std::vector<int>, содержащие одинаковые последовательности, равны как последовательности значений.
В этом случае естественно говорить, что один объект является копией другого, а любые изменения, сделанные в одном, не затрагивают копию. Проверка равенства здесь опирается на модель значений, а не на адреса, а тождественность же отвечает на другой вопрос - "это тот же самый объект или просто другой объект с таким же состоянием?".
В ранних компиляторах и рантаймах C++ вопрос о равенстве и тождественности был тесно связан с тем, как реализованы копирование и перемещение и старые реализации могли неожиданно "делить" внутренние буферы между объектами, например для std::string через copy-on-write, и приходилось осторожно относиться к тому, что именно означает "копия", но по мере развития стандарта и реализации компиляторы и библиотеки стали гораздо более строгими в трактовке равенства по состоянию и тождественности по идентичности, что упростило рассуждения о корректности кода.
// GCC до C++11 с COW строками:
std::string s1 = "hello";
std::string s2 = s1; // Буфер НЕ копируется!
// s1 и s2 указывают на ОДИН буфер в памяти
// Внутри счётчик ссылок = 2
// При модификации:
s2[0] = 'H'; // Только СЕЙЧАС буфер копируется (Copy-On-Write)Схема COW string:
После копирования:
s1: [ptr] ──┐
├──→ [refcount:2][h][e][l][l][o][\0]
s2: [ptr] ──┘
После модификации s2:
s1: [ptr] ────→ [refcount:1][h][e][l][l][o][\0]
s2: [ptr] ────→ [refcount:1][H][e][l][l][o][\0]
(новый буфер)Эволюция реализаций объектов
И разные компиляторы по-разному реализовывали эти идеи: так в раннем cfront объект фактически был структурой C, адрес которой играл роль токена идентичности, а различие между значением и объектом во многом жило только в комментариях и документации. А в Borland C++ и ранних MSVC реализация объектов была тесно завязана на модель памяти конкретной платформы: выравнивание, порядок байтов, соглашения о расположении полей в структурах, и программистам приходилось явно учитывать, как именно их "абстрактные" объекты будут жить в конкретной памяти x86.
// C++ код:
class Point {
int x, y;
public:
void move(int dx, int dy);
};
// cfront транслировал примерно в:
struct Point {
int x, y;
};
void Point_move(struct Point *this, int dx, int dy);
// Адрес = идентичность
Point p1, p2;
// &p1 и &p2 - это токены идентичностиСовременные компиляторы вроде GCC, Clang и MSVC уже имеют богатые внутренние представления типов и значений, часто поверх промежуточного представления вроде LLVM IR, где идея "объект как источник изменяемого состояния" и "значение как неизменная сущность" чётко разведены, и оптимизатор может, например, временно превращать объект в набор значений в регистрах, если видит, что между его обновлениями нет "наблюдателей", а затем обратно материализовывать его в память.
// C++ код:
struct Point { int x, y; };
void foo() {
Point p;
p.x = 10;
p.y = 20;
use(p.x + p.y);
}
// Без оптимизаций (объект в памяти):
; %p = alloca Point
; store 10, p.x
; store 20, p.y
; load p.x, load p.y
// После оптимизаций (объект стал значениями в регистрах):
; %x = 10
; %y = 20
; %sum = add %x, %y
; (объекта Point в памяти вообще нет)Но для нас полезно держать в голове простую картину: память — это адреса и слова, значение — это интерпретация последовательности битов, объект — это место в памяти, где это значение живёт и может меняться, а тип — это договор о том, как мы эти биты храним, читаем, модифицируем и сравниваем.
Процедуры
Когда мы переходим от значений и объектов к поведению программы и что вообще делает программу программой, то на сцене появляется еще одна фундаментальная категория — процедуры. В привычном C++ это просто функция, но в более общем смысле можно сказать так: процедура — это некоторая последовательность правил, которая меняет состояние объектов, с которыми она работает, а иногда ещё и создаёт новые объекты или уничтожает старые.
Исторически компиляторы начинали с очень примитивного понимания процедур: в раннем Fortran и первых версиях C процедура была просто именованным отрывком кода с фиксированным набором аргументов, и вся "магия" состояла в том, чтобы правильно сгенерировать вход и выход из неё — пролог и эпилог, сохранить регистры, организовать стек.
Категории объектов процедуры
По мере развития языков и компиляторов стало ясно, что ключевым вопросом здесь является не столько синтаксис, сколько то, как именно процедура взаимодействует с объектами: какие она читает, какие модифицирует, какие живут только во время вызова, а какие переживают множество вызовов и даже весь срок жизни программы. Если попытаться разложить это взаимодействие на понятные категории, можно выделить четыре группы объектов, с которыми имеет дело практически любая процедура.
Во‑первых, это "вход и выход/in-out", то есть объекты, которые передаются в процедуру и из неё либо напрямую, либо косвенно. Прямо — это когда вы пишете int f(int x) и компилятор передаёт значение x по регистрам или по стеку, а потом возвращает результат, скажем, тоже в регистре; косвенно — когда вы передаете указатель или ссылку, вроде void increment(int* p), и процедура работает с объектом не как с копией значения, а как с оригиналом в памяти.
Во‑вторых, это локальное состояние: временные объекты, которые создаются в начале вызова процедуры, живут на стеке или в регистрах, подстраиваются под нужды алгоритма и уничтожаются, когда процедура завершает работу. Если вы в функции void foo() объявляете int tmp = 0; std::vector<int> v(10);, то и tmp, и v — часть локального состояния этой процедуры: они нужны ей для работы, но снаружи никто о них не знает и знать не должен.
И глобальное состояние: объекты, доступ к которым имеет не только эта процедура, но и другие, причём на протяжении многих вызовов — это глобальные переменные, статические поля, или объекты в динамической памяти, на которые есть ссылки из разных частей программы.
И наконец, есть ещё собственное состояние процедуры, то есть такие объекты, которые доступны только ей самой (и, возможно, тесно связанным функциям), но при этом сохраняются между вызовами. Простейший пример — static переменная внутри функции:
void counter() {
static int n = 0;
++n;
std::cout << n;
}и тогда n будет жить столько, сколько живёт программа, но использовать её сможет только counter, для всех остальных она как бы не существует, и это демонстрирует типичный паттерн "скрытого" состояния процедуры, который появился ещё в старом C задолго до классов.
Входы, выходы и вход/выход
Для того чтобы точнее говорить о поведении процедуры, нужно ввести ещё одно разделение: какие объекты считаются её входами, какие выходами, а какие и теми, и другими. Если процедура только читает значение объекта, никогда его не изменяя, то этот объект для неё — чистый вход; если же процедура создаёт объект, записывает в него данные или уничтожает его, не глядя на его прежнее содержимое, то такой объект выступает как выход и его начальное состояние неважно, важно только новое.
Самый интересный случай — когда объект и читается, и модифицируется: например, переданный по ссылке счётчик, который функция увеличивает, или элемент массива, который сначала проверяется на какое‑то условие, а потом обновляется. Такие объекты выступают как вход/выход процедуры, и именно они чаще всего становятся источником сложных эффектов и ошибок, если программист не до конца отдаёт себе отчёт, кто именно в программе имеет право менять их состояние.
В ранних компиляторах анализ этих категорий был практически полностью на совести программиста и компилятор просто принимал код как есть, но современные оптимизаторы компиляторов активно анализируют, какие переменные только читаются, какие пишутся и где возможны побочные эффекты, и уже на основе этого решают, какие вызовы можно изменить (reordering, cse, dce), какие преобразования допустимы, а какие нарушили бы ожидаемую семантику.
Вычислительная база
Переходя от процедур к идее вычислительной базы, надо понимать какие операции ваш тип вообще поддерживает. Для любого типа значений можно задать некоторый минимальный набор процедур, из которых, в принципе, можно построить все остальные операции над ним; такой набор называют вычислительной базой типа.
Например, для беззнаковых k-битных целых можно взять операции "получить ноль", "проверить равенство" и "перейти к следующему значению", и теоретически из них можно реализовать и сложение, и умножение, и сравнение, просто как очень длинные последовательности вызовов "следующего" и проверок.
Эффективность базы
Но здесь вступает в игру понятие эффективности: база считается эффективной, если любая процедура, построенная на её основе, может быть реализована не хуже, чем на любой другой разумной базе. В нашем примере с операцией "следующего" всё плохо: сложение двух k-битных чисел через многократное инкрементирование одного из них потребует порядка 2^k шагов в худшем случае, то есть будет заведомо медленным, тогда как реализация сложения на уровне машинных инструкций выполняется за фиксированное число тактов, не зависящее от значений аргументов.
Исторически, если посмотреть на эволюцию процессорных архитектур и компиляторов, видно, как набор базовых операций постепенно расширялся именно ради эффективности: от первых машин с очень ограниченным набором инструкций, где сложные операции приходилось эмулировать длинными последовательностями элементарных шагов, до современных архитектур с богатой системой арифметических и логических команд, для которых компиляторы умеют генерировать специализированный код и векторизованные версии алгоритмов.
Выразительность базы
Но одной эффективности мало; второй важной характеристикой базы является её выразительность. База называется выразительной, если с её помощью удобно и компактно определять процедуры над типом, особенно те, которые регулярно встречаются в практике.
Можно, конечно, сказать, что вычитание двух произвольных чисел — излишество, его можно реализовать через сложение с отрицанием, а отрицание — через вычитание из нуля, но если вы попытаетесь писать реальный код только с операциями "+", "0" и "next", то обнаружите, что многие определения становятся громоздкими и нечитаемыми. Поэтому, когда мы проектируем "выразительную" базу, мы добавляем в неё операции, которые логически выводимы из других, но практическая польза от их явного наличия гораздо выше, чем цена увеличения базы.
// ============================================
// МИНИМАЛЬНАЯ БАЗА (теоретически достаточная)
// ============================================
namespace MinimalBase {
using uint = unsigned int;
// Три примитива:
uint zero() { return 0; }
bool equal(uint a, uint b) { return a == b; }
uint next(uint a) { return a + 1; } // инкремент
// Всё остальное строим через эти три операции:
// Сложение через многократный инкремент - O(b) операций!
uint add(uint a, uint b) {
uint result = a;
for (uint i = zero(); !equal(i, b); i = next(i)) {
result = next(result);
}
return result;
}
// Умножение через многократное сложение - O(a*b) операций!
uint multiply(uint a, uint b) {
uint result = zero();
for (uint i = zero(); !equal(i, a); i = next(i)) {
result = add(result, b);
}
return result;
}
// Сравнение через вычитание (через многократный декремент)
// O(min(a,b))
bool less(uint a, uint b) {
while (!equal(a, zero()) && !equal(b, zero())) {
a = a - 1; // здесь нам нужен prev(), но его нет в базе
b = b - 1;
}
return !equal(b, zero());
}
}Так и в стандарте C++: язык формально можно было бы сделать очень минималистичным, но на практике ему нужны операторы вроде -, *, /, проверка <, >, стандартные функции над числами, чтобы программист мог выражать свои мысли понятно и коротко, а компилятор — переводить их на соответствующие машинные инструкции.
Эволюция вычислительной базы
═══════════════════════════════════════════════════════════════════════════
ВЫЧИСЛИТЕЛЬНАЯ БАЗА ДЛЯ UINT
═══════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────────────────────────────────────────┐
│ МИНИМАЛЬНАЯ БАЗА (теоретически полная, но непractical) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Примитивы (3 операции): │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ zero() │ │ equal() │ │ next() │ │
│ └──────────┘ └──────────┘ └──────────┘ │
│ │ │ │ │
│ └─────────────┴──────────────┘ │
│ │ │
│ ┌────────────▼────────────┐ │
│ │ ИЗ ЭТИХ ТРЁХ ОПЕРАЦИЙ │ │
│ │ МОЖНО ПОСТРОИТЬ ВСЁ │ │
│ └────────────┬────────────┘ │
│ │ │
│ ┌────────────▼────────────┐ │
│ │ add(a, b) = O(b) │ ← Неэффективно! │
│ │ for i=0; i<b; i++ │ 2^32 итераций в худшем случае │
│ │ a = next(a) │ │
│ └─────────────────────────┘ │
│ │
│ Проблема: Сложность операций ЗАВИСИТ от значений аргументов │
│ multiply(1000, 2000) = 2 миллиона вызовов next()! │
│ │
└─────────────────────────────────────────────────────────────────────────┘
▼
[Добавляем эффективность]
▼
┌─────────────────────────────────────────────────────────────────────────┐
│ ЭФФЕКТИВНАЯ БАЗА (добавляем операции для производительности) │
├─────────────────────────────────────────────────────────────────────────┤
│ Примитивы (7 операций): │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ zero() │ │ equal() │ │ next() │ │ add() │ O(1) │
│ └──────────┘ └──────────┘ └──────────┘ └──────────┘ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │subtract()│ │multiply()│ │ less() │ O(1) │
│ └──────────┘ └──────────┘ └──────────┘ │
│ Теперь все базовые операции - O(1), константное время! │
│ │
│ Как реализовано: │
│ add(a, b) → 1 инструкция CPU: ADD eax, ebx │
│ multiply(a, b) → 1-3 инструкции: IMUL eax, ebx │
│ less(a, b) → 1-2 инструкции: CMP eax, ebx; SETL cl │
│ │
└─────────────────────────────────────────────────────────────────────────┘
▼
[Добавляем выразительность]
▼
┌─────────────────────────────────────────────────────────────────────────┐
│ ВЫРАЗИТЕЛЬНАЯ БАЗА (добавляем операции для читаемости кода) │
├─────────────────────────────────────────────────────────────────────────┤
│ Все эффективные операции + │
│ Логически выводимые, но удобные: │
│ ┌────────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐ │
│ │not_equal() │ │less_equal()│ │ greater() │ │greater_eq()│ │
│ └────────────┘ └────────────┘ └────────────┘ └────────────┘ │
│ │ │ │ │ │
│ └────────────────┴────────────────┴────────────────┘ │
│ │ │
│ Можно выразить через equal() и less(): │
│ not_equal(a,b) = !equal(a,b) │
│ greater(a,b) = less(b,a) │
│ │
│ ┌────────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐ │
│ │ divide() │ │ modulo() │ │ max() │ │ min() │ │
│ └────────────┘ └────────────┘ └────────────┘ └────────────┘ │
│ │ │ │ │ │
│ └────────────────┴────────────────┴────────────────┘ │
│ │ │
│ Можно выразить через базовые операции: │
│ max(a,b) = greater(a,b) ? a : b │
│ │
│ ┌──────────────────────────────────────────────────────┐ │
│ │ ПРЕИМУЩЕСТВО: Код становится читаемым и компактным │ │
│ │ │ │
│ │ Было: │ │
│ │ if (!equal(a, b) && (less(a, b) || equal(a, b))) │ │
│ │ │ │
│ │ Стало: │ │
│ │ if (not_equal(a, b) && less_or_equal(a, b)) │ │
│ │ │ │
│ │ Или просто: │ │
│ │ if (a != b && a <= b) // перегруженные операторы │ │
│ └──────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────────────┘Компиляторы и библиотеки постепенно обогащали базу доступных операций: ранние версии стандартных библиотек имели меньше алгоритмов и меньше "встроенных" операций над типами, и программистам приходилось самим реализовывать то, что сегодня воспринимается как само собой разумеющееся — от элементарных численных функций до сложных алгоритмов сортировки и поиска.
Современные компиляторы, уже живут в мире, где вычислительная база для фундаментальных типов достаточно богата и хорошо оптимизирована, и их основная задача — максимально эффективно использовать эту базу, не ломая при этом семантику языка. Когда вы пишете a + b для целых, компилятор знает, какую именно машинную инструкцию использовать, как учесть переполнение, какие флаги выставятся в процессоре, и умеет на основе этого строить оптимальные последовательности команд.
Если же вы создаёте свой собственный тип, скажем, BigInt или Rational, и определяете для него минимальный набор операций, который технически полон, но не очень выразителен или неэффективен, то все функции, которые вы будете писать поверх этой базы, унаследуют и её недостатки: сложение, реализованное как многократное применение инкремента, останется экспоненциальным, как ни оптимизируй. Поэтому при проектировании собственных типов на C++ вы фактически повторяете путь архитекторов машин и авторов компиляторов: выбираете, какие операции сделать базовыми, чтобы и выражать алгоритмы было удобно, и компилятор мог порождать эффективный код, и именно здесь идеи регулярных типов и аккуратного выбора вычислительной базы становятся не теорией, а практическим руководством к тому, как проектировать хорошие, предсказуемые и быстро работающие абстракции.
Регулярность
Современный С++ не появился бы без регулярности, которая на первый взгляд кажется избыточной: мы привыкли писать код и полагаться на то, что сравнение, копирование и присваивание "как‑то работают на уровне языка и компилятора".
За этим простым поведением стоит идея, которая позволяет компилятору безопасно оптимизировать код, а нам рассуждать о нём математически корректно, и эта идея уходит корнями в фундаментальную работу Александра Степанова начала 1990-х годов.
Регулярный тип
Регулярный тип в современном понимании — это тип, который ведёт себя как примитивы вроде int или double и поддерживает корректное равенство, копирование, присваивание и конструктор по умолчанию таким образом, что равные значения остаются равными после любых операций, а копии сохраняют полную независимость от оригинала, и такая предсказуемость позволяет компилятору заменять выражения на равные им по смыслу без потери корректности программы.
Регулярные функции, в свою очередь, возвращают равные результаты при применении к равным аргументам, и это свойство, которое называется регулярностью, лежит в основе всех алгоритмов стандартной библиотеки – от сортировки и поиска до преобразований последовательностей. Весь STL был построен на предположении, что типы в контейнерах и алгоритмах ведут себя как регулярные: равенство рефлексивно, симметрично и транзитивно, копирование создаёт независимую копию, а присваивание не меняет оригинал, и именно это позволило создать библиотеку, где один и тот же алгоритм std::sort работает корректно и с int, и с std::string, и с нашими пользовательскими типами, если их спроектировали правильно.
Сложность операций
Когда мы работаем со встроенными типами вроде int, double или bool, мы обычно считаем операции равенства, копирования и присваивания константными по времени, потому что они сводятся к одной-двух машинным инструкциям сравнения или перемещения регистров, но как только мы переходим к составным объектам, картина усложняется.
Мы ожидаем, что проверка равенства займёт время, пропорциональное общему объёму данных, включая локальные поля, однако на практике эта линейная сложность не всегда гарантирована, и компиляторы используют хитрости, чтобы ускорить такие операции.
Если взять мультимножество — неупорядоченную коллекцию элементов с возможными повторениями, представленную как несортированная динамическая последовательность (например, std::vector с дубликатами), вставка нового элемента константна по времени, потому что мы добавляем элемент в конец. Но чтобы проверить равенство двух таких мультимножеств, нужно либо отсортировать оба и сравнить лексикографически — O(n log n), либо для каждого элемента первого проверить его наличие во втором с учётом кратности — O(n²) в наивной реализации. Стандартный std::unordered_multiset справляется с этим лучше: его operator== работает за O(n) в среднем, но деградирует до O(n²) при большом числе коллизий хеш-функции — что стандарт явно допускает. Если вы начнёте использовать такие мультимножества как элементы другого контейнера, где требуется частая проверка равенства для поиска или хеширования, производительность резко упадёт по сравнению с типами, у которых operator== работает за O(1).
В экстремальных случаях равенство может оказаться NP‑трудной задачей, например, если нужно проверить изоморфизм графов для структур данных, представляющих графы, и в таких ситуациях программист вынужден либо отказаться от полноценного равенства по смыслу, либо ограничиться представительным равенством — сравнением битов напрямую, что быстро, но может давать ложные срабатывания для равных по смыслу, но по-разному закодированных значений.
Представительное равенство
Именно поэтому, когда поведенческое равенство реализовать слишком дорого или невозможно, приходится переходить к представительному: два значения равны, если их битовый образ идентичен, и для составных объектов это часто реализуется через рекурсивное сравнение полей или через memcmp на сырых байтах.
Представительное равенство всегда влечёт поведенческое, потому что если биты совпадают, то интерпретация совпадает, а обратное не всегда верно, но в практике это очень удобно для конструкторов копирования и присваивания: если вы реализуете их через побайтовое копирование, вы гарантируете, что копия будет равна оригиналу по представлению, а если тип спроектирован правильно, то и по поведению.
Аналогично, когда полное равенство по смыслу слишком дорого, можно использовать структурный порядок: лексикографический для последовательностей или по первым отличающимся полям для структур, что позволяет эффективно сортировать и искать, даже если истинный порядок по смыслу недоступен. Однако не все объекты вообще допускают копирование или равенство: если объект владеет уникальным ресурсом вроде открытого файла, сетевого соединения или GPU‑буфера, то ни копирование, ни присваивание к нему смысла не имеют, и такие типы мы относим к "не‑регулярным" и используем в специальных контекстах, где явно оговариваем их семантику.
Регулярность в современном C++
В современном C++ идеи регулярности получили наконец официальное выражение в виде концептов, которые буквально воплощают в язык то, о чём Степанов говорил ещё в 1990‑е, и эти решения напрямую влияют на проектирование контейнеров, где хорошие типы всегда стремятся к регулярности.
std::string_view, std::span, std::optional спроектированы так, чтобы равенство отражало смысл, а не детали реализации, копирование означало логическое дублирование, а не совместное владение ресурсами. Если тип по природе своей не регулярный — например, владеет уникальным сокетом, GPU‑буфером или большим файлом, — то его явно относят к "объектным" типам и не пихают в value‑ориентированные контейнеры, либо снабжают слабой моделью равенства с чёткой документацией о том, что именно оно проверяет.
Регулярность и оптимизации
Для оптимизатора компилятора регулярность — это разрешение переупорядочивание операции, замену a + b на b + a или даже кэширование результата, без сайдэффектов и возможности нарушить наблюдаемое поведение программы. Компиляторы шли долгим путём к пониманию этих идей и в раннем C понятия регулярности вообще не существовало, а программист просто полагался на то, что примитивные типы ведут себя предсказуемо, а составные структуры ведут так, как написано. Но сегодня мы можем писать template<std::regular T> void process(T value);, и компилятор на этапе сборки условий может проверить, что тип соответствует всем требованиям, включая корректное равенство и копирование, что радикально упрощает отладку и делает код более надёжным, чем в эпоху, когда всё это висело на честном слове.