You don't need any dynamic allocation (beyond what's required for creating a ListNode for the SortedList). Could you explain why you think you need to do any more than that?
This is what my table's insert code looks like right now:
template <typename Key, typename Data, typename HashFunc>
void ChainedHashTable<Key, Data, HashFunc>::Insert( const HashContainer<Key, Data> &container )
{
/* ...Table resize code can go here... */
// Hash an appropriate index.
std::size_t index = Normalize( hash(container.GetKey()) );
// Insert the key and data into the hash table.
// SortedList object will deal with sorting and inserting into the chain.
m_pTable[index].Insert(container);
}
This is my list's Insert code:
template <typename T>
void SortedList<T>::Insert( const T &item )
{
// Make new node the front if it has the 'lowest' value, or list is empty
if (m_pFront == nullptr || item < m_pFront->Data())
m_pFront = new ListNode(item, m_pFront);
else
{
ListNode *pLinkingNode = m_pFront; // newNode will be pointed to by this.
// Keep iterating until we find the 'in-order' pos, until we hit the end.
while (pLinkingNode->Next() != nullptr &&
pLinkingNode->Next()->Data() < item )
{
pLinkingNode = pLinkingNode->Next();
}
// Insert the node in its appropriate position
ListNode *pNewNode = new ListNode(item, pLinkingNode->Next());
pLinkingNode->SetNext(pNewNode);
}
m_count++;
}
My list only takes one parameter, so what I feed it has to be contained in one object. ...[moment of realization]...Wait, so would something like this work:
template <typename Key, typename Data, typename HashFunc>
void ChainedHashTable<Key, Data, HashFunc>::Insert( const Key &key, const Data &data )
{
/* ...Table resize code can go here... */
// Hash an appropriate index.
std::size_t index = Normalize( hash(key) );
// Insert the key and data into the hash table.
// SortedList object will deal with sorting and inserting into the chain.
m_pTable[index].Insert(HashContainer(key, data));
}
