代数的構造を乗せるデータ構造の設計について

概要

SegmentTree などのように、代数的構造 (特にモノイド) を乗せるデータ構造は多い。この部分の設計は様々だが、「静的メンバを実装した型を受け取る」設計を他の設計と比較する。

設計のバリエーション

A: std::function で関数オブジェクトを持つ

template <class T> class segment_tree {
  std::function<T(T, T)> op;
  T id;
};

B: 関数オブジェクトをそのまま持つ

template <class T, class F> class segment_tree {
  F op;
  T id;
};

C: 演算子がオーバーロードされた型を受け取る

struct add {
  int val;
  add operator+(add r) { return add(val + r.val); }
  add() : val(0) {}
  add(int x) : val(x) {}
};

template <class T> struct segment_tree {};

D: メンバを実装したオブジェクトを持つ

struct add {
  using T = int;
  int op(int l, int r) { return l + r; }
  int id;
};

template <class M> struct segment_tree {
  using T = typename M::T;
  M mo;
};

E: 静的メンバを実装した型を受け取る

struct add {
  using T = int;
  static int op(int l, int r) { return l + r; }
  static inline int id;
};

template <class M> struct segment_tree { using T = typename M::T; };

D, E については、id をメンバ変数ではなくメンバ関数として持つ実装もある。その他、継承を利用する実装もあるようだが詳しくないので割愛。

著者は E を常用している。実装例

E の利点

A と比較して、std::function を使用していない。
- 高速になる。
A, B, D と比較して、データ構造内部に一切オブジェクトを持たなくてよい。
- 永続データ構造など、大量のオブジェクトを作成するときに空間が削減できる。
- meldable heap や平衡二分木など融合を行うデータ構造で、どちらのオブジェクトを使用すればいいのかなどの問題が起こらずスッキリしている。
- データ構造内部でさらに構造体を定義したとき、そのメンバ関数で演算が使える。
C と比較して、扱いたい型をそのまま値に出来る。
- 値をラップしたりはがしたりする手間が無い。
C と比較して、演算子のネタ切れなどが起こらない。
- 環など 2 つの単位元を持つ構造は、デフォルトコンストラクタだけだと表現できない。

E の欠点

A, B と比較して、構造体を書く必要がある。
- operator+ と 0 など、典型的な演算はライブラリにしておくことで回避できる。
- ライブラリ化していない変な演算は手間が増えてしまう。
A, B, D と比較して、内部にオブジェクトを持てない。
- ローカル変数を参照するような演算の表現には静的メンバを使用する必要があり、面倒。
C と比較して、関数を明示的に呼び出す必要がある。
- C は + などを書くだけなので、読みやすく短い。

noshi91のメモ

データ構造のある風景

代数的構造を乗せるデータ構造の設計について

概要

設計のバリエーション

E の利点

E の欠点