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

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

```c++
#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`)
```c++
...
      // 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`)

```c++
...
      /**
       *  @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`のコンストラクタは以下のようになっている。
```c++
...
	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=`は以下のように実装されている。
```c++
...
	// 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_bpos`bit 目を1にする。
  - `__x`が偽ならば、`*_M_wp`の`_M_bpos`bit 目を0にする。
- そして、`bool`へのキャストも実装されているので、`bool`の配列と同様に扱うことができる。
```c++
...
	// For __x = b[i];
	operator bool() const _GLIBCXX_NOEXCEPT
	{ return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
...
```
- `vector<bool>` の場合は、イテレータを実装するためにやや複雑だが、基本的には同様である。

## 簡易的な bitset
- 上記をまとめると、bitset は以下のように実装できる。

```c++
#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
}
```