Toy expression tree evaluator showing std::visit() and overloaded {} sugar

tree_eval_variant_visit.cpp

// Toy expression tree evaluator showing std::visit() and overloaded {} sugar.
//
// https://gcc.godbolt.org/z/r7PffK18e
//
// Diff view for older version showing generated assembly is same with or without overloaded:
// https://godbolt.org/z/6efWvj5o3

#include <variant>
#include <memory>
#include <string>
#include <iostream>
#include <map>

// Algebraic type representing an expression tree.
struct Number;
struct Variable;
struct Add;
using Node = std::variant<Number, Variable, Add>;

struct Number { int value; };
struct Variable { std::string id; };
struct Add { 
    Add(std::unique_ptr<Node> l, std::unique_ptr<Node> r)
        :   left(std::move(l)),
            right(std::move(r))
    {}
    std::unique_ptr<Node> left, right; 
};

// 3 + (x + 5)
Node an_expr() {
    return Add(
        std::make_unique<Node>(Number{3}), 
        std::make_unique<Node>(Add(
            std::make_unique<Node>(Variable{"x"}),
            std::make_unique<Node>(Number{5}))
        )
    );
}

// 3 + (5 + x)
Node another_expr() {
    return Add(
        std::make_unique<Node>(Number{3}), 
        std::make_unique<Node>(Add(
            std::make_unique<Node>(Number{5}),
            std::make_unique<Node>(Variable{"x"}))
        )
    );
}

// Environment passed to evaluator.
using Env = std::map<std::string, int>;

int evaluate_no_overloaded(const Env& env, const Node& tree) {
    struct Evaluator {
        explicit Evaluator(const Env& env) : env_(env) {}

        int operator()(Number n) { return n.value; }
        int operator()(const Variable& v) {
            if (const auto it = env_.find(v.id); it != env_.end()) {
                return it->second;
            } else {
                throw std::runtime_error("unknown variable");
            }
        }
        int operator()(const Add& add) {
            return evaluate_no_overloaded(env_, *add.left) + evaluate_no_overloaded(env_, *add.right);
        }
        
        const Env& env_;
    };

    return std::visit(Evaluator{env}, tree);
}

// from https://en.cppreference.com/w/cpp/utility/variant/visit
template<class... Ts>
struct overloaded : Ts... { using Ts::operator()...; };
// explicit deduction guide (not needed as of C++20)
template<class... Ts>
overloaded(Ts...) -> overloaded<Ts...>;

int evaluate_with_overloaded(const Env& env, const Node& tree) {
    const auto evaluator = overloaded {
        [](Number n) { return n.value; },
        [&](const Variable& v) {
            if (const auto it = env.find(v.id); it != env.end()) {
                return it->second;
            } else {
                throw std::runtime_error("unknown variable");
            }
        },
        [&](const Add& add) {
            return evaluate_with_overloaded(env, *add.left) + evaluate_with_overloaded(env, *add.right);
        }
    };

    return std::visit(evaluator, tree);
}

bool compare_trees(const Node& lhs, const Node& rhs) {
    const auto comparator = overloaded {
        [](Number lhs, Number rhs) { 
            return lhs.value == rhs.value; 
        },
        [&](const Variable& lhs, const Variable& rhs) {
            return lhs.id == rhs.id;
        },
        [&](const Add& lhs, const Add& rhs) {
            return compare_trees(*lhs.left, *rhs.left) && 
                   compare_trees(*lhs.right, *rhs.right);
        },
        [](const auto&, const auto&) {
            return false;
        }
    };

    return std::visit(comparator, lhs, rhs);
}

int main() {
    const Env env { {"x", 6} , {"y", 7} };
    std::cout << evaluate_no_overloaded(env, an_expr()) << '\n';
    std::cout << evaluate_with_overloaded(env, an_expr()) << '\n';
    std::cout << compare_trees(an_expr(), an_expr()) << '\n';
    std::cout << compare_trees(an_expr(), another_expr()) << '\n';
}