Гибкая индексация элементов в контейнере на С++ и при чём тут Boost.MultiIndex

К сожалению сам Boost.MultiIndex остался "черным ящиком" - неизвестно внутреннее строение контейнера.

Я придумал схему, по которой сами объекты хранятся в "стандартном" контейнере, а "индекс" это объект `std::multiset<const Person*, comp>`, то есть в индексе лежит указатель на них.

Тут реализация: https://godbolt.org/z/ne895x73f, но не придумал как быстро искать объект по ключу, потому что std::find_if линейный

Концепция умного указателя static_ptr<T> в C++

С этим я согласен, только замечания: не "программистский", а "вычисляторский"; не "жаргон", а "говор"; не "автор", а "создатель"; не "школа", а "училище". Слова заморского происхождения не пройдут!

Концепция умного указателя static_ptr<T> в C++

На стеке много объектов выделить не получится, он обычно маленький (8192 KiB). А как вы будете аккуратно аллоцировать объекты разных размеров? Тут свой головняк начнется, это не проще.

Для "маленьких объектов" есть memory pools (https://betterprogramming.pub/c-memory-pool-and-small-object-allocator-8f27671bd9ee)

В принципе static_ptr оторван от всяких кастомных аллокаторов, это перпендикулярно к нему идет. Можно считать, что static_ptr это такое представление std::unique_ptr<T>, где указатель T* t и, хм, объект *t находятся "рядом" by desing.

Концепция умного указателя static_ptr<T> в C++

Наверное картинки в статье вводят всех в заблуждение. Объекты sp::static_ptr<T> не живут только на стеке.

Например в std::vector<sp::static_ptr<T>> alloca/VLA ничем не помогут. Почему, например, такой вектор круче - описал тут https://habr.com/ru/post/665632/#comment_24343986

"Динамический буфер" - буфер все таки статический, хотя в compile-time проверяется что объекты туда залезут.

Концепция умного указателя static_ptr<T> в C++

Как быстро получить указатель на базовый класс? У меня вышло так:

using TEngine = std::variant<TSteamEngine, TRocketEngine, TEtherEngine>;
// ...
IEngine* GetEngine(TEngine* engine) {
    if (auto ptr = std::get_if<TSteamEngine>(engine)) return ptr;
    if (auto ptr = std::get_if<TRocketEngine>(engine)) return ptr;
    if (auto ptr = std::get_if<TEtherEngine>(engine)) return ptr;
    return nullptr;
}

std::variant из всех наследников выглядит как-то жутковато) Но идея похоже рабочая

P. S. Только бы еще оттуда удалить copy constructor и copy assignment operator...

Концепция умного указателя static_ptr<T> в C++

Хранимый объект допускает перемещение.

Кстати, std::vector<T> как раз требует, чтобы объект T был перемещаемым или хотя бы копируемым. А то не скомпилируется кусок кода отвечающий за перемещение объектов при переаллокации.

(Соответственно этого не требуется для std::list и подобных контейнеров)

Концепция умного указателя static_ptr<T> в C++

А в описанном случае с выделением памяти ..., сгодится и "глупый" си-шный указатель, разве нет?

А где будет находиться объект, куда указывает "глупый" указатель? В куче не может - цель уйти от кучи. На стеке может только в aligned_storage, а из этого вытекают разные вопросы, которые попытался решить в статье.

sp::static_ptr кстати решает еще одну специфическую проблему - теперь объект невозможно случайно скопировать (передать по значению, etc.)

не позволяет даже просто переиспользовать объект без полной передачи или вложения в другой объект

К сожалению не понял, что имеется в виду под "нельзя переиспользовать объект". Указываемый объект возможно использовать также, как в других умных указателях:

sp::static_ptr<TObj> p;
// ... в `p` лежит объект
TObj obj{std::move(*p)};

Концепция умного указателя static_ptr<T> в C++

Пусть есть виртуальный абстрактный класс IEngine и его наследники TSteamEngine, TRocketEngine, TEtherEngine.

Нужно завести контейнер из объектов, чей тип - какой-то наследник IEngine. Как вы это сделаете?

Стандартный подход: std::vector<std::unique_ptr<IEngine>>.

Этот подход значит, что в куче лежит память вектора для N объектов Engine*, каждый объект указывает еще куда-нибудь в кучу в рандомное место (и каждый раз при добавлении объекта происходит аллокация).

Подход с std::vector<sp::static_ptr<IEngine>> значит, что в куче лежит память вектора для N объектов размера static_ptr_traits<IEngine>::buffer_size, и больше ничего, это круче из-за локальности памяти.

Концепция умного указателя static_ptr<T> в C++

Действительно, идея "витает в воздухе", но здесь позволю себе не согласиться с вами ? Какая мотивация у Антона:

1. Нужно реализовать идиому PImpl, чтобы быстрее компилировалось (убрался инклюд) и т.д.

