Doubts about classes and polymorphism

user_5922196 0
Viewed 65

I'm trying to build a hash table class in C++ using the chaining method, a minimal example class is:

template <class V>                                                                  
class HashTable {                                                                                                                                                                                                            
private:                                                                                                       
  //some parameters to define the hash_table                                                                                                  
  HashFunc * h;  //family of hash functions                                                                                                                                                                                                                                                          
public:                                                                                                       
  /*other functions*/                                                                       
};

I'm having some troubles with the member HashFunc * h, which is the hash function I intend to use to store pairs <key,value> in the hash table. In my main, I need to build two different hash tables, one which hashes integers and another one which hashes strings.

My doubts are:

  1. A natural choice for me would be to use polymorphism for the hash function in the following way (mind that I have limited experience with classes and polymorphism):
class HashFunc{
public:
  virtual int operator()()=0;
}
    
class IntegerHashFunc: public HashFunc
{
  //parameters to hash integers
 public:
  int operator()(int x){
    //operations for integer hashing
  }
}

class StringHashFunc: public HashFunc
{
  //parameters to hash strings
  IntegerHashFunc h_integer; //string->integer->integer hash
  public:
    int operator()(string name){
      int result=0;
      //operations for string hashing
      return h_integer(result); //I need to hash the integer resulting from string "hashing"
    }
}

But this won't work because the operator()(string name) in StringHashFunc has different arguments and thus doesn't override the virtual method in the base class. How to make this work?

  1. I'm not sure on how to make this work in the constructor for the HashTable class: how to choose between the two methods? Should I just use a flag in the constructor like:
template<class V>
HashTable<V>::HashTable(/*args*/, int flag){
  //other parameters
  switch(flag){
    case 1:
      h=new IntegerHashFunc(/*args for integer hashing*/);
    case 2:
      h=new StringHashFunc(/*args for string hashing*/);
  }
}

or is there a better way?

  1. Is there a better and more natural way to do what I want to do? For example, I tried using a single class HashFunc with two overloads operator()(int) and operator()(string), but I don't want to "carry" around string parameters and methods if I'm working just with integers.
hash polymorphism class c++
2 Answers

TL;DR - the answer to all questions is "use templates, not polymorphism".

A natural choice for me would be to use polymorphism for the hash function in the following way (mind that I have limited experience with classes and polymorphism):
But this won't work because the operator()(string name) in StringHashFunc has different arguments and thus doesn't override the virtual method in the base class. How to make this work?

You cannot. In order to make the derived class non abstract, you need to override all pure virtual functions. And even if you add another overload with parameter, it doesn't help, because you can't call those overloads with base class pointer.
Theoretically, you can do dynamic_cast to determine what the actual type is (in a long, long chain of if statements), but that's discouraged.

I'm not sure on how to make this work in the constructor for the HashTable class: how to choose between the two methods? Should I just use a flag in the constructor like:
or is there a better way?

One option would be to use type traits to select the right branch (assuming you really, really want to use polymorphism):

if(std::is_same_v<V, int>) 
    h=new IntegerHashFunc(/*args for integer hashing*/);
else if(std::is_same_v<V, std::string>)
    h=new StringHashFunc(/*args for string hashing*/);

Is there a better and more natural way to do what I want to do? For example, I tried using a single class HashFunc with two overloads operator()(int) and operator()(string), but I don't want to "carry" around string parameters and methods if I'm working just with integers.

Yes, use templates, like the standard library hash table (aka. std::unordered_map) does:

template<typename T>
class HashFunc{
public:
  int operator()(const T&) const;
};

template<>
class HashFunc<int>{
public:
  int operator()(const int&) const {
    // do calculations for int
  }
};

template<>
class HashFunc<std::string>{
public:
  int operator()(const std::string&) const {
    // do calculations for std::string
  }
};

//etc... for all other specializations

template <class V>                                                                  
class HashTable {                                                                                                                                                                                                            
private:                                                                                                       
  //some parameters to define the hash_table                                                                                                  
  HashFunc<V> h;  //family of hash functions                                                                                                                                                                                                                                                          
public:                                                                                                       
  /*other functions*/                                                                       
};

Or better yet, use the already existing std::hash, which does exactly this, but is already implemented.

user_79768050

Use policy based design and it will be much simpler.

First create your hash functions objects:

struct IntegerHashFunc
{
  int operator()(int x){ return x; }
};

struct StringHashFunc
{
  IntegerHashFunc h_integer; //string->integer->integer hash
    int operator()(string name){
      int result=0;
      return h_integer(result);
    }
};

Your HashTable class will take the Hash function as a template parameter.

template <typename Key, typename Val, typename HashFunctionPolicy = IntegerHashFunc>
class HashTable {                                                                                                                                                                                                            
private:                                                                                                       
  //some parameters to define the hash_table                                                                                                                                                                                                                                                         
public:                                                                                                       
  /*other functions*/
  void somefunction(Key key)
  {
      HashFunctionPolicy f;
      auto x = f(key);
  }                                                                   
};
user_22794220
Related