Month: December 2022

When teaching data structures and algorithms in Java, I have implemented corresponding demonstrations in C++. So not to give too much solutions to the students, if I would be using Java in demos.

When demonstrating a hash table, students are given this Java skeleton of a hash table class to implement, with key-value pairs:

public class KeyValueHashTable<K extends Comparable<K>, V> implements Dictionary<K, V> {

So, how to do something similar in C++ to keep the demo closer to the Java code? For hash table, the Key class (K) must implement the Comparable interface, as well as override the hashCode() and equals() inherited from Object class.

I do not need to implement a Comparable interface in C++, since the operator overloading does what is necessary. But the Java Object.hashCode() is something I’d need to implement differently in C++, since in C++ there is no common base class to override the hashCode() from.

Instead, I need a Hashable interface in C++ and all classes that would be used as the Key in the hash table, would have to implement the Hashable interface:

class Hashable {
public:
   virtual long hashCode() const = 0;
   virtual ~Hashable() { }
};

For example, a Vehicle class can implement Hashable interface and thus can act as a Key in hash table:

class Vehicle : public Hashable {
// ...simple hash function, regNum being a std::string.
   long hashCode() const override {
      long hash = 5381;
      for (auto c : regNum) {
         hash = (hash << 5) + hash + c;
      }
      return hash;
   }

Luckily my C++ compiler supports C++20 with concepts. Now I can say in the HashTable class that the classes to be used as Keys in the hash table must conform to the Hashable interface by providing a CheckType that does the checking:

#include <utility>
#include <concepts>

template <class Type, class BaseClass>
concept CheckType = std::is_base_of<BaseClass, Type>::value;

And then finally in the HashTable, explicitly say that the Key is required to pass this check that it inherits (implements) Hashable:

template <class K, class V>
requires CheckType<K, Hashable>
class HashTable {

Now, if I would try to use Vehicle without it being a Hashable:

class Vehicle { // Not implementing the Hashable interface!
...
HashTable<Vehicle, Location> hashTable(20);

// Will result in compiler error:
Constraints not satisfied for class template 'HashTable' [with K = Vehicle, V = Location]