Года четыре назад, на стыке двух проектов, когда старый уже просто сапортили, а новый только находился в стадии препродакшена и питчингов разной степени завершенности (планирование и попыток продать концепт и идеи незаинтересованным инвесторам) у моей тогдашней команды удивительным образом появилось свободное время и где-то между обучением новичков премудростям кастомного движка, попытками переключаться на 20-ый стандарт и ретроспективой бэклога, солнечным сентябрьским утром родилась идея сделать студийные обсуждения в стиле подкаста PVC по теории С++, чтобы понять, какие возможности реализованы в движке, какие компетенции есть у пополнения и вообще как-то освежить теорию. Так родился мини-курс внутристудийных лекций от разных людей с разным, но реальным опытом применения, позже осевший в местной вики в виде набора статей, бест практис или вообще заметок с упором на игродевовскую тематику. Чтобы все это добро не пропадало, ибо человекочасов туда было вбухано порядком, я решил эти заметки облагородить и выложить в читаемом виде (видео к сожалению не будет, ибо НДА и всяческие спойлеры проектов и местной кухни разработки, да и никто не будет эти десятки часов болтовни слушать), но сами принципы языка и его особенностей вещь копирайту неподвластная, поэтому в таком виде вроде можно. Если подобный формат "зайдет" аудитории Хабра, можно будет продолжить статьи в виде небольшого цикла, как это получилось с серией Game++. К сожалению, начнем не с обобщенного программирования, а со второго подкаста про перегрузки, потому что первые записи оказались испорчены и на их восстановление потребуется время. Итак перегрузка в С++, не так как её учат в универе и дают в книжках...

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

Чтобы это понять, нужно вспомнить, что вообще лежит в основе обобщённого программирования и его частного применения в виде перегрузок. Основатели STL, сформулировали ключевую мысль стандартной библиотеки предельно просто: сначала нужно правильно составить (придумать) алгоритм, и только потом понять, для каких типов он работает. Эта фраза часто звучит на конференциях и в книжках умных людей, но на практике её постоянно нарушают. Нарушают не потому что сложно сделать, а потому что очень легко начать с типов, классов, иерархий и других базовых вещей, понятных программисту, а уже потом пытаться «натянуть» на них алгоритм. Само обобщённое программирование предлагает противоположный путь, и если вы посмотрите алгоритмы стандартной библиотеки, то они максимально обобщены, и в большинстве случаев будут работать что для простых интеджеров, что для сложного класса с перегруженными операторами.

Начиная с задачи алгоритма, надо всегда отвлекаться от конкретных типов данных и спрашивать себя не «что это за объект», а «какие операции над ним нужны». Нужно ли уметь умножать значения, сравнивать их, копировать, создавать нейтральный элемент? Ответы на эти вопросы естественным образом будут выявлять требования к типам, которые не будут придумываться из воздуха и для ускорения (физ. величины) некоторой сущности у нас вдруг не появятся флоаты (да он подходит по синтаксису, но флоат там и рядом не стоял по семантике), а они становятся следствием алгоритма.

Что пишут в большинстве учебников:

"Компилятор выберет нужную функцию на основе типов и количества аргументов. Это называется разрешением перегрузки (overload resolution)."

Вот эти примеры выше - это синтаксический сахар, и думая в рамках типов: «у нас есть int, double, string, давайте напишем функцию для каждого», упускается общее решение. Придуманный набор перегрузок становится способом называть похожие вещи одинаково, чтобы программисту не приходилось запоминать add_int(), add_double(), add_string().

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

В "Notes on Programming" Степанов пишет: "Structured Programming School: Dijkstra, Wirth, Hoare, Dahl. By 1975 I became a fanatical disciple. I read every book and paper authored by the giants. I was, however, saddened by the fact that I could not follow their advice. I had to write my code in assembly language and had to use goto statement. I was so ashamed. And then in the beginning of 1976 I had my first revelation: the ideas of the Structured Programming had nothing to do with the language.".

Я читал и эту книгу Степанова и книги Дейкстры, и мне больше нравится другой подход, который он позаимствовал у Гриса/Дейкстры (David Gries/Edsger Dijkstra) - тоже почти учебниковый пример - возведение числа в степень, вычисление x в степени n. Самое первое решение, которое приходит в голову, выглядит тривиально: мы заводим переменную-аккумулятор и n раз умножаем её на x в цикле. Это решение легко объяснить, легко написать и легко проверить и его часто предлагают на собеседованиях. Когда-то главным вопросом было не "как это сделать" (решение пишут практически все), а можно ли быстрее?

Оказывается, можно, и значительно. Существует алгоритм, который называется возведением в степень через квадрат, или exponentiation by squaring. Он опирается на двоичное представление показателя степени и позволяет решить задачу за логарифмическое время. Вместо того чтобы делать n умножений, мы каждый раз делим показатель пополам и возводим основание в квадрат. Если текущий показатель нечётный, мы дополнительно домножаем результат на текущее значение основания.

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

Важно отметить не столько сам алгоритм, сколько то, что ему на самом деле требуется от типа данных. Алгоритму не важно, является ли x целым числом, вещественным, очень большим или малым целым (int6_t/int128_t), матрицей или чем-то ещё. Ему нужно лишь, чтобы существовала операция умножения, чтобы был нейтральный элемент, и чтобы значения можно было копировать. Всё остальное - будут детали реализации.

И вот здесь мы выходим на связь с перегрузками и обобщённым программированием. Алгоритм у нас один и тот же, он описан в абстрактных терминах, а конкретная операция умножения подбирается в зависимости от типа. Для int это будет одно умножение, для double - другое, а для матрицы - третье и именно через перегрузки и обобщённые интерфейсы язык позволяет связать один алгоритм с множеством конкретных реализаций.

И получается, что перегрузки становятся не просто способом избежать разных имён функций, а превращаются в механизм, который позволяет выразить идею: «один и тот же алгоритм, применимый к разным типам, если они удовлетворяют определённым требованиям». Теперь перегрузка является неотъемлемой частью обобщённого программирования, а не его побочным "удобным" эффектом.

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

Продолжение следует...