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