c++ - 散列多态类型的正确方法

Question

我有一个使用 Howard Hinnant's method 实现的哈希过程(基于 hash_append 重载的通用哈希)。

该方法的目的是创建类的散列，以便“记住”计算结果(请参阅本答案的末尾)，所以我遇到了一些问题。特别是，考虑以下可能需要散列的 Input 类:

struct A {
    virtual int do_stuff() const = 0;
    virtual ~A(); 
};
struct B: A {
    int do_stuff() const override { return 0; }
};
struct C: A {
    const int u;
    int do_stuff() const override { return u; }
};

struct Input {
    A const& a; // store a reference to an instance of B or C
};

现在，如果我想对 Input 进行哈希处理，我将得到如下内容:

template <class HashAlgorithm>
void hash_append(HashAlgorithm& h, Input const& input) {
    hash_append(h, typeid(input));
    hash_append(h, typeid(input.a));
}

所以我需要为 A 重载 hash_append:

template <class HashAlgorithm>
void hash_append(HashAlgorithm& h, A const& a) {
    hash_append(h, typeid(a)); 
}

这里的问题是，根据 a 的运行时类型，我需要向散列中添加额外的信息，例如对于 C，我需要添加 u。

我想到了以下解决方案(和缺点):

1. 向 A 添加一个虚方法，该方法返回一个特定值，该值可以添加到 typeid() 散列中，但是:

   • 这意味着在 A 中添加一个与 A 的目的无关的方法，因此我不太喜欢这个想法(特别是因为我有多个A类)；
   • 这打破了 hash_append 的概念，因为该方法将对所有继承类具有唯一的返回类型。

2. 在 hash_append 中做一堆 dynamic_cast:

   • 我发现这很丑陋......特别是如果我有多个类似于 A 的类；
   • 这很容易出错:如果有人添加了 A 的新子代并且没有在 hash_append 中添加 dynamic_cast。

有没有一种方法可以散列多态类型，而无需修改类型本身或依赖一堆 dynamic_cast？

---

这样做的最终目标是能够记住一些繁重函数的结果。让我们勾勒出我的应用程序的基本结构:

struct Input { };
struct Result { };

Result solve(Input const&);

solve 函数的计算量很大，所以我想使用 Input 的哈希将先前计算的结果保存在文件中，例如像这样的东西:

// depends on hash_append
std::string hash(Input const&);

Result load_or_solve(Input const& input) {
    auto h = hash(input);
    Result result;
    if (exists(h)) { // if result exists, load it
        result = load(h);
    }
    else { // otherwize, solve + store
        result = solve(input);
        store(h, result);
    }
    return result;
}

load 和 store 方法将从文件加载和存储结果，目标是在不同运行之间记住解决方案。

如果您有关于如何在不处理上述问题的情况下记住这些结果的建议，我将很乐意阅读它们。

Answer 1

您可以在 A 的 hash_append 版本中使用双重调度，并将请求转发到正确的版本(即 B 或 C)。缺点是您必须向这些类添加样板文件才能接受访问者，我不能说您是否可以接受。
这里有一堆代码可以说明这个想法:

struct B;
struct C;

struct Visitor {
    virtual void visit(const B &) = 0;
    virtual void visit(const C &) = 0;
};

template<typename T, typename... O>
struct HashVisitor: T, HashVisitor<O...> {
    template<typename U>
    std::enable_if_t<std::is_same<T, U>::value> tryVisit(const U &u) {
        T::operator()(u);
    }

    template<typename U>
    std::enable_if_t<not std::is_same<T, U>::value> tryVisit(const U &u) {
        HashVisitor<O...>::visit(u);
    }

    void visit(const B &b) override { tryVisit<B>(b); }
    void visit(const C &c) override { tryVisit<C>(c); }
};

template<>
struct HashVisitor<>: Visitor {};

template<typename... F
auto factory(F&&... f) {
    return HashVisitor<std::decay_t<F>>{std::forward<F>(f)...};
}

struct A {
    virtual void accept(Visitor &) = 0;
    virtual int do_stuff() const = 0;
    virtual ~A();
};

struct B: A {
    void accept(Visitor &v) override { v.visit(*this); }
    int do_stuff() const override { return 0; }
};

struct C: A {
    const int u;
    void accept(Visitor &v) override { v.visit(*this); }
    int do_stuff() const override { return u; }
};

template <class HashAlgorithm>
void hash_append(HashAlgorithm &, const B &) {
    // do something
}

template <class HashAlgorithm>
void hash_append(HashAlgorithm &, const C &) {
    // do something
}

template <class HashAlgorithm>
void hash_append(HashAlgorithm &h, const A &a) {
    auto vis = factory(
        [&h](const B &b){ hash_append(h, b); },
        [&h](const C &c){ hash_append(h, c); }
    );

    a.accept(vis);
}