Posted on by Mark Butler

Hash Functions for Pointers in C++

I was told on Stack Overflow:

“A pointer is just a pointer.”

Well I don’t think it is intended to be in C++. Pass by reference a struct and it knows all about it. But what about char* this is not really pointer to a char, it is a pointer to a string. There is implicit, but clear information about the intended use. The size is defined. It is just not stored.

So what does this mean for a hash function. For std::unordered_map it will check if the type being used for the key has the required functionality. It needs to be sure the key type can provide a comparison function and a hash function. These are built in for the fundamental types as the comparison is part of the language and the hash is easy to implement as size_of(type) is also known. Also for classes like std::string, they are implemented to supply these important functions.

This makes sense, but what about char*?

Here the comparison is known, strcmp(), as is the hash by knowing the length of bytes from strlen(). So it should be possible, however, it has not been implemented. unordered_map will treat char* just like it does const char*. This means that if the string is changed then the result will unexpected.

char* a_name[8];
std::unordered_map<char*, char*> my_names;

strcpy(a_name, "smith");
my_names["john"] = a_name;
strcpy(a_name, "doe");
printf("%s", my_names["john"]);   
// prints "doe" and not "smith" as might be expected.

Is there a way around this?

Presented here is are two minimum example implementation and their pros and cons.

Method 1

See how the operator[] is implemented to return a value that is not a char*. This can then capture values being assigned to it via the operator=. Finally the cast operator char* allows the internal storage to get the right char* pointer returned where map is use.

This is much cleaner than Method 2, but it relies on the order of the operators.

I am not 100% sure that the calling order of operator[] and the assignment and
cast operators are guarranteed in all use cases, but it does work in the typical cases.

class map
{
public:
	map& operator[](size_t index)
	{
		_last_used_index = index;
		return *this;
	};
	map& operator=(const char* cstring)
	{
		strcpy_s(m_data[_last_used_index], 8, cstring);
		return *this;
	};
	operator  char*() const
	{
		return (char*)_data[_last_used_index];
	}
	size_t		_last_used_index = 0; 
	char		_data[5][8] = {0};
};

Method 2

This solution does not rely on the ordering of the execution of the operators. However, it does look messier.

It uses a sub class as the return type from operator[] and returns a value for the internal storage. Then that class has an assignment overload to get a chance to store the char* being supplied, and finally has the casts to allow the use of that type in other places

class map
{
public:
	class index
	{
	public:
		char* operator=(char* cstring) {
			strcpy_s(((map*)this)->_data[_temp], 8, cstring);
			return ((map*)this)->_data[_temp];
		};
		operator char* () const {
			return (char*)((map*)this)->_data[_temp];
		}
		size_t _temp;
	};
	index& operator[](size_t index) {
		((index*)this)->_temp = index;
		return *((index*)this);
	};
	char		_data[5][8] = { 0 };
};

Both these solutions do not solve an important use case. Where the value returned from map[key] is used in a place where the compiler cannot workout what the type is expected to be, the casting operator will not get called. Hence these case have to also include explicit casting. (char*)map[key].

This limitation, and the general deprecation of char* strings in C++, are probably the reason this was not implemented in std::unordered_map.

So the journey took a long time and I ended up taking the original advice. My solution for a hash map just uses the pointer for char* and I solved the string issue in the same way as std::unordered_map but implementing an equivalent to std::string as well. Coding up the solution has also convinced me of having the backing allocators to be a reusable class of their own as well.

Running example of the code can be seen here: https://godbolt.org/z/j7eqPdrrc