Rank/Select
操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
[詳解]
#include "nn/nlib/succinct/Sbv.h"
|
bool | Build () noexcept |
| Rank 辞書を構築します。 [詳解]
|
|
bool | Has (uint32_t idx) const noexcept |
| 値が集合に含まれているかどうかをテストします。 [詳解]
|
|
size_t | MemSize () const noexcept |
| このクラスが明示的に確保するメモリ量を返します。 [詳解]
|
|
uint32_t | GetBitVectorSize () const noexcept |
| ビットベクトルのサイズを返します。 [詳解]
|
|
const uint32_t * | GetBitVector () const noexcept |
| ビットベクトルへのポインタを返します。 [詳解]
|
|
void | Reset () noexcept |
| オブジェクトをコンストラクタが呼ばれた直後の状態にします。
|
|
|
| Set () noexcept |
| コンストラクタです。
|
|
| ~Set () noexcept |
| デストラクタです。
|
|
Set & | assign (Set &rhs, move_tag) |
| swap を利用したムーブにより代入します。
|
|
| Set (Set &rhs, move_tag) |
| swap を利用したムーブによりオブジェクトを構築します。
|
|
| Set (Set &&rhs) |
| ムーブコンストラクタです。C++11の利用時に有効です。
|
|
Set & | operator= (Set &&rhs) |
| ムーブ代入演算子です。C++11の利用時に有効です。
|
|
void | swap (Set &rhs) noexcept |
| オブジェクトの内容をスワップします。
|
|
|
|
uint32_t | Rank1 (uint32_t idx) const noexcept |
| Rank 操作を行います。 [詳解]
|
|
uint32_t | Rank0 (uint32_t idx) const noexcept |
| Rank 操作を行います。 [詳解]
|
|
int32_t | Select1 (uint32_t nth) const noexcept |
| nth 番目の1ビットの場所を返します。nth は0から開始します。 [詳解]
|
|
int32_t | Select0 (uint32_t nth) const noexcept |
| nth 番目の0ビットの場所を返します。nth は0から開始します。 [詳解]
|
|
|
bool | Export (BinaryWriter *w) const noexcept |
| オブジェクトを(ファイルに)書き出します。 [詳解]
|
|
bool | Import (BinaryReader *r) noexcept |
| 書き出されたオブジェクトを読み出します。 [詳解]
|
|
|
Build() の実行前に利用します。
|
typedef uint32_t | IdxType |
| インデックスとなる整数型のtypedef です。
|
|
bool | Init (uint32_t bv_size) noexcept |
| オブジェクトを初期化します。 [詳解]
|
|
bool | TurnOn (uint32_t idx) noexcept |
| 集合に32bit符号なし整数を追加します。 [詳解]
|
|
bool | TurnOff (uint32_t idx) noexcept |
| 集合から32bit符号なし整数を取り除きます。 [詳解]
|
|
Rank/Select
操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。
- 説明
- このクラスは32bit符号なし整数の集合をビットベクトルの形で保持していて、
Rank
操作と呼ばれる操作を \(O(1)\)でサポートしています。 Rank
操作についての詳しい説明は Rank0()
/Rank1()
を御覧ください。
- このクラスの利用方法は、以下のとおりです。
-
コンストラクタでオブジェクトを作成します。
-
Init()
で定義域を設定してビットベクトルを初期化します。
-
TurnOn()
で整数を集合に加えます。
-
Build()
でRank
操作を定数時間で行うための辞書を構築します。
-
Rank1()
, Select1()
といった操作が実行可能になります。
-
なお集合の内容を変更したい場合は、
TurnOn()
, TurnOff()
で変更した後再びBuild()
を実行します。
- 具体的には以下のようなコードとなります。
for (idx : 整数の集合) {
}
if (!myset.Build()) { ERROR }
- データを
Export()
で書きだした場合はコンストラクタの実行後にImport()
を呼び出すことで利用できるようになります。 このクラスは定義域のビットベクトルをすべて保持していて高速なRank
操作が可能ですが、メモリを多く消費します。 疎な集合の場合は、SparseSet
を用いる方をお勧めします。
Sbv.h の 41 行目に定義があります。
◆ Build()
nn::nlib::succinct::Set::Build |
( |
| ) |
|
|
noexcept |
Rank
辞書を構築します。
- 戻り値
- 成功した場合は
true
◆ Export()
オブジェクトを(ファイルに)書き出します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
- 書きだしたデータは
Import()
関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。
◆ GetBitVector()
nn::nlib::succinct::Set::GetBitVector |
( |
| ) |
const |
|
noexcept |
ビットベクトルへのポインタを返します。
- 戻り値
- ビットベクトルへのポインタ
- 説明
- ビットベクトルはLSB(下の桁)から順番に格納されています。
◆ GetBitVectorSize()
nn::nlib::succinct::Set::GetBitVectorSize |
( |
| ) |
const |
|
noexcept |
ビットベクトルのサイズを返します。
- 戻り値
- 集合の定義域のサイズ(ビットベクトルのサイズ)
- 説明
Init()
関数に渡した値と同じ値を返します。
◆ Has()
nn::nlib::succinct::Set::Has |
( |
uint32_t |
idx | ) |
const |
|
noexcept |
値が集合に含まれているかどうかをテストします。
- 引数
-
- 戻り値
- 集合に
idx
が含まれている場合はtrue
◆ Import()
書き出されたオブジェクトを読み出します。
- 引数
-
- 戻り値
- インポートが成功した場合は
true
◆ Init()
nn::nlib::succinct::Set::Init |
( |
uint32_t |
bv_size | ) |
|
|
noexcept |
オブジェクトを初期化します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
0
以上bv_size
未満の値を集合に加えることができるようになります。
◆ MemSize()
nn::nlib::succinct::Set::MemSize |
( |
| ) |
const |
|
noexcept |
このクラスが明示的に確保するメモリ量を返します。
- 戻り値
- バイト数
- 説明
- 実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。
◆ Rank0()
nn::nlib::succinct::Set::Rank0 |
( |
uint32_t |
idx | ) |
const |
|
inlinenoexcept |
Rank
操作を行います。
- 引数
-
- 戻り値
- 集合に含まれない
idx
以下の値の数
- 説明
idx
以下の値で集合に含まれない要素の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は定数時間で行われます。
Sbv.h の 58 行目に定義があります。
◆ Rank1()
nn::nlib::succinct::Set::Rank1 |
( |
uint32_t |
idx | ) |
const |
|
noexcept |
Rank
操作を行います。
- 引数
-
- 戻り値
- 集合に含まれる
idx
以下の値の数
- 説明
- 集合内の
idx
以下の値の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は定数時間で行われます。
◆ Select0()
nn::nlib::succinct::Set::Select0 |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
nth
番目の0ビットの場所を返します。nth
は0から開始します。
- 引数
-
- 戻り値
nth
番目(基数は0)の要素が存在するならばその値。なければ-1
- 説明
- すなわち、ビットベクトルの
nth
番目のOFFになっっているビットの位置を返します。 この操作は内部でRank1()
を利用して二分探索で行われます。
◆ Select1()
nn::nlib::succinct::Set::Select1 |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
nth
番目の1ビットの場所を返します。nth
は0から開始します。
- 引数
-
- 戻り値
nth
番目(基数は0)の要素が存在するならばその値。なければ-1
- 説明
- すなわち、ビットベクトルの
nth
番目のONになっっているビットの位置を返します。 この操作は内部でRank1()
を利用して二分探索で行われます。 通常の場合は、Select
操作を \(O(1)\)でサポートするSbv
を利用してください。
◆ TurnOff()
nn::nlib::succinct::Set::TurnOff |
( |
uint32_t |
idx | ) |
|
|
noexcept |
集合から32bit符号なし整数を取り除きます。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
- 具体的にはビットベクトル内の
idx
に該当する部分をOFFにします。
◆ TurnOn()
nn::nlib::succinct::Set::TurnOn |
( |
uint32_t |
idx | ) |
|
|
noexcept |
集合に32bit符号なし整数を追加します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
- 具体的にはビットベクトル内の
idx
に該当する部分をONにします。
このクラス詳解は次のファイルから抽出されました: