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

整数から整数へのコンパクトなリードオンリーの連想配列です。 [詳解]

#include "nn/nlib/succinct/Sbv.h"

公開型

typedef SetType::IdxType IdxType
 整数インデックスです。
 
typedef std::pair< bool, uint32_t > FindType
 ブール値と整数のペアです。値が見つからなかった場合はブール値がfalseです。
 

公開メンバ関数

bool Build () noexcept
 連想配列を構築します。 [詳解]
 
size_t MemSize () const noexcept
 このクラスが明示的に確保するメモリ量を返します。 [詳解]
 
void Reset () noexcept
 オブジェクトをコンストラクタが呼ばれた直後の状態にします。
 
基本的なメンバ関数
 Map () noexcept
 コンストラクタです。
 
 ~Map () noexcept
 デストラクタです。
 
Mapassign (Map &rhs, move_tag)
 swapを利用したムーブにより代入します。
 
 Map (Map &rhs, move_tag)
 swapを利用したムーブによりオブジェクトを構築します。
 
 Map (Map &&rhs)
 ムーブコンストラクタです。C++11の利用時に有効です。
 
Mapoperator= (Map &&rhs)
 ムーブ代入演算子です。C++11の利用時に有効です。
 
void swap (Map &rhs) noexcept
 オブジェクトの内容をスワップします。
 
Mapの構築

Build()前に利用するメンバ関数です。

bool Init (IdxType bv_size) noexcept
 オブジェクトを初期化します。 [詳解]
 
bool TurnOn (IdxType idx, uint32_t data) noexcept
 キーと値を追加します。 [詳解]
 
値やキーの取得

Build()後に利用することができます。

FindType Find (IdxType idx) noexcept
 キーを指定して連想配列から値を取得します。 [詳解]
 
const FindType Find (IdxType idx) const noexcept
 キーを指定して連想配列から値を取得します。 [詳解]
 
const SetTypeGetKeys () const noexcept
 キーの集合を取得します。 [詳解]
 
const ArrayTypeGetValues () const noexcept
 値の集合を取得します。 [詳解]
 
インポートとエクスポート
bool Export (BinaryWriter *w) const noexcept
 オブジェクトを(ファイルに)書き出します。 [詳解]
 
bool Import (BinaryReader *r) noexcept
 書き出されたオブジェクトを読み出します。 [詳解]
 

詳解

整数から整数へのコンパクトなリードオンリーの連想配列です。

説明
キーとなる整数をSparseSetクラスを用いて格納し、値となる整数をCompressedArrayクラスを用いて格納しています。 疎な連想配列の実装に向いています。
このクラスの利用方法は、以下のとおりです。
  1. コンストラクタでオブジェクトを作成します。
  2. Init()で定義域を設定してビットベクトルを初期化します。
  3. TurnOn()でキーと対応する値を追加します。
  4. Build()Rank/Select操作を定数時間で行うための辞書を構築します。
  5. 以上で連想配列が使えるようになります。
データをExport()で書きだした場合はコンストラクタの実行後にImport()を呼び出すことで利用できるようになります。

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

関数詳解

nn::nlib::succinct::Map::Build ( )
inlinenoexcept

連想配列を構築します。

戻り値
成功した場合はtrue

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

nn::nlib::succinct::Map::Export ( BinaryWriter w) const
inlinenoexcept

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

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

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

nn::nlib::succinct::Map::Find ( IdxType  idx)
inlinenoexcept

キーを指定して連想配列から値を取得します。

引数
[in]idxキーとなる整数値
戻り値
booluint32_tのペア。キーに対応する値が見つかった場合はbool値がtrue

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

nn::nlib::succinct::Map::Find ( IdxType  idx) const
inlinenoexcept

キーを指定して連想配列から値を取得します。

引数
[in]idxキーとなる整数値
戻り値
booluint32_tのペア。キーに対応する値が見つかった場合はbool値がtrue

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

nn::nlib::succinct::Map::GetKeys ( ) const
inlinenoexcept

キーの集合を取得します。

戻り値
キーの集合(SparseSet型)

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

nn::nlib::succinct::Map::GetValues ( ) const
inlinenoexcept

値の集合を取得します。

戻り値
値の集合(CompressedArray型)

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

nn::nlib::succinct::Map::Import ( BinaryReader r)
inlinenoexcept

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

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

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

nn::nlib::succinct::Map::Init ( IdxType  bv_size)
inlinenoexcept

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

引数
[in]bv_sizeキーの取りうる値の上限(bvSize 自体は含まず)
戻り値
成功した場合はtrue
説明
0以上bvSize 未満の値をキーとすることができるようになります。

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

nn::nlib::succinct::Map::MemSize ( ) const
inlinenoexcept

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

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

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

nn::nlib::succinct::Map::TurnOn ( IdxType  idx,
uint32_t  data 
)
inlinenoexcept

キーと値を追加します。

引数
[in]idxキーとなる整数値
[in]data値となる整数値
戻り値
成功した場合はtrue

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


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