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

Question

Это в основном вопрос юриста по языку, я сомневаюсь, что это будет беспокоить большинство реализаций, тем более что это, вероятно, увеличит время компиляции для каждого пользователя.

При этом сказано: Если какая-то реализация std ::набор был реализован с использованием набора битов для каждого экземпляра и статического массива из 256 значений, которые являются общими (это безопасно, поскольку ключи являются постоянными), что будет допустимым в соответствии со стандартом?

Answer 1

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

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

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

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

Answer 2

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

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

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

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