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

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の利用時に有効です。
 
Sbvoperator= (Sbv &&rhs) noexcept
 ムーブ代入演算子です。C++11の利用時に有効です。
 
 Sbv (Sbv &rhs, move_tag) noexcept
 ムーブコンストラクタに相当します。
 
Sbvassign (Sbv &rhs, move_tag) noexcept
 ムーブ代入演算子に相当します。
 
void swap (Sbv &rhs) noexcept
 オブジェクトの内容をスワップします。 [詳解]
 
整数集合の構築

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

bool Init (uint32_t bv_size) noexcept
 オブジェクトを初期化します。 [詳解]
 
bool TurnOn (uint32_t idx) noexcept
 集合に32bit符号なし整数を追加します。 [詳解]
 
bool TurnOff (uint32_t idx) noexcept
 集合から32bit符号なし整数を取り除きます。 [詳解]
 
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
 書き出されたオブジェクトを読み出します。 [詳解]
 

詳解

Rank/Select操作つきの32bit符号なし整数の集合を保持する簡潔データ構造です。

説明
このクラスは32bit符号なし整数の集合をビットベクトルの形で保持していて、Rank操作に加えてSelect操作を \(O(1)\)でサポートしています。 Rank/Select操作を利用することで近年提案されているコンパクトなデータ構造に対する高速な操作を実現することができます。 なお、Rank/Select操作についての詳しい説明はSet::Rank1()及びSelect1()を御覧ください。
このクラスの利用方法は、以下のとおりです。
  1. コンストラクタでオブジェクトを作成します。
  2. Init()で定義域を設定してビットベクトルを初期化します。
  3. TurnOn()で整数を集合に加えます。
  4. Build()Rank/Select操作を定数時間で行うための辞書を構築します。
  5. 以上でRank/Select操作が利用できるようになります。
データをExport()で書きだした場合はコンストラクタの実行後にImport()を呼び出すことで利用できるようになります。 このクラスは定義域のビットベクトルをすべて保持していて高速なRank操作が可能ですが、メモリを多く消費します。 疎な集合の場合は、SparseSetを用いる方をお勧めします。

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

関数詳解

◆ Build()

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

Rank/Select辞書を構築します。

戻り値
成功した場合はtrue

◆ Export()

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

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

引数
[in]w書き出し用オブジェクト
戻り値
成功した場合はtrue
説明
書きだしたデータはImport()関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。

◆ GetBitVector()

nn::nlib::succinct::Sbv::GetBitVector ( ) const
inlinenoexcept

ビットベクトルへのポインタを返します。

戻り値
ビットベクトルへのポインタ
説明
ビットベクトルはLSB(下の桁)から順番に格納されています。

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

◆ GetBitVectorSize()

nn::nlib::succinct::Sbv::GetBitVectorSize ( ) const
inlinenoexcept

ビットベクトルのサイズを返します。

戻り値
集合の定義域のサイズ(ビットベクトルのサイズ)
説明
Init()関数に渡した値と同じ値を返します。

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

◆ Has()

nn::nlib::succinct::Sbv::Has ( uint32_t  idx) const
inlinenoexcept

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

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

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

◆ Import()

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

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

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

◆ Init()

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

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

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

◆ MemSize()

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

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

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

◆ Rank0()

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

Rank操作を行います。

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

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

◆ Rank1()

nn::nlib::succinct::Sbv::Rank1 ( uint32_t  idx) const
inlinenoexcept

Rank操作を行います。

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

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

◆ Select0()

nn::nlib::succinct::Sbv::Select0 ( uint32_t  nth) const
inlinenoexcept

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

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

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

◆ Select1()

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

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

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

◆ swap()

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

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

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

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

◆ TurnOff()

nn::nlib::succinct::Sbv::TurnOff ( uint32_t  idx)
inlinenoexcept

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

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

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

◆ TurnOn()

nn::nlib::succinct::Sbv::TurnOn ( uint32_t  idx)
inlinenoexcept

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

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

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


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