合計型を使用してエレガントに表現できるデータ構造は多数あります。C++ では、合計型の (やや不格好な) 実装は std::variant
です。 .ただし、1 つの選択肢に合計型全体が再び含まれる再帰的なデータ構造を処理することはできません。
どうすれば修正できるか見てみましょう。
問題
足し算と掛け算をサポートする単純な計算機を考えます。11
のような式を保存して評価したいと考えています。 、 40 + 2
、または 3 * 13 + 3
.つまり、式はリテラル数、2 つの部分式を含む加算、または 2 つの部分式を含む乗算のいずれかです。Using std::variant
、次のようになります:
struct LiteralExpr
{
int value;
};
struct AddExpr
{
Expr lhs, rhs;
};
struct MulExpr
{
Expr lhs, rhs;
};
using Expr = std::variant<LiteralExpr, AddExpr, MulExpr>;
しかしもちろん、これはコンパイルできません:C++ では Expr
の前に宣言が必要です AddExpr
で使用できます 、しかし Expr
の宣言 AddExpr
の宣言が必要です .このような循環依存は、AddExpr
を前方宣言することで解決できます。 および MulExpr
Expr
を移動します 定義の前に宣言します。
struct LiteralExpr
{
int value;
};
// We forward declare the types while naming them here.
using Expr = std::variant<LiteralExpr,
struct AddExpr, struct MulExpr>;
struct AddExpr
{
Expr lhs, rhs;
};
struct MulExpr
{
Expr lhs, rhs;
};
さて、 1 + 2 * 3
のような式 次のように保存されます:
auto expr = Expr(AddExpr{LiteralExpr{1}, MulExpr{LiteralExpr{2}, LiteralExpr{3}}});
ただし、まだコンパイルされません:std::variant
前方宣言では機能しません。型のサイズを知る必要があるため、定義が必要です。また、C++ が宣言の順序が問題にならない言語であったとしても、循環依存関係は依然として存在します。
考慮してください:Expr
のサイズは? ?
さて、Expr
はバリアントであるため、そのサイズは最大のメンバーにタグを加えたサイズです。最大のメンバーは AddExpr
です。 、そのサイズは 2 * sizeof(Expr)
です 、これには AddExpr
が含まれる場合があります 、そのサイズは 2 * sizeof(Expr)
です など。 sizeof(Expr) = sizeof(tag) + 2 * sizeof(Expr)
の唯一の解決策 sizeof(Expr) = ∞
です (または sizeof(tag) = -sizeof(Expr)
)!
これは不可能です。
ネストされた式を割り当てるヒープ
無限の入れ子を解決する 1 つの方法は、たとえば、. AddExpr
実際に格納する必要がある場合は空にし、それ以外の場合は空のままにします。これは AddExpr
を割り当てることで実行できます そうすれば、バリアント自体は固定サイズのポインターのみを格納します。
最新の C++ を使用しているため、これは AddExpr
をラップすることを意味します と MulExpr
内部 std::unique_ptr
:
using Expr = std::variant<LiteralExpr, std::unique_ptr<struct AddExpr>, std::unique_ptr<struct MulExpr>>;
std::unique_ptr
前方宣言された型に問題はなく、それ自体が完全な型であるため、 std::variant
無限の入れ子にストレージを提供する代わりに、特定の式に実際に必要なだけのメモリが割り当てられます。
このソリューションは機能します。
それも本当に醜いです。
まず、式の作成には std::make_unique
が必要です 呼び出し:
Expr(std::make_unique<AddExpr>(LiteralExpr{1}, std::make_unique<MulExpr>(LiteralExpr{2}, LiteralExpr{3})));
それも C++20 でのみ機能し、集計は T(args...)
で初期化できます。 .それ以外の場合は、コンストラクターを AddExpr
に追加する必要があります と MulExpr
.
さらに重要なのは、Expr
値のセマンティクスはなくなりました。以前は Expr
を自由にコピーできました その結果、2 つの独立したオブジェクトが生成されます (つまり、std::shared_ptr
std::unique_ptr
に感謝します。 、コピーできなくなりました:
Expr square(Expr operand)
{
// error: can't copy Expr
return std::make_unique<MulExpr>(operand, operand);
}
同様に、constness は伝播しなくなりました:const Expr&
がある場合 lhs
を変更することもできます または rhs
AddExpr
の const std::unique_ptr<Expr>
として それでも Expr&
が表示されます :
int evaluate(const Expr& expr)
{
struct visitor
{
int operator()(const LiteralExpr& expr) { return expr.value; }
int operator()(const std::unique_ptr<AddExpr>& expr)
{
expr->lhs = LiteralExpr{42}; // ups
auto lhs = std::visit(*this, expr->lhs);
auto rhs = std::visit(*this, expr->rhs);
return lhs + rhs;
}
int operator()(const std::unique_ptr<MulExpr>& expr)
{
auto lhs = std::visit(*this, expr->lhs);
auto rhs = std::visit(*this, expr->rhs);
return lhs * rhs;
}
};
return std::visit(visitor{}, expr);
}
それらの問題を解決しましょう。
値セマンティクスの追加
C++ では、malloc
を使用しなくなりました 'ed const char*
文字列のポインター。ポインターをコピーしても文字列はコピーされないため、std::string
を使用します。 :内部的には同じですが、上に値のセマンティクスが追加されています。同じ理由で、std::unique_ptr
は使用しないでください。 :所有権を提供して伝達するという点で生のポインターよりわずかに優れていますが、基本的には参照セマンティクスを持つ型です。std::unique_ptr
の唯一の許容される使用 実装の詳細です。インターフェイスには表示されません。
本当に必要なのは、割り当てられたヒープ T
を格納できる型です それ以外は T
のように動作します .特に、const を伝播する必要があり、ディープ コピーを行うコピー コンストラクターを備えています。Rust からインスピレーションを得て、box<T>
と呼びましょう。 :
template <typename T>
class box
{
// Wrapper over unique_ptr.
std::unique_ptr<T> _impl;
public:
// Automatic construction from a `T`, not a `T*`.
box(T &&obj) : _impl(new T(std::move(obj))) {}
box(const T &obj) : _impl(new T(obj)) {}
// Copy constructor copies `T`.
box(const box &other) : box(*other._impl) {}
box &operator=(const box &other)
{
*_impl = *other._impl;
return *this;
}
// unique_ptr destroys `T` for us.
~box() = default;
// Access propagates constness.
T &operator*() { return *_impl; }
const T &operator*() const { return *_impl; }
T *operator->() { return _impl.get(); }
const T *operator->() const { return _impl.get(); }
};
注意事項:
std::unique_ptr
のラッパーです .そうすれば、デストラクタについて心配する必要がなくなります。T
から暗黙的に構築できます 、これにはヒープ割り当てが含まれます。これはstd::string
に似ていますconst char*
から暗黙的に構築できる 効率上の理由から、コンストラクターはexplicit
にすることができます 、しかし、これはstd::variant
で意図した使い方になります- コピー コンストラクターは先に進み、
T
をコピーします。 新しいオブジェクトを割り当てる必要があります。これは、値のセマンティクスに必要です。 - 基礎となる
T
へのアクセス オブジェクトはoperator*
を使用して可能です とoperator->
.彼らはconst
を広めます :const box<T>
const T&
しか配らない 、std::unique_ptr
とは異なります .理想的な世界では、.
でのアクセスを許可するために、ここである種の自動逆参照が行われました。 、Rust のように。
std::unique_ptr
を置き換えるだけです。 box
で バリアント宣言で.これにより、構造が再び適切になり、式を自由にコピーでき、constness が伝播します。
using Expr = std::variant<LiteralExpr,
box<struct AddExpr>, box<struct MulExpr>>;
…
auto expr = Expr(AddExpr{LiteralExpr{1}, MulExpr{LiteralExpr{2}, LiteralExpr{3}}});
Expr square(Expr operand)
{
return MulExpr{operand, operand}; // ok
}
int evaluate(const Expr& expr)
{
struct visitor
{
int operator()(const LiteralExpr& expr) { return expr.value; }
int operator()(const box<AddExpr>& expr)
{
// expr->lhs = LiteralExpr{42}; -- won't compile
auto lhs = std::visit(*this, expr->lhs);
auto rhs = std::visit(*this, expr->rhs);
return lhs + rhs;
}
int operator()(const box<MulExpr>& expr)
{
auto lhs = std::visit(*this, expr->lhs);
auto rhs = std::visit(*this, expr->rhs);
return lhs * rhs;
}
};
return std::visit(visitor{}, expr);
}
余談:ボックスの移動
box<T>
を与えていないことに注意してください ムーブ コンストラクター。これは意図的なもので、2 つのオプションがあり、さらに議論する必要があります。
1 つ目は、コピー コンストラクターのように動作し、基になる T
を移動するムーブ コンストラクターを用意することです。 object.これには、新しいオブジェクトを割り当てるヒープが必要であり、noexcept
ではありません :
box(box &&other) : box(std::move(*other._impl)) {}
box &operator=(box &&other)
{
*_impl = std::move(*other._impl);
return *this;
}
2 番目のオプションは、std::unique_ptr
に委任することです。 の move コンストラクターで、所有権を譲渡します。これはヒープ割り当てを必要とせず、noexcept になります。
box(box&& other) noexcept = default;
box& operator(box&& other) noexcept = default;
ただし、2 番目のオプションを使用すると、box<T>
の可能性が生じます。 空であること – 移動元の状態。そこでは、基になる T
へのアクセスが許可されなくなりました オブジェクトが存在しないためです。
私が過去に繰り返し主張してきたように、このようなmoved-from状態を追加することは問題があります.C++コンパイラはそれをキャッチするのに役立ちません.そのルートをたどる場合は、空の状態を完全に受け入れる必要があります.デフォルトを追加する.コンストラクター、そのクエリなど - ボックスを optional_box<T>
に変える 繰り返しますが、Rust にはその問題はありません。コンパイラが移動されたオブジェクトへのアクセスを防止するからです。
結論
再帰バリアントにはヒープ割り当てが必要です。それを回避する方法はありません。
ヒープ割り当ての簡単な方法は std::unique_ptr
です .しかし、それは参照セマンティクスを持つ型であり、値型よりもはるかに劣っています.より良い代替手段は、正しい値セマンティクスを追加する単純なラッパーを書くことです box<T>
.
一般的に、私は std::unique_ptr
があまり好きではありません そのため、インターフェイスには場所がなく、実装の詳細にすぎません。残念ながら、C++ 標準ライブラリは box<T>
などのより適切な型を提供していません。 または提案された std::polymorphic_value<T>
、これはポリモーフィック型の置き換えです。これにより、インターフェイスで参照セマンティクスが急増することになります。これは残念なことです。