Make it look like std::unordered_map
When in Rome, do as the Romans do. In C++, if you are writing a container, it would be very nice if it has the same API as any other STL container. This avoids having to learn a different interface, and also makes it easier to use your container as a drop-in for an STL container without having to rewrite a lot of code that uses it. This is also part of making code more generic.
In particular, make sure the public member functions look like those of the closest matching STL container, which would be a std::unordered_map
. So:
- Change
EmplaceBack()
to emplace()
- Consider changing
Get()
to operator[]
which looks up or inserts.
- Add other typical STL container functions, like
clear()
, size()
, erase()
.
Note that the STL containers don't return std::optional
s. Of course, the STL containers themselves were designed way before std::optional
was a thing. Something you know the item already exists, or if it doesn't, you just want a default-constructed one. In those cases, operator[]()
and at()
do exactly what you want. A different function that returns a std::optional
might be nice though, since the standard way to do the same with STL containers:
auto it = container.find(key);
if (it != container.end()) {
auto &value = it->second;
...
}
...is quite annoying. Perhaps a better name than Get()
could be used though, which hints that an optional value will be returned.
Passing a hash function
Passing a function as a template parameter limits the types of functions you can pass. The STL containers that take a hash function take this as a parameter to the constructor. You can do the same thing:
template < class KeyType, class ValueType, size_t nHashGroups, class HashFunction>
class BasicHash
{
public:
BasicHash(const HashFunction& hashFunction = HashFunction()) :
hashFunction(hashFunction) {}
...
private:
size_t Hash(const KeyType& key)
{
return hashFunction(key) % nHashGroups;
}
...
HashFunction hashFunction;
};
The only drawback is that you have to pass the hash function as a function object, but that's not a problem if you use lambdas:
auto hashFunction = [](const std::string& key) -> size_t {
...
return hash;
}
...
BasicHash<std::string, TwoNumberStore, 50, decltype(hashFunction)> table(hashFunction);
Another option would be to not make the hash function type a template parameter, but to pass the hash function using a std::function<size_t(const KeyType&)>
. This has pros and cons; the advantage is that you don't need to specify the hash function type explicitly anymore, and you can pass a regular function to the constructor. The con is that there might be some performance overhead associated with std::function
.
Pass by const
reference where appropriate
You pass key
to Get()
and Hash()
using an r-value reference. However, this is not necessary, since you are not going to move from it. It also might prevent some optimizations. Prefer using const
reference whenever you want to pass a parameter you are not going to modify in any way.
Missing std::move()
in the constructor of KeyValuePair
The constructor of KeyValuePair
takes r-value references, but it just copies the values of the parameters into the member variables. You have to explicitly use std::move()
to ensure the move constructor is used if possible:
KeyValuePair(KeyType&& key, ValueType&& value) :
key(std::move(key)), value(std::move(value)) {}
Efficient storage of keys and values
Your hash table works well if you provide a good hash function and now up front how many elements you are going to store. However, it is usually hard to know exactly how much you are going to store up front, and therefore requiring nHashGroups
to be specified as a template constant is either going to make the hash table too small, leading to large buckets and eventually \$O(N)\$ performance, or it is too large and you waste a lot of memory on empty buckets.
Consider making the size of the hash table dynamic. Let the user optionally reserve()
a certain size if they do have a good estimate.
Furthermore, an empty std::list
uses 24 bytes on a 64-bit architecture, and the moment you start using it, it will have to allocate memory to store the actual contents. Instead of using buckets, consider just using a single array of KeyValuePair
s, and use open addressing to handle collisions. This does require that you can resize your hash table though.