Multiple Template Inheritance

[EleKtroFR]

Hello.

I'm having troubles with this problem:

I Have a template class, named "HashMap" , which includes, in its public area an inner class named "Hashable":

HashMap declaration:
template <typename K, typename V> class HashMap;

Hashable

class is an interface which provides a public method called:

int hashCode()

which is meant to return a int value based on the object state extending this interface.

My Problem is:

I have an object, instance of "Stack" class. This class doesn't extend Hashable, so i need to create a new class which extends Stack and Hashable class.

These are the class involved, i need to combine 2. and 3. in order to create a HashMap<NewStackClass<int>,int>.

1. template <typename K, typename V> class HashMap;
2. template <typename T> class Stack;
3. template <typename K, typename V> class HashMap<K,V>::Hashable;

Any Help is appreciated.

[Golden Lizard]

I have an object, instance of "Stack" class. This class doesn't extend Hashable, so i need to create a new class which extends Stack and Hashable class.

So, you want a multiple inheritance that has also multiple templates? I guess you need something like this.

#include<iostream>
#include<thread>

template<typename a, typename b>
class c1
{
 public:
	void print0(void)
	{
		std::wcout << sizeof(a) << '\n';
		std::wcout << sizeof(b) << '\n';
	}
};

template<typename c>
class c2
{
   public:
	void print1(void)
	{
		std::wcout << sizeof(c) << '\n';
	}
};


template<typename A, typename B, typename C>
class multi : public c1<A, B>, public c2<C>
{
    public:
	void print2(void)
	{
		print0();
		print1();
	}
};

int main()
{
	multi<short,long, double> obj;
	obj.print2();

	std::this_thread::sleep_for(std::chrono::seconds(20));
	return EXIT_SUCCESS;
}

Output:

2
4
8

[EleKtroFR]

Thanks for your answer, i'll try to be clearer since my problem still exists:

This is HASHMAP_H:

#ifndef HASHMAPHEADER_H
#define HASHMAPHEADER_h
#include <stdint.h>

#include "..\ListHeaders\ListHeader.h"

template <class K,class V> class HashMap{
	
	public:
		
		static const int TABLE_SIZE=347;
		
		class Hashable{
	
			public:
			
				virtual int hashCode() const =0;
		};
		
	private:
		
		int hash(const Hashable& key) const{
			
			return (31*17 +key.hashCode()) % TABLE_SIZE;
		}
	
		int hash(const Hashable* key) const{
			
			return (31*17 +key->hashCode()) % TABLE_SIZE;
		}
};


#include "HashEntryCode.h"
#include "HashMapCode.h"

#endif 

I have this class:

template <typename T> class NotHashableStudent {
	
	public:
		
		NotHashableStudent(const char *name){
			
			this->name=name;
		}	
		
		NotHashableStudent(const NotHashableStudent& student){
			
			this->name=student.name;
		}
	
		bool operator==(const NotHashableStudent& student) const{
			
			return this->name==student.name;
		}
		
	protected:
		
		T value;
		const char*name;
};

Since i need a HashMap with Student objects as keys, i need to extend NotHashableStudent class.

template<typename A,typename K, typename V> class HashableStudent : public NotHashableStudent<A>, public HashMap<K,V>::Hashable{
	
	public:
		
		virtual int hashCode() const{
					
			return 31*17 +(uintptr_t)this->name;
		}
		
		bool operator==(const NotHashableStudent<A>& student) const{
			
			return this->name==student.name;
		}	
};

My Intention is to instantiate this:
HashMap<HashableStudent<int>,int> map;


And let my HashMap use the hashcode() method inherited from Hashable interface, to have HashableStudent instances as keys.

But my HashableStudent class needs three parameters:

1. The Student type (A);
2. The HashMap key Type (K);
3. The HashMap value Type (V);

The problem is that K= HashableStudent<A,K,V>.

How should i instantiate it?

[gunnerfunner]

HashableStudent<int> - this is wrong, class template HashableStudent<...> takes three parameters, not one HashableStudent<A,K,V>, unless you have provided default values for the type parameters K and V elsewhere, not show on this thread