2. "Стандартный подход" заключается в замене T на std::unique_ptr<T>, потому что там ок чтобы T был incomplete type (а у меня кстати не так, мне нужен T complete).

3. Этот подход медленный из-за кучи, поэтому T заменяют на обертку над std::aligned_storage<sizeof(T), alignof(T)>, причем эти два числа надо посчитать руками.

И там совсем не про "динамический полиморфизм на стеке", тип жестко фиксирован. Из общего только использование aligned_storage...

Про вторую заметку: интересно, какие есть кейсы, где используются over-aligned типы? Я сам с таким еще не сталкивался.

Концепция умного указателя static_ptr<T> в C++

Устаревший он с C++23. Компилятор может скомпилировать с ворнингом что "это фича из более нового стандарта", но может и не скомпилировать. Это пока в тестовом формате.

Начиная с C++23 было бы так:

alignas(align) std::byte buf_[buffer_size];

Неклассические контейнеры в C++

Думаю что это сделано из соображений перфоманса.

С вашим дизайном было бы так: разыменовать (1) ссылку на вектор, посмотреть на .data(), разыменовать (2) сам объект в нужном адресе.

С текущим дизайном разыменование одно, так как сразу знаем нужный адрес.

Можно считать что итератор станет работать в 2 раза медленнее.

Неклассические контейнеры в C++

К сожалению, не пользовался библиотекой Bitmagic. Прочитав про нее, увидел что это очень мощная библиотека. Про устройство - последовательность битов там может иметь очень разные представления. Все зависит от сценариев использования, мне хватало функционала bitset и dynamic_bitset.

Единственно (на мой взгляд) минус в том, что библиотека Bitmagic является header-only, это негативно влияет на время компиляции.

Неклассические контейнеры в C++

Я на всякий случай проверил работу алгоритма перемещения.

Изначально есть capacity для 10 объектов, при превышении делается реаллокация. Move-конструктор (не-noexcept) на 5-м объекте бросает исключение.

Если есть конструктор копирования, то вызывается именно он - https://godbolt.org/z/8qnEavP1f и strong exception guarantee выполнится

Widget(const Widget&) = default;

Если его нет, то вызывается move-конструктор за неимением другого варианта и после ловли исключения часть объектов "побита" - https://godbolt.org/z/x5hjcGTqE

Widget(const Widget&) = delete;

Поэтому лучше стараться делать move-конструктор noexcept, а то много проблем может быть

Неклассические контейнеры в C++

В статье рассматривается скорее внутреннее устройство контейнеров и управление памятью.

std::valarray по своему внутреннему устройству имеет незначительное отличие от std::vector (а именно 2 указателя вместо 3, так как там size = capacity).

"Синтаксический сахар" (методы min, sqrt, и тд) для std::valarray отличается от такового у std::vector, но это не так важно. В мире C++ есть много vector-like объектов, но они не принесли бы принципиально новой информации в статью.

Неклассические контейнеры в C++

Спасибо! Да, проверил что для Visual C++ в 1.5 раза увеличивается

https://godbolt.org/z/WYs9f7Kn5

Программирование необычных шахмат

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

Делаться должно скорее наоборот - на основе анализа разных партий можно определить стоимость фигур. На Habr есть статья на эту тему - https://habr.com/ru/post/254753/. Но там только для "классических" шахмат.

Программирование необычных шахмат

Да, пожалуй так и есть, "bitboard" это термин только для строго специфического представления доски (такого, какой вы описали), а не вообще для каждого "сжатого" представления доски. Концепция понятна, в моей реализации намеренно делается упор в "человекочитаемый" код с циклами и ветвлениями за счет потери в скорости.

Кроме того, bitboard подход очень плохо масштабируется для досок произвольного размера.

Да, описанный подход совсем не будет работать для любой доски кроме 8x8 (которой повезло "влезть" в один int64).

Многострадальный C++ и системы сборки

С октября 2021 года есть пропозал чтобы то, что вы описали, больше не будет ill-formed/NDR

http://open-std.org/JTC1/SC22/WG21/docs/papers/2022/p2448r1.html#pnum_24

Многострадальный C++ и системы сборки

или вообще не известно завершима ли она. Что компиляторы должны делать в таком случае?

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

Многострадальный C++ и системы сборки

 Вообще, в одном китайском эмуляторе сеги я видел примерно это:
constexpr static inline auto func(args) -> int noexcept const

Не читайте до обеда советских газет исходники китайских эмуляторов.

[dcl.consexpr] - constexpr-метод неявно является inline.

static inline бессмысленный и работает как просто static. И сам static не нужен, когда есть constexpr. (Если этот метод глобальный)

Про "второе значение" слова inline, про встраивание кода - примерно с 2013 года Clang перестал ставить таким методам флаг inlinehint в своем промежуточном представлении, и сейчас это значение утратилось. У других компиляторов скорее всего так же.