boost::container::static_vector
のような動作をする、容量の上限N
がコンパイル時に決められた値であり、実行時に配列の要素数size
を(上限までの範囲で)変更できるようなデータ構造を考えます。
これを実現するには最低何bitの空間が必要でしょうか?
要素一つ当たり必要なビット数を、K
bitだとします。
の場合
これは、自明に0bitで実現可能です。
の場合
これは、自明にbitです。配列の要素数size
が0
である場合、1
である場合、……N
である場合、の通りを区別する必要があるためです。
それ以外の場合で、の場合
この場合、bitで実現可能です。
まず、この値が下限値であることを示します。
要素一つ当たりに必要なビット数がK
bitで、最大N
要素入りうるのでbitは確実に必要です。
N
要素入っている状態は状態あり、それ以外に0
要素入っている状態が少なくともありますから、最低でも通りを区別する必要があります。
bitでは通りの状態しか区別できませんので、最低でもbit必要ということになります。
次に、実現する方法を示します。
まず、一エントリがK
bitであり、N
要素ある配列を普通に用意します。これにはbitが費やされます。残りの1bitは、「size
がN
と等しい」ことを表すフラグにします。
容量をケチるため、フラグの状態がtrue
であるかfalse
であるかによって、データ構造を変化させます。具体的には、以下のようにします。
- フラグが
true
である、つまりsize
がN
と等しい場合、用意した配列にsize
個のK
bitデータを詰め込む - フラグが
false
である、つまりsize
がN
より小さい場合、用意した配列にsize
個のK
bitデータを詰め込む。配列の末尾にはsize
を書き込む
フラグがtrue
である場合、問題が発生しないことはすぐにわかります。フラグがfalse
である場合について少し補足します。
- 「配列の末尾には」となっていますが、
size
はN
より小さいので、配列の末尾一エントリは使われていません。よって、必ず使えます。 - 「
size
を書き込む」となっていますが、size
としてあり得るのは0
、1
、……N-1
のN通りなので、(二進数として書き込むことで)K
bitで足ります。
それ以外の場合
もし、要素数取得関数size()
の時間計算量が定数である必要がある*1なら、以下のケチりテクニックは使えません。
なくてもよいなら、上記と同じbitで実現する方法があります。ただし、size()
の時間計算量が定数でなくなるということからもわかるように、かなり非効率な実装となります。
まず、先と同じ議論により、bitが下限値であることはすぐにわかります。
実現する方法も、先の方法とおおよそ同じです。フラグがfalse
の場合の議論が成り立っていないので、以下のように変更します。
- フラグが
false
である、つまりsize
がN
より小さい場合、用意した配列にsize
個のK
bitデータを詰め込む。使っていないエントリの先頭にtrue
を、他のエントリにはfalse
を書き込む
少し補足します。
- 「使っていないエントリの先頭に」となっていますが、
size
はN
より小さいので、使っていないエントリは常に存在します。 - 「
true
を」「false
を書き込む」となっていますが、であるので、そのエントリはtrue
とfalse
を区別できるビット幅を持っていることが保証されます。ただし、タグなしunion
という、かなり危険なコードを書く必要があります。 - 「ほかのエントリには」となっていますが、そのようなエントリがなければ何もする必要はありません。
このように書き込んだデータ構造を解釈するには、後ろから解釈する必要があります。前から解釈することは不可能です。
後ろから解釈する、というのはつまり、フラグ→配列の末尾→配列の末尾のその前→……という順番で確認していくということです。
このように確認を進めていき、最初にtrue
が書き込まれていた部分までに並んでいたfalse
の数が、N-size
に対応しています。
つまり、size
の情報が一進数で書き込まれているということになります。
別の解釈もできます。フラグを「true
なら配列にはN
個の要素が書き込まれている、false
なら配列には『容量の上限がN-1
の"この仕組み"のデータ構造』が書き込まれている」という切り替えフラグだと解釈すると、再帰的なデータ構造になっていることが確かめられます。基底ケース(N=0
)ではfalse
があり得ないので常にtrue
となっていることとも整合します。
参考:要素としてあり得る状態が通り未満である場合
この場合、きっかりbitで実現可能です。その実例は、ヌル文字(NUL)終端文字列であり、文字列以外にも一般化可能です。
このように書き込んだデータ構造は、前から解釈することになります(一種の接頭符号になっています)。
size()
の時間計算量が定数でないという特徴は似ていますが、前から解釈できる特徴により、コンパイル時に容量上限を決めなくてよいという利点があります。