Your current design has a circular problem - to instantiate Hashmap<HashableStudent<A, K, V>, int>> its key-type HashableStudent<A, K, V> needs to be a complete type but this in turn is derived from HashMap<K, V> and so no ...

[EleKtroFR]

Thanks for your answer gunnerfunner.. I tried this, we are getting near to the point now:

template <typename T> class NotHashableStudent {
	
	public:
		
		NotHashableStudent(){}
		
		NotHashableStudent(const char *name){
			
			this->name=name;
		}	
		
		NotHashableStudent(const NotHashableStudent<T>& student){
			
			this->name=student.name;
		}
	
		bool operator=(const NotHashableStudent<T>& student){
			
			this->name=student.name;
		}	
		
		bool operator==(const NotHashableStudent<T>& student) const{
			
			return this->name==student.name;
		}
		
	protected:
		
		const char*name;
};

template<typename A, typename V> class HashableStudent : public NotHashableStudent<A>, public HashMap<HashableStudent<A,V>,V>::Hashable{
	
	friend ostream& operator<<(ostream& out, const HashableStudent<A,V>& student){
		
		out << student.name;
		return out;
	}
	
	public:

		HashableStudent(){}
		
		HashableStudent(const char *name) : NotHashableStudent<A>(name){}	
		
		HashableStudent(const HashableStudent<A,V>& student) : NotHashableStudent<A>(student){}
		
		virtual int hashCode() const{
					
			return (uintptr_t)this->name;
		}
};

int main(int argc, char** argv) {
	
	HashMap<HashableStudent<int,int>*,int> map;
	HashableStudent<int,int> st1("Marcus");
	map.put(&st1,0);
	
	cout << map << endl;
	
	return 0;
}

If I choose to not use pointers:
HashMap<HashableStudent<int,int>,int> map

Everything works fine and method:

int hash(const Hashable& const key) const{
			
        return (31*17 +key.hashCode()) % TABLE_SIZE;
}

calls the correct hashCode() method.

But if i use pointers this problem occurs:

[Note] no known conversion for argument 1 from 'HashableStudent<int, int>* const' to 'const HashMap<HashableStudent<int, int>*, int>::Hashable*'

Even if my HashMap class has this method:

int hash(const Hashable* const key) const{
			
	return (31*17 +key->hashCode()) % TABLE_SIZE;
}

Which is used when i'm using pointers instead of references.

Any help?

Also, my HashableStudent is a subclass of Hashable, so HashableStudent * => Hashable*, right?

[mbozzi]

One solution is to make Hashable independent of the hash table. Avoid coupling it to everything and provide template specializations instead.

template <typename T>
struct Hash { }; 
template <>
struct Hash<YourClass> { int hashCode(YourClass const&) const { ... }; };
template <typename K, typename V> class Hashtable;

[EleKtroFR]

THANKS FOR THE ANSWER! This solved my problem, but i didn't use template specializations. I'm not so good at that... How should i make this? And how should i modify my method inside HashMap class?

int hash(const Hashable& key);
int hash(const Hashable *const key);

Finally, I have two questions:

1. Why should i make it independent in order to work?
2. Should i use class or struct? why?

[Golden Lizard]

1. Why should i make it independent in order to work?

Well, it makes the code much cleaner and less error-prone to begin with. Also objects stored inside should be more container "agnostic", a good container (like a hash table) should store any kind of objects, just think about the STL, you have hash tables there, both with value-key pair and value only. For hashing you may consider passing a lambda/function pointer/functor so if you got some more special objects you can still use a "hashing" seed.

2. Should i use class or struct? why?

Struct is the same as class, except that values by default in a struct are public, while in a class they are private.

e.g:

class A
{
     int value;
}

//it's the same as

class A
{
   private:
     int value;
}

struct A
{
     int value;
}

//it's the same as

class A
{
   public:
     int value;
}
//or

struct A
{
   public:
     int value;
}

[mbozzi]

I'm glad to hear!

Doing things out-of-order -- your 2 questions first.

Why should i make it independent in order to work?

1. The snarky answer is that it's impossible to use a dependent name in terms of the dependency (well, without some complicated stuff to help, anyways).

