使用 boost::recursive_variant 和 std::unordered_map

Question

我正在尝试创建一个 std::unordered_map，其中 boost::variant 作为键，整数作为值。我正在尝试完成这项工作：

#include <boost/variant.hpp>

#include <unordered_map>
#include <string>

enum Token {};

struct AssignExpr;
struct LiteralExpr;

using Expr = boost::variant<boost::blank, 
                            boost::recursive_wrapper<AssignExpr>,
                            boost::recursive_wrapper<LiteralExpr>>;

using Literal = int;

struct LiteralExpr {
  Literal literal;

  explicit LiteralExpr(const Literal &literal);
};

struct AssignExpr {
  Token name;
  Expr value;

  AssignExpr(const Token &name, const Expr &val);
};

int main() {
  LiteralExpr li{0};
  AssignExpr ae{{}, li};

  std::unordered_map<Expr, std::size_t> m_locals{{li, 10}, {ae, 20}};
}

我尝试添加 operator== 和哈希函数，但 get 出现链接错误。

Answer 1

如果您使用的是 hash-based 容器，所有元素类型都必须是可散列的和相等可比较的。

Boost 变体根据 ADL 自定义点 hash_value 实现哈希 - 默认情况下使用 boost::hash<T>{}。这意味着获得可哈希性的最简单方法是为所有类型实现 hash_value - 包括 boost::blank.

接下来，让我们默认 operator==

bool operator==(LiteralExpr const&) const = default;
bool operator==(AssignExpr const&) const = default;

或者，如果您的编译器足够时髦，three-way 一次比较：

auto operator<=>(LiteralExpr const&) const = default;
auto operator<=>(AssignExpr const&) const = default;

然后就全部编译通过了，更好的运行，不会产生UB。确保你的散列符合等式关系！

Live Demo

#include <boost/variant.hpp>
#include <boost/functional/hash.hpp>

#include <string>
#include <unordered_map>
#include <utility>

namespace boost {
    [[maybe_unused]] static inline size_t hash_value(boost::blank) { return 0; }
} // namespace boost

namespace MyLib {
    using boost::hash_value;

    enum Token {A,B,C,D,E,F,G,H};

    [[maybe_unused]] static constexpr auto name_of(Token tok) {
        return tok["ABCDEFGH"];
    }

    struct AssignExpr;
    struct LiteralExpr;

    using Expr = boost::variant<                //
        boost::blank,                           //
        boost::recursive_wrapper<AssignExpr>,   //
        boost::recursive_wrapper<LiteralExpr>>; //

    using Literal = int;

    struct LiteralExpr {
        Literal literal;

        explicit LiteralExpr(Literal literal) : literal(literal) {}

        auto operator<=>(LiteralExpr const&) const = default;
        friend size_t hash_value(LiteralExpr const& le) {
            return hash_value(le.literal);
        }

        friend std::ostream& operator<<(std::ostream& os, LiteralExpr const& le) {
            return os << le.literal;
        }
    };

    struct AssignExpr {
        Token name;
        Expr  value;

        AssignExpr(Token name, Expr val) : name(name), value(std::move(val)) {}

        auto operator<=>(AssignExpr const&) const = default;
        friend size_t hash_value(AssignExpr const& ae) {
            auto h = hash_value(ae.name);
            boost::hash_combine(h, hash_value(ae.value));
            return h;
        }

        friend std::ostream& operator<<(std::ostream& os, AssignExpr const& ae) {
            return os << name_of(ae.name) << " := " << ae.value;
        }
    };

} // namespace MyLib

#define FMT_DEPRECATED_OSTREAM
#include <fmt/ranges.h>
#include <fmt/ostream.h>
template <> struct fmt::formatter<MyLib::Expr> {
    auto parse(auto& ctx) const { return ctx.begin(); }
    auto format(MyLib::Expr const& e, auto& ctx) const {
        return boost::apply_visitor(
            [&](auto const& el) { return format_to(ctx.out(), "Expr({})", el); },
            e);
    }
};

int main() {
    using namespace MyLib;

    LiteralExpr li{42};
    AssignExpr  ae{D, li};

    std::unordered_map<Expr, std::size_t> m_locals{{li, 10}, {ae, 20}};

    fmt::print("{}\n", fmt::join(m_locals, "\n"));
}

版画

(Expr(D := 42), 20)
(Expr(42), 10)

旁注

我会简化。 LiteralExpr 不会在 Literal 上添加任何内容（当然也不会递归）。

跳过 blank 除非你真的需要那个能力（在你的 AST 中通常类似于 Null）。

你所有的结构似乎都可以是聚合体，所以也许只是享受聚合体构造。

struct Nil {
    friend constexpr size_t hash_value(Nil) { return 0; }
    constexpr bool operator==(Nil) const { return true; }
};

using Literal = int;

struct AssignExpr;
using Expr = boost::variant<               //
    Nil,                                   //
    Literal,                               //
    boost::recursive_wrapper<AssignExpr>>; //

enum Token {A,B,C,D,E,F,G,H};

struct AssignExpr {
    Token name;
    Expr  value;
};

你可能会稍微同质化相等和散列操作：

auto key() const { return std::tie(name, value); }

bool operator==(AssignExpr const& rhs) const { return key() == rhs.key(); }
friend size_t hash_value(AssignExpr const& ae) { return hash_value(ae.key()); }

这使得两个不能不同步。

现在变成了Live Demo，缩短了25行，功能更强大：

(Expr(Nil), 30)
(Expr(D := 42), 20)
(Expr(42), 10)

使用 boost::recursive_variant 和 std::unordered_map

Using boost::recursive_variant with std::unordered_map

c++

boost

旁注