Ссылка на битовый набор

Question

С http://www.cplusplus.com/reference/stl/bitset/:

Поскольку в большинстве сред C ++ такой маленький элементный тип не существует, к отдельным элементам обращаются как к специальным ссылкам, которые имитируют bool элементы.

Как именно работает эта битовая ссылка?

Единственный способ, которым я мог бы придумать, - это использовать статический массив из char s, но тогда каждый экземпляр должен будет хранить свой индекс вмассив.Поскольку каждый эталонный экземпляр будет иметь по крайней мере размер size_t, это нарушит компактность набора битов.Кроме того, изменение размера может быть медленным, а работа с битами ожидается быстрой.

Answer 1

Я думаю, вы путаете две вещи.

Класс bitset хранит биты в компактных представлениях, например в массиве char обычно 8 бит на char (но YMMV на «экзотических» платформах).

Класс bitset::reference предназначен для того, чтобы пользователи класса bitset могли иметь объекты, подобные ссылкам, для битов, хранящихся в bitset.

Поскольку обычные указатели и ссылки не имеют достаточной степени детализации, чтобы указывать на отдельные биты, хранящиеся в bitset (их минимальная степень детализации равна char), такой класс имитирует семантику ссылки на поддельные ссылки-подобные lvalue операции над битами. Это необходимо, в частности, для того, чтобы значение, возвращаемое operator[], работало «нормально» как l-значение (и, вероятно, составляет 99% от его «нормального» использования). В этом случае его можно рассматривать как «прокси-объект».

Такое поведение достигается путем перегрузки оператора присваивания и оператора преобразования в bool; класс bitset::reference, вероятно, будет инкапсулировать ссылку на родительский объект bitset и смещение (байты + бит) ссылочного бита, которые используются такими операторами для извлечения и сохранения значения бита.

--- EDIT ---

На самом деле, реализация g ++ заставляет bitset::reference хранить непосредственно указатель на слово памяти, в котором хранится байт, и номер бита в таком слове. Это, однако, лишь деталь реализации для повышения его производительности.

Кстати, в источниках библиотеки я нашел очень компактное, но четкое объяснение того, что такое bitset::reference и что оно делает:

  /**
   *  This encapsulates the concept of a single bit.  An instance of this
   *  class is a proxy for an actual bit; this way the individual bit
   *  operations are done as faster word-size bitwise instructions.
   *
   *  Most users will never need to use this class directly; conversions
   *  to and from bool are automatic and should be transparent.  Overloaded
   *  operators help to preserve the illusion.
   *
   *  (On a typical system, this <em>bit %reference</em> is 64
   *  times the size of an actual bit.  Ha.)
   */

Answer 2

Я не смотрел на источник STL, но я ожидаю, что ссылка на набор битов будет содержать указатель на фактический набор битов и битовое число размера size_t.Ссылки создаются только тогда, когда вы пытаетесь получить ссылку на элемент набора битов.

При нормальном использовании наборов битов маловероятно, что ссылки будут широко использоваться (если вообще будут использоваться), поэтому производительность не должна быть значительнойвопрос.И это концептуально похоже на char типов.Значение char обычно составляет 8 бит, но для хранения «ссылки» на char требуется указатель, поэтому обычно 32 или 64 бита.

Answer 3

Я не совсем уверен, что вы спрашиваете, но я могу рассказать вам, как получить доступ к отдельным битам в байте, что, возможно, и делает набор битов. Имейте в виду, что следующий код не мой и является спецификацией Microsoft (!).

Создайте структуру как таковую:

struct Byte
{
    bool bit1:1;
    bool bit2:1;
    bool bit3:1;
    bool bit4:1;
    bool bit5:1;
    bool bit6:1;
    bool bit7:1;
    bool bit8:1;
}

Часть этого кода ': 1' является битовыми полями. http://msdn.microsoft.com/en-us/library/ewwyfdbe(v=vs.80).aspx Они определяют, сколько битов переменная должна занимать, поэтому в этой структуре есть 8 значений типа bool, каждый из которых занимает 1 бит. Таким образом, структура 'Byte' имеет размер 1 байт.

Теперь, если у вас есть байт данных, например, char, вы можете сохранить эти данные в байтовом объекте следующим образом:

char a = 'a';
Byte oneByte;
oneByte = *(Byte*)(&a);   // Get the address of a (a pointer, basically), cast this  
                          // char* pointer to a Byte*,
                          // then use the reference operator to store the data that 
                          // this points to in the variable oneByte.

Теперь вы можете получить доступ (и изменить) отдельные биты, обратившись к переменным-членам bool oneByte. Чтобы снова сохранить измененные данные в символе, вы можете сделать следующее:

char b;
b = *(char*)(&oneByte);   // Basically, this is the reverse of what you do to 
                          // store the char in a Byte.

Я постараюсь найти источник этой техники, чтобы отдать должное там, где она нужна.

Кроме того, опять же, я не совсем уверен, полезен ли вам этот ответ. Я интерпретировал ваш вопрос как «как будет обрабатываться доступ к отдельным битам?».

Answer 4

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