手法:再帰的なバリアントとボックス

合計型を使用してエレガントに表現できるデータ構造は多数あります。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 AddExprconst 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> 、これはポリモーフィック型の置き換えです。これにより、インターフェイスで参照セマンティクスが急増することになります。これは残念なことです。