nlib
nn::nlib::succinct::Set クラスfinal

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
 オブジェクトをコンストラクタが呼ばれた直後の状態にします。
 
基本的なメンバ関数
constexpr Set () noexcept
 コンストラクタです。
 
 ~Set () noexcept
 デストラクタです。
 
Setassign (Set &rhs, move_tag)
 ムーブ代入演算子に相当します。
 
 Set (Set &rhs, move_tag)
 ムーブコンストラクタに相当します。
 
 Set (Set &&rhs)
 ムーブコンストラクタです。C++11の利用時に有効です。
 
Setoperator= (Set &&rhs)
 ムーブ代入演算子です。C++11の利用時に有効です。
 
void swap (Set &rhs) noexcept
 オブジェクトの内容をスワップします。 [詳解]
 
RankとSelect操作

Build()の実行後に利用します。

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() を御覧ください。
このクラスの利用方法は、以下のとおりです。
  1. コンストラクタでオブジェクトを作成します。
  2. Init() で定義域を設定してビットベクトルを初期化します。
  3. TurnOn()で整数を集合に加えます。
  4. Build()Rank操作を定数時間で行うための辞書を構築します。
  5. Rank1(), Select1()といった操作が実行可能になります。
  6. なお集合の内容を変更したい場合は、TurnOn(), TurnOff()で変更した後再びBuild()を実行します。
具体的には以下のようなコードとなります。
Set myset;
if (nlib_is_error(myset.Init(size))) { ERROR }
for (idx : 整数の集合) {
if (nlib_is_error(myset.TurnOn(idx))) { ERROR }
}
if (!myset.Build()) { ERROR }
// 以降のコードでRank/Select操作が可能
データをExport()で書きだした場合はコンストラクタの実行後にImport()を呼び出すことで利用できるようになります。 このクラスは定義域のビットベクトルをすべて保持していて高速なRank操作が可能ですが、メモリを多く消費します。 疎な集合の場合は、SparseSetを用いる方をお勧めします。

Sbv.h41 行目に定義があります。

関数詳解

◆ Build()

nn::nlib::succinct::Set::Build ( )
noexcept

Rank辞書を構築します。

戻り値
成功した場合はtrue

◆ Export()

nn::nlib::succinct::Set::Export ( BinaryWriter w) const
noexcept

オブジェクトを(ファイルに)書き出します。

引数
[in]w書き出し用オブジェクト
戻り値
成功した場合は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

値が集合に含まれているかどうかをテストします。

引数
[in]idx32bit符号なし整数
戻り値
集合にidx が含まれている場合はtrue

◆ Import()

nn::nlib::succinct::Set::Import ( BinaryReader r)
noexcept

書き出されたオブジェクトを読み出します。

引数
[in]r読み出し用オブジェクト
戻り値
インポートが成功した場合はtrue

◆ Init()

nn::nlib::succinct::Set::Init ( uint32_t  bv_size)
noexcept

オブジェクトを初期化します。

引数
[in]bv_sizeビットベクトルのサイズ。
戻り値
成功した場合はtrue
説明
0以上bv_size 未満の値を集合に加えることができるようになります。

◆ MemSize()

nn::nlib::succinct::Set::MemSize ( ) const
noexcept

このクラスが明示的に確保するメモリ量を返します。

戻り値
バイト数
説明
実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。

◆ Rank0()

nn::nlib::succinct::Set::Rank0 ( uint32_t  idx) const
inlinenoexcept

Rank操作を行います。

引数
[in]idx32bit符号なし整数
戻り値
集合に含まれないidx 以下の値の数
説明
idx 以下の値で集合に含まれない要素の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は定数時間で行われます。

Sbv.h54 行目に定義があります。

◆ Rank1()

nn::nlib::succinct::Set::Rank1 ( uint32_t  idx) const
noexcept

Rank操作を行います。

引数
[in]idx32bit符号なし整数
戻り値
集合に含まれるidx 以下の値の数
説明
集合内のidx 以下の値の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は定数時間で行われます。

◆ Select0()

nn::nlib::succinct::Set::Select0 ( uint32_t  nth) const
noexcept

nth 番目の0ビットの場所を返します。nth は0から開始します。

引数
[in]nth0以上の整数
戻り値
nth 番目(基数は0)の要素が存在するならばその値。なければ-1
説明
すなわち、ビットベクトルのnth 番目のOFFになっっているビットの位置を返します。 この操作は内部でRank1()を利用して二分探索で行われます。

◆ Select1()

nn::nlib::succinct::Set::Select1 ( uint32_t  nth) const
noexcept

nth 番目の1ビットの場所を返します。nth は0から開始します。

引数
[in]nth0以上の整数
戻り値
nth 番目(基数は0)の要素が存在するならばその値。なければ-1
説明
すなわち、ビットベクトルのnth 番目のONになっっているビットの位置を返します。 この操作は内部でRank1()を利用して二分探索で行われます。 通常の場合は、Select操作を \(O(1)\)でサポートするSbvを利用してください。

◆ swap()

void nn::nlib::succinct::Set::swap ( Set rhs)
inlinenoexcept

オブジェクトの内容をスワップします。

非推奨:
この関数は将来のリリースにおいて削除されます。

Sbv.h340 行目に定義があります。

◆ TurnOff()

nn::nlib::succinct::Set::TurnOff ( uint32_t  idx)
noexcept

集合から32bit符号なし整数を取り除きます。

引数
[in]idx集合から取り除く整数
戻り値
成功した場合はtrue
説明
具体的にはビットベクトル内のidx に該当する部分をOFFにします。

◆ TurnOn()

nn::nlib::succinct::Set::TurnOn ( uint32_t  idx)
noexcept

集合に32bit符号なし整数を追加します。

引数
[in]idx集合に加える整数
戻り値
成功した場合はtrue
説明
具体的にはビットベクトル内のidx に該当する部分をONにします。

このクラス詳解は次のファイルから抽出されました: