Appropriately hash polymorphic type

Question

I have a hash process implemented using the Howard Hinnant method (shared hash_append overload hash_append ).

The purpose of this method is to create a class hash for the “memoize” result of the computation (see the end of this answer), so I ran into some problem. In particular, consider the following possible Input class, which should be hashed:

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

Now, if I want hash Input , I will have something like:

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

I need hash_append overload for A :

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

The problem is that depending on the type of runtime A I will need to add additional information to the hash file, for example. for C I need to add u .

I thought of the following solutions (and disadvantages):

• add a virtual method to A , which returns a specific value that can be added to the typeid() hash, but:

  • This means adding a method inside A that is not related to the purpose of A , so I don't really like this idea (in particular, because I have several classes of A );
  • this violates the concept of hash_append , since the method will have a unique return type for all inheriting classes.

• Make a bunch of dynamic_cast inside hash_append :

  • I found this pretty ugly ... in particular, if I have several classes similar to A ;
  • this is error prone: if someone adds new children to A and does not add dynamic_cast inside hash_append .

Is there a way to hash a polymorphic type without having to change the type itself or rely on the dynamic_cast bunch?

---

The ultimate goal is to be able to remember the results of some heavy functions. We describe the basic structure of my application:

 struct Input { }; struct Result { }; Result solve(Input const&); 

The solve function is computationally heavy, so I want to save the results of previous calculations in a file using the Input s hash, for example. something like:

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

The load and store methods will load and store the results from files, the goal is to memoize the solutions between different runs.

If you have a suggestion on how to save these results without having to discuss the above issues, I will be happy to read them.

Answer 1

You can use dual dispatch in hash_append version A and redirect the request to the desired version (i.e. either for B or C ). The downside is that you have to add a template for these classes in order to accept the visitor, and I cannot say if it is acceptable to you.
Here is a bunch of code that should illustrate the idea:

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