Хорошо, сортировка у вас есть, но не из коробки: вы сами её реализовывали, а основная мысль была об использовании готового инструментария.
По сложности не отличается, но отличается в удобстве применения. Написать 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<...>) или собственноручно добавленным мьютексом/спинлоком, благо в стандарте чётко оговаривается этот момент (мол, «шарьте, но не один указатель»).
… хотя тут надо не запутаться в пресловутом lock-free — что и где мы считаем свободным от блокировок. А то может сложиться впечатление, что простая обёртка в такой atomic_shared_ptr любого контейнера сделает его и весь его интерефейс lock-free.
Меня смутила некоторая категоричность выводов статьи. Действительно, если пользователи каким бы то ни было образом получили доступ к raw-указателю (под капотом ли он shared_ptr или нет) — да, никакая сила не спасёт многопоточную среду от гонки. Но, например, в озвученной книге довольно часто обращалось внимание на тот факт, что для достижения lock-free зачастую приходится чем-то жертвовать, что в реализации выливалось в использование proxy-классов возврата или идиомы «создать-и-обменять» (что близко к понятию транзакций). Если абстрагироваться от святого желания сделать shared_ptr таким же быстрым, как и raw-указатели, думаю, с использованием сложных proxy и, возможно, в будущем transactional memory (если появится и войдёт в стандарт) или её эмуляцией в текущих реалиях стандарта, реализовать lock_free shared_ptr всё-таки возможно.
Тема неблокирующих контейнеров и алгоритмов (абстракций уровня более высокого, чем std::atomic<> и их интерефейса) сложная и интересная, более того, в настоящий момент ведутся активные исследования на эту тему (пишутся диссертации (!), берутся патенты и т.д.). Настоятельно рекомендую автору познакомиться с замечательной книгой C++ Concurrency in Action — Practical Multithreading Э. Уильямса (в русском переводе: Параллельное программирование на С++ в действии. Практика разработки многопоточных программ). Главы 4-7 весьма сложны для понимания, но в них рассматривается модель памяти нового стандарта и некоторые рецепты, как с её помощью и с новыми примитивами можно строить lock-free структуры. Также в книге детально разобрано поэтапное построение lock-free очереди, из которого можно извлечь весьма ценные уроки работы с CAS и вообще atomic'ами (как, например, одновременное измененние структуры наподобие указатель-счётчик (или как без этого можно обойтись), что, уверен, автору будет особенно интересно).
По сложности не отличается, но отличается в удобстве применения. Написать
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<...>) или собственноручно добавленным мьютексом/спинлоком, благо в стандарте чётко оговаривается этот момент (мол, «шарьте, но не один указатель»).