Стоит ли основывать битовый контейнер, не являющийся владельцем, на std::vector‹bool›? станд::промежуток?

В нескольких моих проектах мне все чаще приходилось иметь дело с непрерывными последовательностями битов в памяти - эффективно (*). До сих пор я написал кучу встраиваемых автономных функций, основанных на выборе типа «контейнера битов» (например, uint32_t), для получения и установки битов, применения «или» и «и» к их значениям, нахождения контейнер, преобразование длины в битах в размеры в байтах или длины в контейнерах и т. д. ... похоже, пришло время написания класса.

Я знаю, что стандартная библиотека С++ имеет специализацию std::vector<bool>, что многие считают недостатком дизайна, поскольку ее итераторы не выставляют фактические bool, а скорее прокси-объекты. Является ли это хорошей или плохой идеей для специализации, я определенно обдумываю это — явный битовый прокси-класс, который, надеюсь, будет «всегда» оптимизирован (с хорошей смазкой с помощью constexpr, noexcept и inline) . Итак, я подумал о возможной адаптации кода std::vector из одной из реализаций стандартной библиотеки.

С другой стороны, мой предполагаемый класс:

  • Никогда не будет владеть данными / битами - он получит адрес начального битового контейнера (при условии выравнивания) и длину в битах и ​​не будет выделять или освобождать.
  • Он не сможет динамически или иным образом изменять размер данных - даже при сохранении того же объема пространства, что и std::vector::resize(); его длина будет фиксированной в течение срока его службы/области действия.
  • Он ничего не должен знать о куче (и работать, когда кучи нет)

В этом смысле это больше похоже на класс span для битов. Тогда, может быть, начать с диапазона? Не знаю, пролеты еще не стандартные; а в спэнах нет прокси...

Итак, что было бы хорошей основой (изменить: НЕ базовый класс) для моей реализации? std::vector<bool>? std::span? Оба? Никто? Или - может я изобретаю велосипед и это уже решаемая проблема?

Заметки:

  • Длина последовательности битов известна во время выполнения, а не во время компиляции; в противном случае, как предполагает @SomeProgrammerDude, я мог бы использовать std::bitset.
  • Моему классу не нужно "быть" span или "be-a" вектором, поэтому я не думаю о специализации ни одного из них.

(*) - Пока неэффективно SIMD, но это может появиться позже. Кроме того, это может использоваться в коде CUDA, где мы не используем SIMDize, а притворяемся, что дорожки являются правильными потоками.


c++ stdvector class-design c++20 std-span
person einpoklum    schedule 13.06.2018    source источник
comment
std::bitset? И я действительно не рекомендую специализироваться на std::vector, так как тогда вы, по сути, просто переделаете std::vector<bool>. Вместо этого вы можете создать свой собственный класс, который лучше соответствует вашим требованиям и может быть достаточно открытым, чтобы включать ваши планы на будущее.   -  person Some programmer dude    schedule 14.06.2018
comment
@Someprogrammerdude: смотрите примечания в моем редактировании.   -  person einpoklum    schedule 14.06.2018
comment
Судя по тому, что я себе представляю, я бы начал с реализации std::span, которую можно найти в Интернете, и позаимствовал бы битовый прокси у vector<bool>.   -  person Drew Dormann    schedule 14.06.2018
comment
почему бы просто не сохранить необработанный ptr и длину в своем классе, а затем предоставить некоторые функции для проверки битов? поскольку он не имеет права собственности, не вижу необходимости в копии.   -  person skeller    schedule 14.06.2018
comment
@skeller: я не уверен, что понимаю ваш комментарий. Я не собираюсь ничего копировать...   -  person einpoklum    schedule 14.06.2018
comment
Будете ли вы изменять биты через невладеющий контейнер?   -  person BeeOnRope    schedule 14.06.2018
comment
@BeeOnRope: Да, я сказал установить биты...   -  person einpoklum    schedule 14.06.2018
comment
Ваш вопрос мне не ясен. Вы говорите, что у вас уже есть куча автономных функций, которые реализуют это поверх класса битового контейнера (здесь битовый контейнер просто что-то вроде uint64_t - или он более сложный?) - так что кажется, что у вас уже есть свое решение? По сути, вы просто хотите переместить эти автономные функции внутрь класса, который поддерживает указатель на массив битовых контейнеров? Вы также спрашиваете, должны ли std::vector или std::span служить основой для вашего класса, но что здесь означает основа? Вы говорите об использовании одного...   -  person BeeOnRope    schedule 14.06.2018
comment
... этих классов как часть реализации (вы исключили наследование, но, конечно, композиция все еще в игре), или вы имеете в виду вдохновение для дизайна? Ясно, что std::vector<bool> отсутствует с точки зрения фактической реализации, поскольку он владеет своим хранилищем: тогда как вам ясно, что вы хотите что-то похожее на span/view. Я думаю, что более четкий вопрос покажет функции, которые у вас уже есть, и спросит о конкретном решении, например, относительно дизайна итератора (если вы вообще хотите, чтобы итераторы) или использования прокси-объектов для представления одного бита.   -  person BeeOnRope    schedule 14.06.2018
comment
@BeeOnRope: 1. битовый контейнер - моя формулировка немного вводит в заблуждение. Это просто интегральный тип, как вы подозреваете. 2. Что такое база? Отчасти копирование кода, отчасти дизайнерское вдохновение. 3. Я примерно объяснил, о чем мои функции, я не хочу глотать наживку, публиковать какой-то код и заставлять людей комментировать мой код.   -  person einpoklum    schedule 14.06.2018
comment
@einpoklum - мне до сих пор непонятно, почему вы не превращаете свои существующие автономные методы, которые соответствуют вашим потребностям и были разработаны с учетом вашего варианта использования, в класс, а вместо этого представляете это как выбор между vector или span - но в любом случае, если вы хотите начать с нуля, а не использовать свои методы, я попытался ответить.   -  person BeeOnRope    schedule 15.06.2018
comment
@BeeOnRope: потому что я хочу использовать прокси, поэтому код будет структурирован немного по-другому. Но спасибо.   -  person einpoklum    schedule 15.06.2018
comment
@einpoklum - правильно, я вижу. Если вы определенно хотите использовать прокси, было бы неплохо включить его в вопрос. В любом случае, std::bitset предоставляет прокси-объект для побитовой модификации, поэтому я думаю, что это отличный кандидат.   -  person BeeOnRope    schedule 15.06.2018
comment
Я голосую за внедрение на основе std::span; в основном обертка вокруг ряда объектов. Даже если он не войдет в окончательный вариант стандарта, std::span, по крайней мере, был проверен комитетом как действительно хорошая идея, настолько, что, вероятно, он останется в стандартной версии для C++20.   -  person AndyG    schedule 18.06.2018