The real answer is that the concept of a hash function is independent of a hash-table. In other words, you can hash something without having a hash-table around.

That's a clear sign that the two concepts should be separated in code. This is because it's much more difficult to handle two interrelated concepts than two independent concepts. By defining a hashable object in terms of a hash table, your code made things seem much more complicated than they actually are.

A good guideline is that whenever two concepts can be separated, they should be separated. Do this in your programs.

Another less-general guideline suggests that a nested class should only be used internally by the class it is defined in terms of. (i.e., the use of a nested class should be an implementation detail). If it needs to be exposed it should be defined outside the class.


2. I used struct { ... }; for 2 reasons:
-- It's shorter than class { public: ... };
-- Our struct Hash is much closer to a function than an object. Instead it's closer to what category theory calls a morphism or a functor. In C++ terms that's a "callable object" or a lambda-expression.
Why's it more a function than an object? Because in the context of the name struct Hash, "hash" is a verb; the object itself does nothing except hash some values. It carries no state and doesn't represent any single hash, it just has a member function that takes a value and hashes it.

Whether or not to use struct or class is preference, though. I usually write function objects with struct.

I didn't use template specializations

If you didn't use template specializations I'm assuming you wrote a (potentially overloaded) free or member function that takes an instance of the type you need to hash and returns the hash.
Something like int hash(Student const& s) { ... }. Please correct me if I'm wrong.

This is fine, but using a template class member function has two main advantages:
1. By making it a class you get the ability to hold state, cleanly -- this might be useful if you have special requirements for a particular hash function.
2. By using specializations instead of function overloads you can create compatible hash objects without ever having to modify the module's code -- that's the Hash class or the Hash table.

How should i make this

Given that template specializations are acceptable, and some class you want to hash like this:

template<typename T> class Student {
public:
  std::string get_name() const;	
};

Something like this:

// empty object -- we don't know how to hash everything.  
template <typename T> struct Hash { };
// specialization for hashing Student (i.e., hash<Student> can hash a student)
template <> struct Hash<Student> {
  // borrowing your hashing algorithm,
  // overloading the function-call operator:
  unsigned operator() (Student const& s){ return 31 * 17 + (uintptr_t)(&s); }
};

And whenever you need a Student's hash inside HashTable, simply

template <typename K, typename V> class HashTable {
public:
  int foo(K const& key) const { auto hashCode = hash(key); }; 
private:
  Hash<K> hash;
}; 

Quick note: 31*17 +(uintptr_t)this->name;
In your hash function this expression has the potential to be overflow when converted to int (which is the return value). If I'm not mistaken, signed integer overflow is undefined behavior. Change the return value to unsigned int.

[EleKtroFR]

First, thanks for the tip about the return type. I didn't know this.

Second, i'll try to put Hashable and HashMap in a single Namespace, and make many specializations of Hashable, since i'm simply overloading the hash method many times inside my HashMap class, making it a bit longer to read, and using a single templated "object" is much more comfortable to read. i'm coupling Hashable and HashMap simply because, at the moment, the only context in which i would use Hashable interface is in HashMaps

Finally, this problem has been solved, however:

What if i MUST use an inner class (public) and use it exactly how i was using Hashable before? Is this possible? I understand the need of keeping things separate but if, in future, this solution would not be applicable, will it be possible to overcome the issue?

Really thanks for your help.

[mbozzi]

What if I MUST use an inner class (public) and use it exactly how i was using Hashable before? Is this possible?

No, because you'll end up needing to instantiate

using map_hashable_student = Map1<HashableStudent<Student<T>, 
                                  Map1<HashableStudent<Student<T>,
                                      Map1<...>>>;

Which is an infinitely recursive type.

You can use recursive types as long as there is a way to terminate the recursion. This is relatively fundamental, but since there is no such base-case this is not possible.

You can get more or less close depending on the semantics you require but that's not clear from such a general question. Maybe this is closer to what you're thinking?

template <typename K, typename V> struct Map2 {
    struct Hashable_K: public K {
        unsigned hashCode(K const&) const { /* your hash algorithm here */ }     
    };
};