Yet another template class question (corrected)

[Anonymous]

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
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:
class myHashKey
{
virtual bool operator==(cons t myHashKey& key) const = 0 ;
virtual size_t Size() const = 0 ;
};
class IHashable
{
virtual const myHashKey* GetKey() const = 0 ;
virtual bool IsKeyEqual(cons t myHashKey* key) const = 0;
virtual size_t KeySize() const = 0 ;
};

With this new policy, I want to be able to simplify my HashTable class to:
template <class InnerType>
class myHash
{
//Ho do I reference KeyType and KeyToSizeT now ?
// Impl here
};

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

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_ke y, val));
}

ValueType& get(const IHashable& key)
{
size_t h_key = key.getHash();
std::list<std:: pair<size_t, ValueType::iter ator 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