union と Placement new で ADT を定義する

Fri, Aug 31, 2018

C++ には Placement new という機能があって、簡単に言えば、事前に確保されているメモリ領域に新たに生成されたオブジェクトを埋め込む機能です。私は Placement New の使い道にあまり詳しくないですが、1 つ有用なパターンがあるので紹介します。

よく関数型言語だと、

data Tree a = Leaf a | Branch (Tree a) (Tree a)

というような ADT(Abstract Data Type) を定義します。

これを C++ で実現するにはどうするか？という話なんですが、1 つの方法としては継承を用いた sub-typing が考えられるでしょう。で、継承に代わる別の方法として Placement new が使えます。

ということで、早速 Haskell や Scala にある Either を Placment new を使って定義する例を見てみましょう。

まず、ADT におけるそれぞれのデータ構成子を定義します。Tree の例で言えば Leaf と Branch に相当します。

template <typename T>
struct Left {
  T value;
};

template <typename T>
struct Right {
  T value;
};

次に ADT の型構成子を定義します。こちらが Either の本体になります。

template <typename L, typename R>
struct Either {
  union {
    L leftValue;
    R rightValue;
  };

  bool isLeft = false;

  constexpr Either(Left<L> const& l)
      : leftValue { l.value }, isLeft(true) {}

  constexpr Either(Right<R> const& r)
      : rightValue { r.value }, isLeft(false) {}

  constexpr Either(Either<L, R> const& e)
      : isLeft(e.isLeft)
  {
    if (e.isLeft) {
      new (&leftValue)L(e.leftValue);
    } else {
      new (&rightValue)R(e.rightValue);
    }
  }

  ~Either()
  {
    if (isLeft) {
      leftValue.~L();
    } else {
      rightValue.~R();
    }
  }

  static constexpr Either<L, R> right(R const& r)
  {
    return Either<L, R> { Right<R> { r } };
  }

  static constexpr Either<L, R> left(L const& l)
  {
    return Either<L, R> { Left<L> { l } };
  }

  template<typename F>
  constexpr auto map(F const& f) const& -> Either<L, decltype(f(rightValue))>
  {
    if (isLeft) {
      return left(leftValue);
    }

    return right(f(rightValue));
  }
};

それほど複雑ではないと思います。

この実装のポイントは、

  constexpr Either(Either<L, R> const& e)
      : isLeft(e.isLeft)
  {
    if (e.isLeft) {
      new (&leftValue)L(e.leftValue);
    } else {
      new (&rightValue)R(e.rightValue);
    }
  }

  ~Either()
  {
    if (isLeft) {
      leftValue.~L();
    } else {
      rightValue.~R();
    }
  }

の部分になります。C++ に詳しくない人は new (&leftValue)L(e.leftValue) の意味がよく分からないかもしれませんが、これが Placement new です。Placement new を使った場合、デストラクタを適切に自分で呼び出す必要がある点に注意してください。

また、Left と Right を区別するために isLeft メンバ変数を使っているように、union と placement new を組み合わせて ADT を表現する場合、デストラクタ呼び出しのために isLeft に相当する補助情報が必要になります。

Placement new のメリットについては、継承を使わないことで仮想関数呼び出しを排除できる点があります。vtable lookup にはそれなりのコストがかかるので、Either のようなコア機能では性能面で嬉しいですね。(現実的には C++ では Either はあまり使われないと思いますが…。)

ということで、他にも Placement new の有用なパターンがあれば教えてください。

libmacro.com

union と Placement new で ADT を定義する

Comments