散列多态类型的正确方法

Question

我有一个使用Howard Hinnant的方法(基于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));
}

所以,我需要的过载hash_append为A:

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. 做一堆dynamic_cast内部hash_append:

   • 我发现这很丑陋...特别是如果我有多个类似的类A;
   • 这很容易出错:如果有人添加了新的子项,A并且不在其中添加dynamic_cast hash_append.

有没有办法散列多态类型,而不必修改类型本身或依赖一堆dynamic_cast？

---

这样做的最终目标是能够记忆一些重要功能的结果.让我们勾勒出我的应用程序的基本结构:

struct Input { };
struct Result { };

Result solve(Input const&);

该solve函数计算量很大,所以我想使用Inputs的散列将先前计算的结果保存在文件中,例如:

// 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方法将加载和文件存储的结果,我们的目标是memoize的不同运行之间的解决方案.

如果你有关于如何记住这些结果而不必处理上述问题的建议,我将很高兴阅读它们.

Answer 1

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

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