HashCons

クラス · hash-consing (不変な木/DAG ノードのインターン)

template <class Tag = int>
struct HashCons;

概要

hash-consing (不変な木/DAG ノードのインターン)

(tag, 子 id の列) の組を一意な整数 id に写す。構造的に等しいノードは必ず同じ id になるため、木・式・型の等価判定が $O(1)$ の整数比較になる。子は既にインターン済みの id で渡す (葉から根へボトムアップに構築)。共通する部分木は 1 ノードに共有されるので、生成されるのは DAG。式/型の等価判定、相異なる部分木の数え上げ・重複排除、共通部分式の共有などに使う。

テンプレートパラメータ

名前	説明
`Tag`	ノードのラベル型。`std::hash` と `==` を持つ型（`int`・`char`・`std::string` 等）。

計算量

ノードの登録は子数を $k$ として期待 $O(k)$、参照は $O(1)$

メンバ関数

名前	説明	計算量
`intern`	ノード `(tag, children)` をインターンして id を返す	子数を $k$ として期待 $O(k)$
`tag`	ノード `id` のラベル	$O(1)$
`children`	ノード `id` の子 id 列	$O(1)$
`child`	ノード `id` の $k$ 番目の子 id	$O(1)$
`arity`	ノード `id` の子の数	$O(1)$
`size`	相異なるノード (id) の総数	$O(1)$

メンバの詳細

intern

int intern(const Tag &tag, std::vector<int> children =;

ノード (tag, children) をインターンして id を返す

同じ (tag, children) に対しては常に同じ id を返す。 children は各要素が既存の id（[0, size()) の範囲）であること。

計算量: 子数を $k$ として期待 $O(k)$