I'm trying to create a std::unordered_map with a boost::variant as a key and with integer value. What I'm trying to make work is this:

#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}};
}

I tried to add operator== and an hash function but get a linkage error.

CodePudding user response：

You put this in the declaration of your struct:

explicit LiteralExpr(const Literal &literal);

But you never provided an implementation for it. What is it supposed to do?

Also, for future reference, please include any error messages in the question itself. Links rot.

CodePudding user response：

If you're using a hash-based container, all the element types must be hashable and equality comparable.

Boost variant implements hashing in terms of the ADL custoimization point hash_value - which by defaults uses boost::hash<T>{}. This means the easiest way to get the hashability is to implement hash_value for all types - including boost::blank.

Next up, let's default the operator==

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

Or, if your compiler is hip enough, three-way comparison in one go:

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

Then it all compiles, and better runs without incurring UB. Make sure your hash agrees with the equality relation!

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"));
}

Prints

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

Side Notes

I'd simplify. LiteralExpr doesn't add anything over Literal (and certainly doesn't recurse).

Skip the blank unless you really need that capability (which would usually be something like Null in your AST).

All your structs seem they could be aggregates, so perhaps just enjoy aggregate construction.

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;
};

And you might homogenize the equality and hash operations a bit:

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()); }

This makes it so that the two cannot get out of sync.

Now it becomes Live Demo, 25 lines shorter and more capable:

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