Ответы (1)


arrow_upward
1
arrow_downward

Вместо std::vector или std::span я подозреваю, что реализация вашего класса будет иметь больше общего с std::bitset, поскольку это почти то же самое, за исключением (фиксированного) размера, определяемого во время выполнения.

На самом деле, вы, вероятно, могли бы взять типичную реализацию std::bitset и переместить параметр шаблона <size_t N> в класс в качестве члена size_t size_ (или как вам угодно), и вы получите класс динамического набора битов практически без изменений. Возможно, вы захотите избавиться от всего, что вы считаете бесполезным, например, от конструкторов, которые берут std::string и друзей.

Последним шагом является удаление владения базовыми данными: в основном вы удаляете создание базового массива в конструкторе и поддерживаете представление существующего массива с некоторыми указателями.

Если ваши клиенты не согласны с тем, какой базовый целочисленный тип без знака использовать для хранения (то, что вы называете «битовым контейнером»), вам также может потребоваться сделать свой класс шаблоном для этого типа, хотя было бы проще, если бы все согласились с этим. скажи uint64_t.

Что касается std::vector<bool>, то от этого многого не нужно: все, что vector делает то, что вы хотите, std::bitset, вероятно, тоже делает: главное, что добавляет vector, — это динамичный рост, но вы сказали, что не хотите этого. vector<bool> имеет концепцию прокси-объекта для представления одного бита, но то же самое относится и к std::bitset.

Из std::span вы берете идею невладения базовыми данными, но я не думаю, что на самом деле это представляет собой много базового кода. Возможно, вы захотите рассмотреть std::span подход с использованием либо известного размера во время компиляции, или размера, предоставленного во время выполнения (обозначенного Extent == std::dynamic_extent), если это было бы полезно для вас (в основном если вы иногда используете размеры времени компиляции и можете специализировать некоторые методы, чтобы они были более эффективными в этом случае).

person BeeOnRope    schedule 15.06.2018
comment
На самом деле, было бы не так просто для всех согласиться с uint64_t по двум причинам: 1. Использовать его на некоторых платформах, отличных от x86 (например, графических процессорах nVIDIA), дорого. 2. Существует реальная необходимость создать экземпляр этого класса для другого контейнера. размеров из-за некоторых практических соображений. - person einpoklum; 15.06.2018
comment
@einpoklum В этом случае вы можете сделать его классом шаблона поверх C (тип битового контейнера), чтобы клиентский код мог выбирать тип хранилища. Это лишь немного усложняет реализацию. Единственным недостатком является то, что наборы битов с различными базовыми вариантами C являются разными типами, поэтому вы не можете напрямую передать dyn_bitset<uint8_t> чему-то, что ожидает dyn_bitset<uint32_t>, даже если вы предоставляете один и тот же API. Если вы измените принимающую функцию, чтобы использовать аргумент шаблона, она будет работать через утиную печать, хотя у этого также есть некоторые недостатки. - person BeeOnRope; 15.06.2018
comment
Да, действительно, я уже упоминал в вопросе, что я шаблонизирую тип контейнера. Кстати, когда у меня будет время изучить код std::bitset и поиграть с ним, я решу, принимать ли ваш ответ (который я поставил +1). - person einpoklum; 15.06.2018
comment
@einpoklum - чтобы было ясно, вы сказали, что ваше существующее решение автономных функций было создано по шаблону типа контейнера. В комментариях к вопросу я попытался узнать больше о существующем решении и о том, почему вы не хотели его использовать, или чего вы хотели больше, но вы, так сказать, не попались на удочку. Итак, как я уже упоминал, я написал это более или менее так, как если бы вы делали реализацию с нуля, поэтому такие вещи, как шаблон или нет, требовали переоценки. - person BeeOnRope; 15.06.2018
comment
Для класса общего назначения, такого как bitset (включая полудинамический [1] набор битов, как вы хотите), использование шаблона для типа хранилища было бы довольно раздражающим, поскольку каждый тип хранилища приводит к несвязанному объекту, поэтому вы хотели бы согласиться на обычном типе для совместимости, но ваш вариант использования может быть другим, более узким и предпочтительнее включать хранилище в тип (например, для производительности). [1] Здесь я использую полудинамический для обозначения продолжительности выполнения, но который фиксируется при построении для каждого объекта, как вы хотите. - person BeeOnRope; 15.06.2018