std::bitset と std::vector<bool> のビット参照

• C++ のstd::bitset と、std::vector<bool>はいずれもboolの配列として実装されているのではない。

#include <iostream>
#include <bitset>

int main() {
	bool boolarray[1<<16];
	std::cout << sizeof(boolarray) << std::endl; // 65536
	std::bitset<1<<16> bs;
	std::cout << sizeof(bs) << std::endl;        // 8192
}

• bool型はcharと同様に、普通に配列にすると 1 byte のメモリを消費する。
• しかしこれでは無駄が多いため、std::bitsetやstd::vector<bool>では、各要素が 1 bit になるように実装されている。
• 私の環境は 1 byte が 8 bit であるため、bitsetはboolの配列に比べて、メモリ消費が 1/8 になっていることがわかる。

operator[]

• 問題となるのはoperator[]の実装である。

一般の型の場合

• まず、std::vector<T>では以下のように実装されている。
• (gcc version 12.2.0 (Debian 12.2.0-14), /usr/include/c++/12/bits/stl_vector.h)

...
      // element access
      /**
       *  @brief  Subscript access to the data contained in the %vector.
       *  @param __n The index of the element for which data should be
       *  accessed.
       *  @return  Read/write reference to data.
       *
       *  This operator allows for easy, array-style, data access.
       *  Note that data access with this operator is unchecked and
       *  out_of_range lookups are not defined. (For checked lookups
       *  see at().)
       */
      _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
      reference
      operator[](size_type __n) _GLIBCXX_NOEXCEPT
      {
	__glibcxx_requires_subscript(__n);
	return *(this->_M_impl._M_start + __n);
      }

      /**
       *  @brief  Subscript access to the data contained in the %vector.
       *  @param __n The index of the element for which data should be
       *  accessed.
       *  @return  Read-only (constant) reference to data.
       *
       *  This operator allows for easy, array-style, data access.
       *  Note that data access with this operator is unchecked and
       *  out_of_range lookups are not defined. (For checked lookups
       *  see at().)
       */
      _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
      const_reference
      operator[](size_type __n) const _GLIBCXX_NOEXCEPT
      {
	__glibcxx_requires_subscript(__n);
	return *(this->_M_impl._M_start + __n);
      }
...

• referenceおよびconst_referenceは、型Tへの参照、コンスト参照である。
• this->_M_impl._M_startは、配列の開始番地を指す、型Tのポインタである。
• つまり、開始番地から__n個進めた場所への参照を返している。

std::bitset/std::vector<bool>の場合

• 上記の方法では単一のビットにアクセスすることはできない。
• そこで用いられるのがいわゆる proxy pattern であり、参照のためのクラスreferenceのインスタンスを返す実装である。
• 以下はstd::bitsetのoperator[]の実装である。 (std::vector<bool>を用いるべきだがstd::bitsetのほうが説明しやすいのでこちらを用いる。)
• (gcc version 12.2.0 (Debian 12.2.0-14), /usr/include/c++/12/bitset)

...
      /**
       *  @brief  Array-indexing support.
       *  @param  __position  Index into the %bitset.
       *  @return A bool for a <em>const %bitset</em>.  For non-const
       *           bitsets, an instance of the reference proxy class.
       *  @note  These operators do no range checking and throw no exceptions,
       *         as required by DR 11 to the standard.
       *
       *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
       *  resolves DR 11 (items 1 and 2), but does not do the range-checking
       *  required by that DR's resolution.  -pme
       *  The DR has since been changed:  range-checking is a precondition
       *  (users' responsibility), and these functions must not throw.  -pme
       */
      reference
      operator[](size_t __position)
      { return reference(*this, __position); }
...

• referenceというクラスのインスタンスを返している。
• referenceのコンストラクタは以下のようになっている。

...
	reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT
	{
	  _M_wp = &__b._M_getword(__pos);
	  _M_bpos = _Base::_S_whichbit(__pos);
	}
...

• referenceは 2 つのフィールドを持っている。
  • _M_wp: その参照オブジェクトが指し示す bit を含む word へのポインタ
  • _M_bpos: その参照オブジェクトが指し示す bit の、_M_wpにおける位置
• そして、referenceのoperator=は以下のように実装されている。

...
	// For b[i] = __x;
	reference&
	operator=(bool __x) _GLIBCXX_NOEXCEPT
	{
	  if (__x)
	    *_M_wp |= _Base::_S_maskbit(_M_bpos);
	  else
	    *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
	  return *this;
	}

	// For b[i] = b[__j];
	reference&
	operator=(const reference& __j) _GLIBCXX_NOEXCEPT
	{
	  if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
	    *_M_wp |= _Base::_S_maskbit(_M_bpos);
	  else
	    *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
	  return *this;
	}
...

• コメントにも書かれている通り、これによって単一bitへの書き込みが行える。
  • __xが真ならば、*_M_wpの_M_bposbit 目を1にする。
  • __xが偽ならば、*_M_wpの_M_bposbit 目を0にする。
• そして、boolへのキャストも実装されているので、boolの配列と同様に扱うことができる。

...
	// For __x = b[i];
	operator bool() const _GLIBCXX_NOEXCEPT
	{ return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
...

• vector<bool> の場合は、イテレータを実装するためにやや複雑だが、基本的には同様である。

簡易的な bitset

• 上記をまとめると、bitset は以下のように実装できる。

#include <iostream>

#define ceil64(x) (x % 64 == 0 ? x / 64 : x / 64 + 1)

class reference {
public:
	uint64_t *ptr;
	size_t pos;
	reference(uint64_t& n, size_t p) : ptr(&n), pos(p) {}

	reference& operator=(bool val) {
		if (val)
			*(this->ptr) |= (uint64_t)1<<this->pos;
		else
			*(this->ptr) &= ~((uint64_t)1<<this->pos);
		return *this;
	}

	reference& operator=(reference& ref) {
		if (*(ref.ptr) & (uint64_t)1 << ref.pos)
			*(this->ptr) |= (uint64_t)1<<this->pos;
		else
			*(this->ptr) &= ~((uint64_t)1<<this->pos);
		return *this;
	}

	operator bool() const {
		return *(this->ptr) & (uint64_t)1<<this->pos;
	}
};

template<size_t len>
class bitset {
public:
	friend class reference;

	uint64_t data[ceil64(len)];

	reference operator[](size_t pos) {
		return reference(data[pos / 64], pos % 64);
	}
};

int main() {
	bitset<10> bs;
	for (int i = 0; i < 10; i++)
		bs[i] = false;
	for (int i = 0; i < 10; i++)
		std::cout << bs[i];
	std::cout << std::endl; // 0000000000

	bs[0] = true;
	bs[9] = bs[0];

	for (int i = 0; i < 10; i++)
		std::cout << bs[i];
	std::cout << std::endl; // 1000000001
}