Hash table and linked list implementation in C++

I'm trying to improve my understanding of inheritance and template classes in C++ so I coded a hash table (see compilable source code below).

I would be greatly appreciative of any comments on how to improve this code.

Description: The LinkedList template class inherits from the template class Stack. The Stack class contains a member variable of type LLNode which inherits from the template class Node. The HashTable class contains insert, delete and search operations. The constructor accepts a table size and two function pointers representing the hash-map and the prehash function.

```
#include
#include

template
class Node {
public:
Node(T key);
T getKey();
protected:
T key_;
};

template Node::Node(T key):key_(key)
{}

template T Node::getKey()
{
return key_;
}

template
class LLNode : public Node {
public:
LLNode(T key);
LLNode* getNext();
void setNext(LLNode* next);
protected:
LLNode* next_;

};

template LLNode::LLNode(T key):Node(key), next_(0)
{}

template LLNode* LLNode::getNext()
{
return next_;
}

template void LLNode::setNext(LLNode* next)
{
next_ = next;
}

template
class Stack {

public:
// constructor
Stack();
// destructor
virtual ~Stack();

// implements stack data structure
virtual void push(T data);
virtual void pop();

// return the number of nodes in the stack
int getSize() const;

int peek();

// wrapper functions for printing the list
void reversePrintList() const;
void printList() const;

protected:
LLNode* createNode(T insertionKey);
LLNode* head_;
int size_;

void reversePrintWorker(LLNode*) const;
void printWorker(LLNode*) const;
};

template Stack::Stack():head_(0), size_(0)
{}

template Stack::~Stack()
{
while(head_!=0)
{
pop();
}
}
template int Stack::getSize() const
{
return size_;
}

template int Stack::peek()
{
return head_->getKey();
}

template LLNode* Stack::createNode(T insertionK

Design Review

Not sure you need both Node and LLNode they seem to be the same thing.

Style Review

If a function is only one line do it in-line in the class rather than breaking it out.

Code Review

Use References

Return by reference when you can (to avoid a copy). If you don't want the user modifying it then use const reference.

Node(T key);
    // Pass key by reference. Otherwise you are copying it to the
    // parameter then you are copying it to the member.
    //
    // If you can pass by r-value reference so you can move it into
    // the objext

So I would have done:

Node(T const& key)     // Copy constructor. 
        : key_(key)        //    but only one copy
    {}
    Node(T&& key)          // Move constructor.
        : key_(std::forward(key))
    {}

When retrieving the key you return by value. This means you are going to make a copy of the key to return. I assume you don't want people modiying the key so you should return by const reference.

T getKey();

I would have done:

T const&  getKey() const { return key_;}
    ^^^^^^^^                                return const reference
                       ^^^^^                this method does not change state

RAII

When you play with pointers you need to define the ownership. If a class owns a pointer then you need to make sure that it correctly handles that pointer when being copied and assigned. To do this you need to obey the rule of three (rule of five).

Basically this means you need to define destructor/copy constructor/copy assignment operator (for rule of three) add move constructor/move assignment operator (for rule of five).

Now defining does not mean it needs to do anything you can delete it (or make it undefined) so it can not be used if that is appropriate. But you must think about it and define it.

Stack: This class owns a pointer:

LLNode* head_;

But I don't see a copy or move operators. Thus I am sure this will not work correctly (because the compiler will generate default versions).

{
    stack    x;
    x.push(5);

    stack    y(x)
}                            // Code will break here.

Top

This is usually called top()

template int Stack::peek()
{
    return head_->getKey();
}

Also it should be returning a T (the type being stored). Though you should return T by reference.

Is there really a need for this function?

template LLNode* Stack::createNode(T insertionKey)
{
    LLNode* insertionPtr = new LLNode(insertionKey);
    return insertionPtr;
}

It looks like the just a call to the constructor. Why not just call that constructor.

If you modify the constructor of LLNode to pass the next pointer then you can really simplify the push.

I would write it like this:

template void Stack::push(T const& data)
{
    head = new LLNode(data, head);
    size_++;
}
template void Stack::push(T&& data)
{
    head = new LLNode(std::forward(data), head);
    size_++;
}

Sure you need a print. But why limit it to printing to std::cout. Sure you can make that the default but you should be able to print to any stream. You can also add an output operator to allow you to use << to print the stream.

template void Stack::reversePrintWorker(LLNode* currPtr, std::ostream& stream = std::cout) const;
template void Stack::printWorker(LLNode* currPtr, std::ostream& stream = std::cout) const;

std::ostream& operator const& data) {
    str << "[";
    data.printWorker(currPtr, str);
    str << "]";
    return str;
}

Not sure why you did this:

(this->size_)--;

Just do:

--size_;

This be should returning a T.

template int LinkedList::getData(int idx) const

Hashing

Not sure I would require two functions for hashing. If its a good hash you should just be able to do the modulus of the number of slots. You should also provide a default hash function. Most people don't know how to write hash function and making them do so will cause lots of problems.

Using C function pointers for the functions is also a bit old school (and prevents optimization). Use functors (or lambdas (fancy functors)).

Always use the initializer list rather than setting the values in the body of the constructor.

StackExchange Code Review Q#113695, answer score: 4