Posted on by Mark Butler

Member Function Partial Template Specialisation

I was messing around implementing a hash function to be able to do the equivalent of std::map_unordered. I realised that I would like to have some functions specialised but that most of them would be OK use the default implementation. I tried to do this and found the compiler would not let me. Google helped out and I found that this is not in the language. So I thought that this must have a community accepted idiom to achieve the same thing. This is the story of that journey.

Doing research on this was interesting. I discovered a number of good resources and discussion points.

Underscores in Identifiers

First up was discovering that underscores in a variable name is a topic with strong views as well as a hard C++ rule. The official rules can be seen at ccpreference.com:

  • the identifiers with a double underscore anywhere are reserved;
  • the identifiers that begin with an underscore followed by an uppercase letter are reserved;
  • the identifiers that begin with an underscore are reserved in the global namespace.

However there is a community view that even for local namespace use of the underscore prefix should be banned. Given the level of heat in this subject it would seem best to not use this in public places like Stack Overflow.

As a novice it feels like using underscore for local use in my files seems like a good thing and implies a step towards the reserved identifiers. In the past I have also seen a lot of member variables prefixed with underscore. I think I will continue to use this. Also to denote local versions of identically named library functions, but more on that in this post: C++ Coding Standards

Templates

I found an industry name, Arthur O’Dwyer, and some of his talks that were really interesting, even if I don’t understand all the details at this stage, it was still helpful to hear a knowledgable person talk about templates.

CRTP – Curiously Recurring Template Pattern

I heard Tsoding talk about CRTP in C++ and that helped me learn a new idiom for inheritance which has a natural way to specify common functions, rather than using a true hierarchy and it also saves the indirect on the virtual function that is normally needed.

This is a clever trick that passes the type of the child/derived/sub class into the parent/base/super class so that the parent (or common functions) can call the derived implementations of a member function. As the type of the child is past into the template, the parent can perform static casting to use the implementation in the child, this can be thought of as Static Polymorphism. Another way to think of this is the child classes are implementation specialisation and the parent class is just a normal class that knows how to do different things depending on the types used in the template.

Stack Overflow

With all this reading and trying things out, I came up with 3 different solutions. Now, which to use as they all have their pros and cons. I thought an idiom discussion would be of interest to those who use Stack Overflow, so I braved my first post to ask this very question, which idiom is best to work around this C++ limitation. That turned out to be an education piece in itself.

Here is the post on Stack Overflow@

https://stackoverflow.com/questions/67220778/is-this-a-good-way-to-construct-the-class-for-a-c-template-partial-specialisat

Originally the question had all 3 versions and asked what is be preferred one. The feedback included comments that the question was not well framed and that I should be asking about code that does not work. So I tried to make the question more specific and that did not really help that much more. I was also told that for bigger code questions I should post on Stack Exchange.

So I posted on Stack Exchange and was told that they do not review partial code they wanted ot see a finished implementation and for questions like mine I should post on Stack Overflow.

So I posted on Stack Overflow and… Well you get the idea.

I also reduced the question on Stack Exchange to try to get it in a form they would like, but for me that took away the real question. “What is a good idiom for this”.

I do have to give a big shout out to @largest_prime_is who was very kind and helpful. Now goes by the handle 463035818_is_not_a_number .

I will share with you the solutions I found with some pros and cons, and also explain the path I finally took in the real code I was writing.

Before that I should point out some things I learnt on Stack Overflow. I guess everyone else knows all these things, but perhaps someone else is a novice and would like to see these point before posting.

  • It is very hard to write the minimum code to put the question
    • Make sure you write it in the coding style they are used to or the comments will all be about that and not the question
  • Ask a very specific point. Obvious really, but even when you try it may not be simple enough.
    • They appear to like to have have code to fix. So ask questions like: Why does this not compile?
  • You are not supposed to have a back and forth conversation in the comments. There is a Chat feature for that. However you have to have 20 reputation points for that and as a newbie I could not use that but still was told to move the conversation to chat.
  • They are a tough crowd so be warned.
    • To be honest it turned out not to be the right place for me to ask about this sort of thing. It is a shame, as it would be great to be a learner and be able to ask questions about ‘why’ rather than ‘how’.

The Toy Project

To see the need and solutions for this, you need a reason. I started going down this rabbit hole because I was implementing my own version of std::map_unordered. This is a C++ solution to be able to do things like this even thought the language does not natively support it:

a["word"] = 3;
b[4.5] = 4;
c[1] = 12;

The idea was to support all the types for the key and value while sharing as much code as possible. That requires separate processing for char*. Basic types and well built classes will automatically be able compared and copied into the backing storage, but char* will need a special function for the hashing and comparing.

The solutions below are:

  • Whole class partial template specialisation
    • Obvious idiom but has virtual pointer cost and a lot of duplicated code.
    • I did not write this one out as it is easy to do.
  • CRTP with partial template specialisation
    • Less indirections, but a bit ugly and requires some focus on where the code lives.
  • Structure partial template specialisation
    • Doing this in structures is supported in C++, but it has extra redirection through the structure.
  • Using compile time decision if constexpr
    • This is nice as all the code can be in one class, but requires C++ 17. The fall back can be made to work but requires some messy casting.

CRTP with Partial Template Specialisation

template <typename K>
class hash_table_common
{
public:
	// Going via virtual cost an indirection.
	virtual int& get_value(K key) = 0; 
	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 hash_table : public hash_table_common<K>
{
public:
	// Different approaches
	// Easier to read, but  will turn into a long list.
	using hash_table_common<K>::hash;
	// This is one way to simplify the clutter.
	class hash_table_common<K>& hash_table_common1()
	{
		return static_cast<hash_table_common<K>&>(*this);
	} 
	// Typedef it another solution but more ugly perhaps?
	using hash_table_common2 = hash_table_common<K>;		

	int& get_value(K key)
	{
		int hash_as_int = *((int*)&key);

		// Best looking case but requires a list of 'using's
		int index = hash(hash_as_int);
		// An ugly but workable?
		int index1 = hash_table_common1().hash(hash_as_int);	
		// An ugly but workable?
		int index2 = hash_table_common2::hash(hash_as_int);
		// The default solution but looks ugly and hard to read
		int index3 = hash_table_common<K>::hash(hash_as_int);

		return hash_table_common<K>::m_storage[index];
	};
};

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

Whole class partial template specialisation

Links