Templates

Never really had a chance to play around with C++ Templates, since most work during my undergrad didn't require it and I had found that most companies avoided writing any templates themselves (at most only using the STL ones).

I noticed at my current job that they had implemented a few times their own LinkList classes since they are not including/using the STL. Looking over some of the implementations (some a bit more generic than others using void pointers) wanted me to try and write my own LinkList template class.

Although most would quickly deem it worthless of an attempt and clearly trivial, writing the class helped solidify a few deeper understandings for me in C++.

• The use of the keyword typename. Since C++ templates are generated at compile time, they are done in a multipass fashion. During the first pass, certain types are not yet defined however can be referenced, i.e. LinkList::Iterator. In order to tell the compiler that Iterator is a type and not a variable, the keyword typename is used.
• Proper const and reference correctness. There were some additional nuances that I was unaware of when working with const types. For instance, when returning a reference via an inspection method (const method), the return type must be const as well.
• You can actually some pretty crazy shit with templates, namely metaprogramming.
• The STL is pretty crazy and I take it for granted in most software projects I do. I was scratching my head for a bit on just how I wanted to implement my Iterator...

The STL is pretty crazy and I take it for granted in most software projects I do.

Here's my stab...

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

template
class LinkList
{
private:
    typedef T value_type;
	typedef T& reference_type;
	typedef const T & const_reference_type;
	typedef T * pointer_type;
	typedef const T * const_pointer_type;

	class Node
	{
     public:
        Node(value_type data): m_data(data), 
                               m_next(NULL), 
                               m_previous(NULL){}
        ~Node(){}
        
        void setNext(Node * next) { 
            this->m_next = next; 
        }
        Node * getNext() const { 
            return this->m_next; 
        }
        
        void setPrevious(Node * prev) { 
            this->m_previous = prev; 
        }
        Node * getPrevious() const { 
            return this->m_previous; 
        }
        
        void setData(const_reference_type data) { 
            m_data = data; 
        }
        reference_type getData() { 
            return m_data; 
        }
        
    private:
        Node * m_next;
        Node * m_previous;
        value_type m_data;
	};
    
    unsigned int m_size;
    Node * m_head;
    Node * m_tail;
	
public:
    class Iterator
    {
    public:
        Iterator & operator++() { //prefix
            this->m_current = m_current->getNext(); 
            return *this; 
        } 
        Iterator operator++(int) //postfix
        {
            Iterator result = *this;
            ++(*this);
            return result;
        }
        reference_type operator*() { 
            return m_current->getData(); 
        } 
        pointer_type operator->() const { 
            return &this->m_current->getData(); 
        }
        bool operator== (const Iterator & rhs) const { 
            return this->m_current == rhs.m_current; 
        }
        bool operator!=(const Iterator & rhs) const { 
            return !(*this == rhs); 
        }
        
    private:
        friend class LinkList;
        Iterator(Node * node) : m_current(node){}
        Node * m_current;
        
    };

    LinkList(): m_size(0), 
                   m_head(NULL), 
                   m_tail(NULL) {}
    virtual ~LinkList();
    
    void push_back(const_reference_type item);
    void push_front(const_reference_type item);
    void pop_front();
    void pop_back();
    
    Iterator begin() const { 
        return Iterator(m_head); 
    }
    Iterator end() const { 
        return Iterator(NULL); 
    }
    
    Iterator find(const_reference_type value)const;
    void clear();
    unsigned int size() const { return m_size; }
    bool empty() const { return m_size == 0; }
    
    
};

template
LinkList::~LinkList()
{
    this->clear();
}

template
void LinkList::clear()
{    
    for (unsigned int i = 0 ; i < m_size; ++i)
    {
        this->pop_back();
    }
}

template
typename LinkList::Iterator LinkList::find(const_reference_type value) const
{
    Node * curr = m_head;
    while (curr != NULL)
    {
        if (curr->getData() == value)
        {
            return Iterator(curr);
        }
        
        curr = curr->getNext();
    }
    
    return Iterator( this->end() );
}

template
void LinkList::push_back(const_reference_type item)
{
    Node * newNode = new Node(item);
    m_size+=1;
    if (this->m_head == NULL)
    {
        this->m_head = newNode;
        this->m_tail = m_head;
        return;
    }
    newNode->setPrevious(this->m_tail);
    this->m_tail->setNext( newNode );
    this->m_tail = newNode;
    return;
}

template
void LinkList::push_front(const_reference_type item)
{
    Node * newNode = new Node(item);
    m_size+=1;
    if (this->m_head == NULL)
    {
        this->m_head = newNode;
        this->m_tail = m_head;
        return;
    }
    this->m_head->setPrevious(newNode);
    newNode->setNext(this->m_head);
    this->m_head = newNode;
    return;
}

template
void LinkList::pop_back()
{
    if (this->m_tail != NULL)
    {
        m_size-=1;
        Node * popNode = this->m_tail;
        this->m_tail = popNode->getPrevious();
        delete popNode;
        if(this->m_tail == NULL)
        {
            this->m_head = NULL;
        }
    }
    
}

template
void LinkList::pop_front()
{
    if (this->m_head != NULL)
    {
        m_size-=1;
        Node * popNode = this->m_head;
        this->m_head = popNode->getNext();
        delete popNode;
        if(this->m_head == NULL)
        {
            this->m_tail = NULL;
        }
    } 
}
#endif

---