In learning C++ I dug in and tried to use classes and templates to solve what feels like a typical use case. I found that what I needed was Template Specialisation and that C++ does not support this very well. I came up with 3 different methods and wanted to check what others though was we the best approach. If there was a “preferred idiom in C++”, or an even better solution.
The Stack Overflow post is here:
I did get some very good answers and a lot of patience from one particular contributor (@largest_prime_is who now goes by the handle 463035818_is_not_a_number), so I owe a lot to them – thanks. From this answer, I found the best overall answer which is to use either a templated structure with a function for the hash in it, or the C++17 and constexpr.
The answer (Live Example):
This is a saved copy of the solution using the templated structure with a function:
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; }
};
I also learnt that I should frame questions very carefully on Stack Overflow.
Here is a list of things I found from posting just two questions:
- Try to post a very small thing with a very specific question. And with broken code if possible.
- Don’t expect them to reply with a solution that is just in C++. If an STL function will do the job they will consider that the answer. This is hard if you have a bigger problem that is hard to reduce down to a small example that is then not trivial enough to be solved with one library call.
- The comments section is very limited and not really to be used for chat or interactive discussion.
- There is a chat system but you have to have enough points to use it. These are gained by up votes.
- If you post a question they don’t like or your have not explained it well enough it will be down voted and you lose points.
- They have an expected style guide that you should conform to. If you don’t then the answers will all be about fixing that. I would suggest K&R brackets and one of the standard variable formats (
m_member, first_entryetc).- Don’t use
_variable_nameas this this had a lot of discussion already and the outcome is to not use it anywhere on Stack Overflow even if it is legal.
- Don’t use
- They are a tough crowd so be warned.
- To be honest it turned out not to be a tough journey, especially being a newbie. It is a shame, as it would be great to be a learner and be able to ask questions about ‘why’ rather than ‘how’.
In retrospect it is a bit obvious that I should have read the tour and read the FAQ.
For interest and for me to come back to this for future consideration, this is the original full source code with the three different methods all mixed in:
#include "stdlib.h"
#include "stdio.h"
// Implement a["word"] = 3 and b[4.5] = 4 and c[1] = 12;
// IE a toy hash table that shows how to share as much code as possible
// Use templates, but the special requirements for char* requires template specialisation.
// With no "member function partial template specialisation" in C++ try other idioms
// Whole class partial template specialisation - obvious but has virtual pointer cost.
// CRTP with partial template specialisation - less indirections so best, but ugly.
// Structure partial template specialisation - supported but has extra redirection struct.
#if 1
// Whole class partial template specialisation - obvious but has virtual pointer cost.
template <typename K>
class base {
public:
virtual int& get_value(K key) = 0; // Virtual cost an indirection.
int& operator[](K key) {
return get_value(key);
};
int& operator=(int value) {
return value;
};
size_t hash(int key) {
return key % 10;
};
int m_storage[10] {0};
};
template <typename K>
class derived : public base<K> {
public:
// Different approaches
using base<K>::hash; // Easier to read, but turns into a long list in real use cases.
class base<K>& _() { return static_cast<base<K>&>(*this); } // Simplify the clutter?
using __ = base<K>; // Typedef it another solution but more ugly perhaps?
int& get_value(K key) {
int hash_as_int = *((int*)&key);
int index = hash(hash_as_int); // Best looking but requires a list of 'using's
int index1 = _().hash(hash_as_int); // An ugly but workable?
int index2 = __::hash(hash_as_int); // An ugly but workable?
int index3 = base<K>::hash(hash_as_int);// Looks ugly and hard to read
return base<K>::m_storage[index];
};
};
template <>
class derived<const char*> : public base<const char*> {
public:
int& get_value(const char* key) {
int hash_as_int = (int)key[0];
int index = base<const char*>::hash(hash_as_int);
return base<const char*>::m_storage[index];
};
};
#endif
#if 0
// CRTP with partial template specialisation - less indirections so best, but ugly?
template <typename K, typename H>
class base {
public:
H& _() { // Standard CRTP helper function
return static_cast<H&>(*this);
};
int& operator[](K key) {
return _().get_value(key);
};
int& operator=(int value) {
return value;
};
size_t hash(int key) {
return key % 10;
};
int m_storage[10]{ 0 };
};
template <typename K>
class derived : public base<K, derived<K>> {
public:
class base<K, derived<K>>& _() {
return static_cast<base<K, derived<K>>&>(*this);
};
int& get_value(K key) {
int hash_as_int = *((int*)&key);
int index = _().hash(hash_as_int);
return _().m_storage[index];
};
};
template <>
class derived<const char*> : public base<const char*, derived<const char*>> {
public:
class base<const char*, derived<const char*>>& _() {
return static_cast<base<const char*, derived<const char*>>&>(*this);
};
int& get_value(const char* key) {
int hash_as_int = (int)key[0];
int index = _().hash(hash_as_int);
return _().m_storage[index];
};
};
#endif
#if 0
// Structure partial template specialisation - supported but has extra redirection struct.
template <typename K>
class derived {
public:
int& get_value(derived<K>* abase, K key);
int& operator[](K key) {
return get_value(this, key);
};
int& operator=(int value) {
return value;
};
size_t hash(int key) {
return key % 10;
};
int m_storage[10];
};
template <typename K>
struct get_value_impl {
int& _(derived<K>* derived, K key) {
int hash_as_int = *((int*)&key);
int index = derived->hash(hash_as_int);
return derived->m_storage[index];
};
};
template <>
struct get_value_impl<const char*> {
int& _(derived<const char*>* derived, const char* key) {
int hash_as_int = (int)key[0];
int index = derived->hash(hash_as_int);
return derived->m_storage[index];
};
};
template<typename K>
int& derived<typename K>::get_value(derived<K>* derived, K key)
{
return get_value_impl<K>::_(derived, key);
}