Is this a good way to construct the class for a C++ template partial specialisation of a member function?

user_15742708 0
Viewed 170

I am teaching myself c++ by doing a series of exercises. I liked the idea of working out how hash tables could be done using just the language and no std calls. I discovered that you cant do "class member function partial template specialisation" and so worked on options for how this would be achieved. The code below is a stripped down version of the useful parts of a hash table. Leaving just enough to show the structure of what is needed.

Is there a better way to construct the class - IE a better idiom to solve partial specialisation?

I have tried full class specialisation and struct partial template specialisation but this seems the best so far.

I would be interested in comments about other ways to call the members and fuctions. I have thought of:

  1. A 'using' line for all the members/function in the fuctions.
  2. One 'using' line to create a typedef that can be used as the prefix.
  3. Putting the full cast at each use.
#include "stdio.h"

template <typename K, typename H>
class hash_table_common {
public:
    H& hash_type()                          // Standard CRTP helper function
    {
        return static_cast<H&>(*this);
    }
    int& operator[](K key)
    {
        return hash_type().get_value(key);
    }
    size_t hash(int key)
    {
        return key % 10;
    }
    int m_storage[10]{ 0 };
};

template <typename K>
class hash_table : public hash_table_common<K, hash_table<K>> {
public:
    class hash_table_common<K, hash_table<K>>& hash_type()
    {
        return static_cast<hash_table_common<K, hash_table<K>>&>(*this);
    }
    int& get_value(K key)
    {
        int hashable = 3; // value_to_int(); Real code will go here, for this demo it works for one value!
        int index1 = hash_type().hash(hashable);
        return hash_type().m_storage[index1];
    }
};

template <>
class hash_table<const char*> : public hash_table_common<const char*, hash_table<const char*>> {
public:
    class hash_table_common<const char*, hash_table<const char*>>& hash_type()
    {
        return static_cast<hash_table_common<const char*, hash_table<const char*>>&>(*this);
    }
    int& get_value(const char* key)
    {
        int hash_as_int = (int)key[0];
        int index = hash_type().hash(hash_as_int);
        return hash_type().m_storage[index];
    }
};
#endif

int main() {
    class hash_table<const char*> a;
    class hash_table<float> b;
    a["word"] = 3;
    b[4.5f] = 14;
    printf("%d %d", a["word"], b[4.5f]);
    return 0;
}
idioms crtp templates class c++
3 Answers

First, lets consider your example of implementing a hashtable. I made some small modifications to your main:

int main() {    
    my_hash_table<const char*> c;
    my_hash_table<float> d;
    c["word"] = 3;
    d[4.5f] = 14;
    std::cout << c["word"] << " " << d[4.5f] << "\n";
}

Lets take this as test case that we want to pass.

Ignoring deficiencies of the implementation and only talking about design, this is what is needed to "pass the test" and have specializations for const char* and float:

#include <map>
#include <iostream>
#include <type_traits>

template <typename T>
struct my_hash {
    size_t operator()(const T& t){ return t;}
};
template <typename key_t,typename hash = my_hash<key_t>,typename value_t = int>
struct my_hash_table {
    std::map<size_t,value_t> table;
    value_t& operator[](key_t key){ return table[hash{}(key)]; }
};
template <>
struct my_hash<const char*> {
    size_t operator()(const char* t){ return t[0]; }
};
template <>
struct my_hash<float> {
    size_t operator()(const float& t) { return t*100; }
};

Don't get me wrong, but your code looks like you tried to squeeze everything into one class. Not everything related to a class must be inside the class' definition. Rather, the less there is in the definition of a class, the better. Functors are typically rather light-weight, they have an operator() (ie they can be called) and often thats it. You can easily add specializations for my_hash.

Also, inheritance has its place, but to be honest, I don't understand what purpose it serves in your code. Last, but not least you are mixing the hashing function with the container, but those are seperate concerns. A different container might use the same hashing function and you might want to use the same data structure with a different hash.

"Class member function partial template specialisation" isn't a thing. Though, that does not pose a problem per se. It's just a tool we do not have in our box. When you want member function of a class template to do something special depending on only one of the paramters, you can do that. Either as above, or C++17 introduced if constexpr :

template <typename A> struct foo { void operator()() {} };
template <> struct foo<int> { void operator()(){ std::cout << "A is int\n";}};

template <typename A,typename B>
struct bar {
    void do_something() {
        
        foo<A>{}();

        if constexpr (std::is_same_v<A,int>){
            std::cout << "A is int\n";
        }
    };
};

Live Example

user_41177280

Using the struct approach from @largest this is another solution candidate for the best idiom for this use case. I think I still like the CRTP option due to its symetric way of calling the other parts functions and members. hash_type()

In the code below there must be better names for hash_table_functions amd table as these should be invisible redirections I want say _{} and _ but the underscore police will come after me (lol).

#include <stdio.h>
#include <stdint.h>

template <typename key_t>
struct hash_table_struct;

template <typename key_t, typename hash_table_functions = hash_table_struct<key_t>>
class hash_table {
public:
    int& operator[](key_t key)
    {
        return hash_table_functions{}.get_value(*this, key);
    };
    size_t hash(uint32_t key)
    {
        return key % 10;
    }
    int m_storage[10];
};

template <typename key_t>
struct hash_table_struct {
    int& get_value(hash_table<key_t>& table, key_t key)
    {
        uint32_t hashable = (uint32_t)key;
        size_t index = table.hash(hashable);
        return table.m_storage[index];
    }
};

template <>
struct hash_table_struct<const char*> {
    int& get_value(hash_table<const char*>& table, const char* key)
    {
        uint32_t hashable = (uint32_t)key[0];
        size_t index = table.hash(hashable);
        return table.m_storage[index];
    }
};

#endif

int main() {
    class hash_table<const char*> a;
    class hash_table<float> b;
    a["word"] = 3;
    b[4.5f] = 14;
    printf("%d %d", a["word"], b[4.5f]);
    return 0;
}
user_157427080

The constexpr version Which only works on C++17. Emululated is_same_v to keep to the original rules. This was useful as it taught me how that all works. This results in much cleaner and easier to read code.

// C++ 17 required
#include <stdio.h>
#include <stdint.h>

template<class type1, class type2>
struct is_same
{
    static constexpr bool _value = false;
    constexpr operator bool() const noexcept { return _value; }
};

template<class type1>
struct is_same<type1, type1>
{
    static constexpr bool _value = true;
    constexpr operator bool() const noexcept { return _value; }
};

template<class type1, class type2>
inline constexpr bool is_same_v = is_same<type1, type2>::_value;

template <typename key_t>
class hash_table {
public:
    int& operator[](key_t key)
    {
        return get_value(key);
    };
    size_t hash(int key)
    {
        return key % 10;
    }
    int m_storage[10]{ 0 };
    int& get_value(key_t key)
    {
        uint32_t hashable;
        if constexpr ( is_same_v<key_t, const char*> )
        {
            hashable = (uint32_t)key[0];
        }
        else
        {
            hashable = (uint32_t)key;
        }
        size_t index = hash(hashable);
        return m_storage[index];
    }
};

int main()
{
    class hash_table<const char*> a;
    class hash_table<float> b;
    a["word"] = 3;
    b[4.5f] = 14;
    printf("%d %d", a["word"], b[4.5f]);
    return 0;
}
user_157427080
Related