Re: Yet another template class question (corrected)
On 2007-08-31 15:05, Anonymous wrote:
I am writing a template HashTable class. I have got it working, but I
want to make the code more generic and more robust. The current code
looks something like this:
template <class InnerType, class KeyType, class KeyToSizeT>
class myHash
{
// Impl here
};
Where:
InnerType is the data type being stored
I'd call it ValueType
KeyType is the data type of the hash key
KeyToSize is the function that returns the size of the hash key
I am now mandating that InnerType MUST implement interface IHashable:
I think you've confused things here, it is the KeyType you should hash,
not the value. Unless you plan to first hash the key, and then hash the
value, but that seems to me like either you have a bad hash-function for
the key or a multi-hash-map (i.e. the keys don't have to be unique).
I'm not an expert but I'd do something like this:
template <typename ValueType, size_t TableSize = 100>
class HashTable
{
std::list<std::pair<size_t, ValueType> > table[TableSize];
public:
void add(const IHashable& key, const ValueType& val)
{
size_t h_key = key.getHash();
table[h_key % TableSize].push_back(std::make_pair(h_key, val));
}
ValueType& get(const IHashable& key)
{
size_t h_key = key.getHash();
std::list<std::pair<size_t, ValueType> >::iterator it;
for (it = table[h_key % TableSize].begin();
it != table[h_key % TableSize].end();
++it)
{
if (it->first == h_key)
return it->second;
}
}
};
This assumes that your hash-function always produces unique hashes for
unique IHashables, another method can be used to get the correct one,
such as storing a pointer copy of the IHashable (to prevent slicing).
--
Erik Wikstr?m