Будет ли законно, чтобы std::set был специализирован для (u)int8 и символов с использованием набора битов и общего статического массива?

Я не вижу ограничений, которые запрещали бы вам делать специализированную реализацию, если вы соблюдаете стандартные спецификации в разделе [set].

Для set<char> или set<uint8_t> вам потребуется 32 октета для хранения 256 битов, представляющих потенциальные элементы, с преимуществом очень быстрых операций над множествами. Для set<int> вы бы потребляли слишком много памяти, и это было бы оправдано IMHO только в том случае, если бы у вас были очень заполненные наборы.

При этом есть некоторые проблемы, которые необходимо преодолеть:

• вам нужно будет организовать массив, который отображает значения в битовые позиции, чтобы он соответствовал предоставленному компаратору (стоимость при построении, если вы не можете поделиться им)
• вам придется реализовать итератор (но это не проблема, так как растровое изображение и битовое смещение могут работать).
• поскольку C++17 существует открытое предположение, что структура данных использует узлы поскольку существует элемент extract(), который должен возвращать значение (не указан) специализированный тип node_type. Не уверен, что подразумевает это требование, но я думаю, что его можно решить таким же образом, как и проблему с итератором выше.
• Вам нужно будет соответствовать требованиям сложности (см. комментарий Натана Оливье к вашему вопросу). Трудность возникает из-за упорядочения общего массива. Однако, если бы вы использовали два общих массива (один для преобразования значения в битовое смещение и один для преобразования битового смещения в значение) или один массив пар, вы могли бы вставить что угодно в O (1).

РЕДАКТИРОВАТЬ: Сделал ошибку. Прокси-итераторы не разрешены в C++17.

Я думаю, что это невозможно. Во-первых: эта реализация будет содержать все гарантии сложности и для большинства из них будет лучше, чем требования.

Во-вторых: вам не разрешено создавать прокси-итератор при использовании стандартного контейнера, поскольку в некоторых точках они должны были возвращать реальные ссылки. (Упомянутый @Christophe std::bitset не является контейнером и в его определении есть прокси-ссылка. std::vector ‹ bool > — известный пример нарушения гарантий). Таким образом, невозможно использовать эту реализацию.

Редактировать: спасибо @NicolBolas за указание на то, что итераторы прокси по-прежнему запрещены.

Ответ Кристофа содержит важный момент:

• вам нужно будет организовать массив, который сопоставляет значения с битовыми позициями, так, чтобы он соответствовал предоставленному компаратору (стоимость при построении, если вы не можете поделиться им)

Это указывает на сложную проблему работы с компараторами с сохранением состояния (когда отношение порядка не является фиксированным, но может управляться извне и динамически изменяться во время выполнения). Хотя не одобряется общими людьми C++, я не мог найти ничего в стандарте, который запрещал бы компараторы с отслеживанием состояния для ассоциативных контейнеров (но я не искал слишком много). Если вы управляете состоянием компаратора и содержимым набора так, чтобы требование упорядочения никогда не нарушалось, то это работает на практике (по крайней мере, это сработало для меня).

Итак, мой вердикт таков: в самом общем случае произвольный компаратор std::set не может специализироваться для небольших целочисленных типов с использованием bitset и любых поддерживающих общих статических данных.