Часто встречал подобное мнение и не считаю его справедливым и конструктивным: всё-таки А.А. сыграл значительную роль в развитии языка (см. спойлер «Лирическое отступление»). В конце концов, никто не заставляет программистов городить воздушные замки из шаблонов: они, как и любой инструмент, имеют свою область применения, а большинство задач может быть решено разными способами (и с разным соотношением время/универсальность/расширяемость/производительность).
ИМХО, гораздо более «страшным» мне видится виртуально-интерфейсный фарш, бездонные иерархии и километровые определения приезжих в C++ из C#/Java, обычно и пышущих ненавистью к углоскобочному миру.
Уоу, это действительно круто, вроде как кейс попадает под «statement is a type-dependent expression» + функция-то шаблонная, но сходу вообще не очевидно.
Вангую, что подобные фичи опять будут открываться методом проб и ошибок a la «ребят, тут фарш инстанцировался, получился Coq».
Пожалуй, скажу ещё пару слов о constexpr if. В описании есть несколько важных моментов, и самыми вкусными являются эти:
The return statements in a discarded statement do not participate in function return type deduction.
...if condition is not value-dependent after instantiation, the discarded statement is not instantiated when the enclosing template is instantiated.
т.е. constexpr функции отныне действительно смогут «конструировать» типы и останавливать рекурсию по типам (с некоторыми оговорками). Рис возвращается в плов.
Энтузиасты пилят совершенно нереальные вещи. Например, паттерн матчинг на C++, даже синтаксис приемлемый, и без макросов (!).
Ещё посмотрите на constexpr if — фича C++17. Вообще, по мощности C++17 должен получиться тортом. Ждём и желаем удачи (и душевных сил) разработчикам компиляторов!
А, то есть вы предлагаете хранить генератор вместе с Treap'ом? Хорошо, я же имел в виду внешний «настоящий» генератор, никак не связанный с контейнером. В таком случае ваше решение, безусловно, несоизмеримо проще, это правда.
не вижу большой разницы между counter::next() и Random::next. Что-то вам все равно придется хранить и передавать
Более того я привел пример того как ее можно сгенерировать
Как раз не придётся. То, что вы описали, просто не будет работать: вам либо придётся руками считать вызовы Random<...>, либо подсовывать предыдущие псевдонимы в параметр шаблона. Упомянутые статьи как раз и описывают реализацию счётчика, способного инкрементироваться без посторонней помощи.
Хорошо, сортировка у вас есть, но не из коробки: вы сами её реализовывали, а основная мысль была об использовании готового инструментария.
По сложности не отличается, но отличается в удобстве применения. Написать template<..., counter::next()> func{...}; проще (и логичнее), чем помнить пробрасываемый генератор. Следуя вашей логике вообще можно заранее руками написать всю последовательность «случайных» чисел.
Добавлю в TODO мини-задачу реализации compile-time генератора псевдослучайных чисел. Challenge accepted. Закончу — оставлю здесь ссылку.
У вас есть готовая функция сортировки кортежей в рукаве? Замечание о балансировке было сказано только как пример: мол, на основе уже существующего API можно это же дерево и сбалансировать.
Касательно статьи, которую я привел: ознакомьтесь с ней, пожалуйста, прежде, чем делать выводы (+ещё лучше сразу с источником перевода, это цикл из 3-х статей). Техника, описанная в них, позволяет реализовать глобальный счётчик времени компиляции как минимум. Применение его (несть числа способам) — дело техники.
Я думаю, автор (@semenyakinVS) скорее хотел обратить внимание на более общий вопрос рефлексии в C++ (см. его цикл статей, рассказывающий о разработке библиотеки поддержки рефлексии).
А так да, действительно, каждый день просто сажусь и описываю AST в compile-time. Вот скоро порт boost::spirit на язык шаблонов закончу, вот тесты на static_assert дописываю, жаль, компилируются по две недели…
Оуоу, давайте жить дружно! Практика как самоцель тоже имеет право на существование, и ничего плохого в попытке «с нуля» по аналогии соорудить мета-контейнер нет (набить руку, так сказать).
По теме беседы:
Описанное в статье дерево может быть сбалансировано очень простым приёмом (однако сложность O(n2) при конструировании с пустого): добавляем элементы «как попало» => делаем симметричный обход (сортируем) => сортированный кортеж разбираем делением пополам (в новое дерево кладём серединный элемент, далее середины середин и т.д.)
Генератор псевдослучайных чисел можно соорудить и на этапе компиляции (только надо пробрасывать seed для всех последующих «вызовов»). Есть ещё крайне интересная идея: использовать этот подход для генерации псевдослучайной последовательности (ОПАСНОСТЕ: по ссылке разрыв шаблонов во всех смыслах).
Рад, что задача вызвала интерес: варка в собственном соку в перспективе не приносит ничего хорошего, всегда важен взгляд со стороны заинтересованного сообщества.
Если даже разработанная реализация никогда явно никому не пригодится (кроме инсайдеров нашей команды), но идеи и подходы заинтересуют энтузиастов и помогут в изучении темы или реализации собственных инструментов и идей, то задача статьи будет выполнена.
Балансировка — интересная задача, и, в принципе, вполне решаемая уже на описанном уровне абстракций, реализация вращений будет похожа идеей на insert. Не знаю, насколько оправдана она будет (как упражнение — вполне): там, где важна балансировка, нужно смотреть уже в сторону АВЛ или красно-чёрных деревьев, реализацию которых пока оставим как домашнее упражнение заинтересованным читателям :)
Понял замечание, согласен, такой подход был бы хорош в случае, если бы узлы хранились в плоском кортеже, а структура дерева описывалась бы последовательностями индексов. В случае же, когда навигация осуществляется непосредственно по вложенным псевдонимам (т.е. так, как дерево описано в статье), «считать» как бы ничего и не остаётся, нужно просто явно применять рекурсивные алгоритмы навигации. В статье есть упоминание о неединственности представления дерева.
Каюсь, согласен, это частный случай АСД, однако данное конкретное дерево имеет узлы степени не более 2 и может быть построено рекусивным спуском особым сравнителем и типами-ключами. Вообще, описанное дерево имеет косвенное отношение к указанной задаче, и было, можно сказать, тренировкой и проверкой выразительных возможностей.
Не совсем корректно: constexpr-функции всё-таки не способны создавать новые типы (в зависимости от значений аргументов), а если применять вывод возвращаемого типа из типов аргументов через auto a la C++14, то задача скатывается к старым добрым шаблонам.
Все алгоритмы в статье возвращают именно типы, о наделении же узлов данными-членами сказано несколько слов в Применении.
Спасибо за замечания. Это была, так сказать, проба пера*, и некоторый сумбур, безусловно, присутствует.
По пунктам:
Во-первых, для логарифмической сложности требуется сбалансированность дерева
Статья не претендует на звание исчерпывающего руководства по алгоритмам и структурам данных (она и так получилась весьма объёмной даже со спойлерами), поэтому я намеренно опускал некоторые моменты: сведующий читатель поймёт, о чём речь, остальные же получат повод загуглить, если эти моменты действительно им интересны. И да, корень «логарифм» встречается только в одном месте в тексте, а сырое бинарное дерево не имеет балансировки (и необходимость в ней, вообще говоря, зависит от решаемой задачи*).
Просто нужно конкретизировать шаблон не внутри, а снаружи
Вот это очень интересное замечание, спасибо, я обращу на конкретизацию особое внимание. Вы хотите сказать, что такой подход автоматически отключит инстанцирование search или insert на неверном пути? Пока я в этом сомневаюсь.
Без остановки прохода по ненужным веткам и без сбалансированности такое «дерево поиска» хуже простого линейного поиска.
О сбалансированности было сказано ранее, об отключениях — согласитесь, без сбалансированности оно не имеет особого смысла :) Надо сказать, слово «поиска» в определении немного сбивает с толку: кому-то может показаться, что описанная структура — это готовый мета-std::map, однако это именно бинарное дерево (не более) с минимально необходимым интерфейсом.
Так 17-й же уже на подходе.
Справедливо. У меня до сих пор присутствует некоторая инертность относительно новых и грядущих стандартов — политика партии требует стабильности компиляции.
Речь не об АСД, в эпилоге имеется в виду конкретный алгоритм типа «first/last/follow pos» (пример описания, самое простое, что сразу нашёл).
Нет, готовых измерений производительности нет, но вопрос интересный, доп. флагами компилятора можно включить вывод времени фаз компиляции. Сделаю замеры и обновлю комментарий/эпилог статьи.
И сразу вопрос — а зачем? Ответ в вопросе: если в задаче требуется создание дерева и операции с ним на этапе компиляции, то вот и пример) Описан инструментарий, о более реальном(ых) же примерах его применения сказано несколько слов в соответствующем разделе. Вы правы, для описаной вами задачи макроса действительно будет достаточно. Одной из целей статьи, однако, было показать, как можно обходиться без макросов в довольно нетривиальных ситуациях.
Про Spirit — да, в каком-то смысле, вы правы: упрощенно, финальная задача — получить (но на этапе компиляции) некоторый предметно-ориентированный автомат.
Да, прошу прощения, унесло немного не туда :)
К вопросу о thread-safe текущей реализации — думаю, в свете упомянутого, цена такого решения в виде громоподобно хрустящих compare_exchange под капотом не совсем соотносится с возможным выигрышем от всей этой кухни, поэтому комитету (и пользователям) было и будет проще пока что довольствоваться блокирующим доступом и специализациями std::atomic_xxx(shared_ptr<...>) или собственноручно добавленным мьютексом/спинлоком, благо в стандарте чётко оговаривается этот момент (мол, «шарьте, но не один указатель»).
ИМХО, гораздо более «страшным» мне видится виртуально-интерфейсный фарш, бездонные иерархии и километровые определения приезжих в C++ из C#/Java, обычно и пышущих ненавистью к углоскобочному миру.
Вангую, что подобные фичи опять будут открываться методом проб и ошибок a la «ребят, тут фарш инстанцировался, получился Coq».
constexpr if. В описании есть несколько важных моментов, и самыми вкусными являются эти:т.е.constexprфункции отныне действительно смогут «конструировать» типы и останавливать рекурсию по типам (с некоторыми оговорками). Рис возвращается в плов.Ещё посмотрите на
constexpr if— фича C++17. Вообще, по мощности C++17 должен получиться тортом. Ждём и желаем удачи (и душевных сил) разработчикам компиляторов!Random<...>, либо подсовывать предыдущие псевдонимы в параметр шаблона. Упомянутые статьи как раз и описывают реализацию счётчика, способного инкрементироваться без посторонней помощи.Спасибо! Задача действительно интересная.
По сложности не отличается, но отличается в удобстве применения. Написать
template<..., counter::next()> func{...};проще (и логичнее), чем помнить пробрасываемый генератор. Следуя вашей логике вообще можно заранее руками написать всю последовательность «случайных» чисел.Добавлю в TODO мини-задачу реализации compile-time генератора псевдослучайных чисел. Challenge accepted. Закончу — оставлю здесь ссылку.
Касательно статьи, которую я привел: ознакомьтесь с ней, пожалуйста, прежде, чем делать выводы (+ещё лучше сразу с источником перевода, это цикл из 3-х статей). Техника, описанная в них, позволяет реализовать глобальный счётчик времени компиляции как минимум. Применение его (несть числа способам) — дело техники.
А так да, действительно, каждый день просто сажусь и описываю AST в compile-time. Вот скоро порт
boost::spiritна язык шаблонов закончу, вот тесты наstatic_assertдописываю, жаль, компилируются по две недели…Если даже разработанная реализация никогда явно никому не пригодится (кроме инсайдеров нашей команды), но идеи и подходы заинтересуют энтузиастов и помогут в изучении темы или реализации собственных инструментов и идей, то задача статьи будет выполнена.
Балансировка — интересная задача, и, в принципе, вполне решаемая уже на описанном уровне абстракций, реализация вращений будет похожа идеей на
insert. Не знаю, насколько оправдана она будет (как упражнение — вполне): там, где важна балансировка, нужно смотреть уже в сторону АВЛ или красно-чёрных деревьев, реализацию которых пока оставим как домашнее упражнение заинтересованным читателям :)Окай :( В общем, поправлено.
constexpr-функции всё-таки не способны создавать новые типы (в зависимости от значений аргументов), а если применять вывод возвращаемого типа из типов аргументов черезautoa la C++14, то задача скатывается к старым добрым шаблонам.Все алгоритмы в статье возвращают именно типы, о наделении же узлов данными-членами сказано несколько слов в Применении.
Вот это очень интересное замечание, спасибо, я обращу на конкретизацию особое внимание. Вы хотите сказать, что такой подход автоматически отключит инстанцирование
searchилиinsertна неверном пути? Пока я в этом сомневаюсь.О сбалансированности было сказано ранее, об отключениях — согласитесь, без сбалансированности оно не имеет особого смысла :) Надо сказать, слово «поиска» в определении немного сбивает с толку: кому-то может показаться, что описанная структура — это готовый мета-
std::map, однако это именно бинарное дерево (не более) с минимально необходимым интерфейсом.Справедливо. У меня до сих пор присутствует некоторая инертность относительно новых и грядущих стандартов — политика партии требует стабильности компиляции.
Нет, готовых измерений производительности нет, но вопрос интересный, доп. флагами компилятора можно включить вывод времени фаз компиляции. Сделаю замеры и обновлю комментарий/эпилог статьи.
И сразу вопрос — а зачем? Ответ в вопросе: если в задаче требуется создание дерева и операции с ним на этапе компиляции, то вот и пример) Описан инструментарий, о более реальном(ых) же примерах его применения сказано несколько слов в соответствующем разделе. Вы правы, для описаной вами задачи макроса действительно будет достаточно. Одной из целей статьи, однако, было показать, как можно обходиться без макросов в довольно нетривиальных ситуациях.
Про Spirit — да, в каком-то смысле, вы правы: упрощенно, финальная задача — получить (но на этапе компиляции) некоторый предметно-ориентированный автомат.
К вопросу о thread-safe текущей реализации — думаю, в свете упомянутого, цена такого решения в виде громоподобно хрустящих compare_exchange под капотом не совсем соотносится с возможным выигрышем от всей этой кухни, поэтому комитету (и пользователям) было и будет проще пока что довольствоваться блокирующим доступом и специализациями std::atomic_xxx(shared_ptr<...>) или собственноручно добавленным мьютексом/спинлоком, благо в стандарте чётко оговаривается этот момент (мол, «шарьте, но не один указатель»).