• Advertisement
Sign in to follow this  

Attempt at Linked List Template Class

This topic is 3402 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I just coded out a linked list template class, its my first attempt at template coding. It compiles fine; however, I get these 3 linker errors:
error LNK2019: unresolved external symbol "public: __thiscall LinkedList<int,0>::~LinkedList<int,0>(void)" (??1?$LinkedList@H$0A@@@QAE@XZ) referenced in function _main	main.obj
error LNK2019: unresolved external symbol "public: int & __thiscall ListIterator<int,0>::operator()(void)" (??R?$ListIterator@H$0A@@@QAEAAHXZ) referenced in function _main	main.obj
error LNK2019: unresolved external symbol "public: class ListIterator<int,0> & __thiscall LinkedList<int,0>::insertAfter(class ListIterator<int,0>,int const &)" (?insertAfter@?$LinkedList@H$0A@@@QAEAAV?$ListIterator@H$0A@@@V2@ABH@Z) referenced in function _main	main.obj

Here is the code:
//main.cpp
#include "LinkedList.h"

int main()
{
    LinkedList<int, 0> list;
    ListIterator<int, 0> listBegin = list.begin();

    list.insertAfter(listBegin, 10);
    listBegin() = 5;
    return 0;
}

//LinkedList.h
#include "ListIterator.h"
#include "ListNode.h"

#ifndef __LINKED_LIST__
#define __LINKED_LIST__

template<class tDataType, tDataType tZeroVal>
class LinkedList
{
public:
    LinkedList() : m_head(0), m_tail(0), m_iNodes(0)
    { }
    LinkedList(const LinkedList<tDataType, tZeroVal> &ll) : m_head(ll.m_head), m_tail(ll.m_tail), m_iNodes(ll.m_iNodes)
    { }
    ~LinkedList();

    ListIterator<tDataType, tZeroVal>   begin() { return ListIterator<tDataType, tZeroVal>(m_head); }
    ListIterator<tDataType, tZeroVal>   end() { return ListIterator<tDataType, tZeroVal>(m_tail); }

    ListIterator<tDataType, tZeroVal>&  insertBefore(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data);
    ListIterator<tDataType, tZeroVal>&  insertAfter(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data);
    void                                remove(ListIterator<tDataType, tZeroVal> p_iter);

protected:
    ListNode<tDataType, tZeroVal>*   m_head;
    ListNode<tDataType, tZeroVal>*   m_tail;
    int         m_iNodes;
};

#endif

//LinkedList.cpp
#include "LinkedList.h"

template<class tDataType, tDataType tZeroVal>
LinkedList<tDataType, tZeroVal>::~LinkedList()
{
    if(m_head != 0)
    {
        ListNode* pPrev = m_head;
        ListNode* pNext;

        while(pPrev != 0)
        {
            pNext = pNext->m_next;
            delete pPrev;
            pPrev = pNext;
        }
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>& LinkedList<tDataType, tZeroVal>::insertBefore(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data)
{
    if(m_iNodes != 0)
    {
        if(&p_iter == m_head || !(&p_iter))
        {
            m_head->prev = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
            m_iNodes++;
            return ListIterator<tDataType, tZeroVal>(m_head->m_prev);
        }
        else
        {
            (&(p_iter - 1)).next = new ListNode<tDataType, tZeroVal>(data, &p_iter, &(p_iter - 1));
            (&p_iter).prev = (&(p_iter - 1)).next;
            return ListIterator<tDataType, tZeroVal>((&p_iter).prev);
        }
    }
    else
    {
         m_tail = m_head = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
         m_iNodes = 1;
         return ListIterator<tDataType, tZeroVal>(m_head);
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&  LinkedList<tDataType, tZeroVal>::insertAfter(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data)
{
    if(m_iNodes != 0)
    {
        if(&p_iter == m_tail || !(&p_iter))
        {
            m_tail->next = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
            m_iNodes++;
            return ListIterator<tDataType, tZeroVal>(m_tail->next);
        }
        else
        {
            (&(p_iter - 1)).next = new ListNode<tDataType, tZeroVal>(data, &p_iter, &(p_iter - 1));
            (&p_iter).prev = (&(p_iter - 1)).next;
            return ListIterator<tDataType, tZeroVal>((&p_iter).prev);
        }
    }
    else
    {
         m_tail = m_head = new ListNode<tDataType, tZeroVal>(data, &p_iter, 0);
         m_iNodes = 1;
         return ListIterator<tDataType, tZeroVal>(m_head);
    }
}

template<class tDataType, tDataType tZeroVal>
void LinkedList<tDataType, tZeroVal>::remove(ListIterator<tDataType, tZeroVal> p_iter)
{
    if(m_iNodes != 0)
    {
        if(m_iNodes == 1)
        {
            delete m_head;
            m_tail = m_head = 0;
            m_iNodes = 0;
        }
        else
        {
            if(p_iter == m_head)
            {
                ListNode<tDataType, tZeroVal>* pTemp = m_head->m_next;
                delete m_head;
                m_head = pTemp;
                m_head->m_prev = 0;
                m_iNodes--;
            }
            else if(p_iter == m_tail)
            {
                ListNode<tDataType, tZeroVal>* pTemp = m_tail->m_prev;
                delete m_tail;
                m_tail = pTemp;
                m_tail->m_next = 0;
                m_iNodes--;
            }
            else
            {
                ListNode<tDataType, tZeroVal>* prev = (&p_iter)->m_prev;
                ListNode<tDataType, tZeroVal>* next = (&p_iter)->m_next;
                delete (&p_iter);
                prev->m_next = next;
                next->m_prev = prev;
                m_iNodes--;
            }
        }
    }
}

//ListNode.h
#ifndef __LIST_NODE__
#define __LIST_NODE__

template<class tDataType, tDataType tZeroVal>
class ListNode
{
public:
    ListNode() : m_data(tZeroVal), m_next(0), m_prev(0)
    { }
    ListNode(const ListNode<tDataType, tZeroVal> &ln) : m_data(ln.m_data), m_next(ln.m_next), m_prev(ln.m_prev)
    { }
    ListNode(tDataType& p_data) : m_data(p_data), m_next(0), m_prev(0)
    { }
    ListNode(ListNode<tDataType, tZeroVal>* p_prev, ListNode<tDataType, tZeroVal>* p_next) : m_data(tZeroVal), m_next(p_next), m_prev(p_prev)
    { }
    ListNode(tDataType& p_data, ListNode<tDataType, tZeroVal>* p_next, ListNode<tDataType, tZeroVal>* p_prev) : m_data(p_data), m_next(p_next), m_prev(p_prev)
    { }

    tDataType    m_data;
    ListNode*    m_next;
    ListNode*    m_prev;
};

#endif

//ListIterator.h
#include "ListNode.h"

#ifndef __LIST_ITERATOR__
#define __LIST_ITERATOR__

template<class tDataType, tDataType tZeroVal>
class ListIterator
{
public:
    ListIterator() : m_node(0)
    { }
    ListIterator(const ListIterator<tDataType, tZeroVal>& iter) : m_node(iter.m_node)
    { }
    ListIterator(ListNode<tDataType, tZeroVal>* p_node) : m_node(p_node)
    { }

    ListNode<tDataType, tZeroVal>*        operator&() { return m_node; }
    ListIterator<tDataType, tZeroVal>&    operator++();
    ListIterator<tDataType, tZeroVal>&    operator++(int dummy);
    ListIterator<tDataType, tZeroVal>&    operator--();
    ListIterator<tDataType, tZeroVal>&    operator--(int dummy);
    ListIterator<tDataType, tZeroVal>&    operator+(int p_amount);
    ListIterator<tDataType, tZeroVal>&    operator-(int p_amount);
    tDataType&                           operator[](int p_amount);
    tDataType&                           operator()();
private:
    ListNode<tDataType, tZeroVal>*   m_node;
};

#endif

//ListIterator.cpp
#include "ListIterator.h"

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator++()
{
    if(m_node != 0 && m_node->m_next != 0)
    {
        m_node = m_node->m_next;
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator++(int dummy)
{
    if(m_node != 0 && m_node->m_next != 0)
    {
        ListNode* temp = m_node;
        m_node = m_node->m_next;
        return ListIterator<tDataType, tZeroVal>(temp);
    }
    else
    {
        return *this;
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator--()
{
    if(m_node != 0 && m_node->m_prev != 0)
    {
        m_node = m_node->m_prev;
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator--(int dummy)
{
    if(m_node != 0 && m_node->m_prev != 0)
    {
        ListNode* temp = m_node;
        m_node = m_node->m_prev;
        return ListIterator<tDataType, tZeroVal>(temp);
    }
    else
    {
        return *this;
    }
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator+(int p_amount)
{
    if(m_node != 0 && m_node->m_next != 0)
    {
        ListNode*   newNode = m_node;

        for(int i = 0; (i < p_amount) && (newNode->next != 0); i++)
            newNode = newNode->m_next;
        return ListIterator<tDataType, tZeroVal>(newNode);
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
ListIterator<tDataType, tZeroVal>&    ListIterator<tDataType, tZeroVal>::operator-(int p_amount)
{
    if(m_node != 0 && m_node->m_prev != 0)
    {
        ListNode*   newNode = m_node;

        for(int i = 0; (i < p_amount) && (newNode->prev != 0); i++)
            newNode = newNode->m_prev;
        return ListIterator<tDataType, tZeroVal>(newNode);
    }
    return *this;
}

template<class tDataType, tDataType tZeroVal>
tDataType&       ListIterator<tDataType, tZeroVal>::operator[](int p_amount)
{
    if(m_node != 0)
    {
        ListNode*   newNode = m_node;

        for(int i = 0; (i < p_amount) && (newNode->next != 0); i++)
            newNode = newNode->m_next;
        return newNode->m_data;
    }
    return tZeroVal;
}

template<class tDataType, tDataType tZeroVal>
tDataType&       ListIterator<tDataType, tZeroVal>::operator()()
{
    if(m_node != 0)
    {
        return m_node->m_data; 
    }
    return tZeroVal;
}

Any tips will be appreciated as well. Thanks, Mikfig

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by mikfig
Why is that?


Templates by themselves aren't really anything. Only when you try to instantiate a templated class/function does code get generated for the specific type you are trying to instantiate it with. As such, the compiler must have full access to all the template code from the compilation unit it is being instantiated in. If you could split template declarations and definitions, the compiler would have no idea what to do when it came across an instantiation. It would have the relevant class/function header, but no idea what code it actually needed to generate, hence the linker errors.

More additional reading.

Share this post


Link to post
Share on other sites
Quote:
Original post by mikfig
Why is that?
Because it can't compile that code until it knows what types to compile it for, and the other cpp files cant see inside this cpp file, they can only see what is in the headers.

Your ListIterator operator & is pure evil...
If you ever use a ListIterator in a std::map say, you'll horribly shoot yourself in the foot. It will not do what you want at all. Changing the meaning of operator & is really only for making something like smart pointers, and even then they basically still return the address of something within them, never the value of a pointer from within them. When you find yourself writing bizarre things like "!(&p_iter)", you need to know that something is seriously wrong! The address of anything should never be zero.
I believe you should be using operator * for your iterator class not operator & or ().

Also, your ListIterator operator +, -, and [] are an abomination...
If you ever use those +, - and [] operators then you'll throw performance out the window. If you ever need such operations on a list, chances are you're using the wrong type of container.

Several of your functions including operator () wont compile, because you've got them returning a reference to tZeroVal. You can't return a reference to the value 0, for example. You could declare a static variable in each function that is initialised to 0, and return that. It should probably be asserting or throwing exceptions instead though.

What's up with all those destructors, you seem to have the parameters in random order. Some of them have next before prev, some of them have it after etc. Who are you trying to confuse?
You should be able to cut down the number of constructors a bit anyway. You didn't need to implement the copy-constructor for either of those classes as the automatically generated one would do the same thing. By writing it yourself you only add more code which brings with it the possibility of more bugs, either now or in future as more members are added.

Share this post


Link to post
Share on other sites
Lol, i think i just got chewed out. I know that lists aren't supposed to have random access, but I just wanted to do it for kicks :D. However, I did take all of your other suggestions except for the one to not overload the () operator. I don't see why it doesn't make sense to overload this operator.

New Code:

//main.cpp
#include "LinkedList.h"
#include <iostream>

int main()
{
LinkedList<int, 0> list;
list.insertAfter(list.begin(), 10);
list.begin() = 5;
list.insertAfter(list.begin(), 100);
list.insertAfter(list.begin() + 1, 1000);
list.insertAfter(list.begin() + 2, 1000) = 50;
ListIterator<int, 0> iter = list.begin();
iter[1] = 30;

for(ListIterator<int, 0> i = list.begin(); i != (list.end() + 1); i++)
{
std::cout << i() << std::endl;
}
std::cout << "Press ENTER to exit." << std::endl;
getchar();
return 0;
}




//LinkedList.h
#include "ListIterator.h"
#include "ListNode.h"

#ifndef __LINKED_LIST__
#define __LINKED_LIST__

template<class tDataType, tDataType tZeroVal>
class LinkedList
{
public:
LinkedList() : m_head(0), m_tail(0), m_iNodes(0)
{ }
~LinkedList()
{
if(m_head != 0)
{
ListNode<tDataType, tZeroVal>* pPrev = m_head;
ListNode<tDataType, tZeroVal>* pNext;

while(pPrev != 0)
{
pNext = pPrev->m_next;
delete pPrev;
pPrev = pNext;
}
}
}

ListIterator<tDataType, tZeroVal> begin() { return ListIterator<tDataType, tZeroVal>(m_head); }
ListIterator<tDataType, tZeroVal> end() { return ListIterator<tDataType, tZeroVal>(m_tail); }

ListIterator<tDataType, tZeroVal>& insertBefore(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data)
{
if(m_iNodes != 0)
{
if(*p_iter == m_head || !(*p_iter))
{
m_head->m_prev = new ListNode<tDataType, tZeroVal>(data, m_head, 0);
m_head = m_head->m_prev;
m_iNodes++;
return ListIterator<tDataType, tZeroVal>(m_head);
}
else
{
(*(p_iter - 1)).next = new ListNode<tDataType, tZeroVal>(data, *p_iter, *(p_iter - 1));
(*p_iter).prev = (*(p_iter - 1)).next;
return ListIterator<tDataType, tZeroVal>((*p_iter).prev);
}
}
else
{
m_tail = m_head = new ListNode<tDataType, tZeroVal>(data, *p_iter, 0);
m_iNodes = 1;
return ListIterator<tDataType, tZeroVal>(m_head);
}
}

ListIterator<tDataType, tZeroVal>& insertAfter(ListIterator<tDataType, tZeroVal> p_iter, const tDataType& data)
{
if(m_iNodes != 0)
{
if(*p_iter == m_tail || !(*p_iter))
{
m_tail->m_next = new ListNode<tDataType, tZeroVal>(data, 0, m_tail);
m_tail = m_tail->m_next;
m_iNodes++;
return ListIterator<tDataType, tZeroVal>(m_tail);
}
else
{
(*p_iter)->m_next = new ListNode<tDataType, tZeroVal>(data, *p_iter, *(p_iter - 1));
(*(p_iter + 1))->m_prev = (*p_iter)->m_next;
return ListIterator<tDataType, tZeroVal>((*p_iter)->m_next);
}
}
else
{
m_tail = m_head = new ListNode<tDataType, tZeroVal>(data, 0, 0);
m_iNodes = 1;
return ListIterator<tDataType, tZeroVal>(m_head);
}
}

void remove(ListIterator<tDataType, tZeroVal> p_iter)
{
if(m_iNodes != 0)
{
if(m_iNodes == 1)
{
delete m_head;
m_tail = m_head = 0;
m_iNodes = 0;
}
else
{
if(p_iter == m_head)
{
ListNode<tDataType, tZeroVal>* pTemp = m_head->m_next;
delete m_head;
m_head = pTemp;
m_head->m_prev = 0;
m_iNodes--;
}
else if(p_iter == m_tail)
{
ListNode<tDataType, tZeroVal>* pTemp = m_tail->m_prev;
delete m_tail;
m_tail = pTemp;
m_tail->m_next = 0;
m_iNodes--;
}
else
{
ListNode<tDataType, tZeroVal>* prev = (*p_iter)->m_prev;
ListNode<tDataType, tZeroVal>* next = (*p_iter)->m_next;
delete (*p_iter);
prev->m_next = next;
next->m_prev = prev;
m_iNodes--;
}
}
}
}

protected:
ListNode<tDataType, tZeroVal>* m_head;
ListNode<tDataType, tZeroVal>* m_tail;
int m_iNodes;
};

#endif




//ListIterator.h
#include "ListNode.h"

#ifndef __LIST_ITERATOR__
#define __LIST_ITERATOR__

template<class tDataType, tDataType tZeroVal>
class ListIterator
{
public:
ListIterator() : m_node(0)
{ }
ListIterator(ListNode<tDataType, tZeroVal>* p_node) : m_node(p_node)
{ }

ListNode<tDataType, tZeroVal>* operator*() { return m_node; }

ListIterator<tDataType, tZeroVal>& operator++()
{
if(m_node != 0 && m_node->m_next != 0)
{
m_node = m_node->m_next;
}
return *this;
}

ListIterator<tDataType, tZeroVal>& operator++(int dummy)
{
if(m_node != 0)
{
ListNode<tDataType, tZeroVal>* temp = m_node;
m_node = m_node->m_next;
return ListIterator<tDataType, tZeroVal>(temp);
}
else
{
return *this;
}
}

ListIterator<tDataType, tZeroVal>& operator--()
{
if(m_node != 0 && m_node->m_prev != 0)
{
m_node = m_node->m_prev;
}
return *this;
}

ListIterator<tDataType, tZeroVal>& operator--(int dummy)
{
if(m_node != 0 && m_node->m_prev != 0)
{
ListNode<tDataType, tZeroVal>* temp = m_node;
m_node = m_node->m_prev;
return ListIterator<tDataType, tZeroVal>(temp);
}
else
{
return *this;
}
}

ListIterator<tDataType, tZeroVal>& operator+(int p_amount)
{
if(m_node != 0)
{
ListNode<tDataType, tZeroVal>* newNode = m_node;

for(int i = 0; i < p_amount; i++)
{
newNode = newNode->m_next;
if(!newNode)
break;
}
return ListIterator<tDataType, tZeroVal>(newNode);
}
return *this;
}

ListIterator<tDataType, tZeroVal>& operator-(int p_amount)
{
if(m_node != 0 && m_node->m_prev != 0)
{
ListNode<tDataType, tZeroVal>* newNode = m_node;

for(int i = 0; (i < p_amount) && (newNode->m_prev != 0); i++)
{
newNode = newNode->m_prev;
if(!newNode)
break;
}
return ListIterator<tDataType, tZeroVal>(newNode);
}
return *this;
}

tDataType& operator[](int p_amount)
{
if(m_node != 0)
{
if(p_amount == 0)
return m_node->m_data;
ListNode<tDataType, tZeroVal>* newNode = m_node;

for(int i = 0; (i < p_amount) && (newNode->m_next != 0); i++)
newNode = newNode->m_next;
return newNode->m_data;
}
static tDataType zero = tZeroVal;
return zero;
}

tDataType& operator()()
{
if(m_node != 0)
return m_node->m_data;
static tDataType zero = tZeroVal;
return zero;
}

void operator=(const tDataType& d)
{
if(m_node != 0)
m_node->m_data = d;
}

bool operator==(ListIterator<tDataType, tZeroVal> iter)
{
if(*iter == m_node)
return true;
else
return false;
}

bool operator!=(ListIterator<tDataType, tZeroVal> iter)
{
if(*iter == m_node)
return false;
else
return true;
}
private:
ListNode<tDataType, tZeroVal>* m_node;
};

#endif




//ListNode.h
#ifndef __LIST_NODE__
#define __LIST_NODE__

template<class tDataType, tDataType tZeroVal>
class ListNode
{
public:
ListNode() : m_data(tZeroVal), m_next(0), m_prev(0)
{ }
ListNode(const ListNode<tDataType, tZeroVal> &ln) : m_data(ln.m_data), m_next(ln.m_next), m_prev(ln.m_prev)
{ }
ListNode(const tDataType& p_data) : m_data(p_data), m_next(0), m_prev(0)
{ }
ListNode(ListNode<tDataType, tZeroVal>* p_prev, ListNode<tDataType, tZeroVal>* p_next) : m_data(tZeroVal), m_next(p_next), m_prev(p_prev)
{ }
ListNode(const tDataType& p_data, ListNode<tDataType, tZeroVal>* p_next, ListNode<tDataType, tZeroVal>* p_prev) : m_data(p_data), m_next(p_next), m_prev(p_prev)
{ }

tDataType m_data;
ListNode* m_next;
ListNode* m_prev;
};

#endif



Thanks,
Mikfig

P.S. Will compilers ever support defining functions in a template class outside of the class' declaration? As in, not having to define the functions inline. I thought that that was in the C++ Standard.

Share this post


Link to post
Share on other sites
Just to be sure that you're aware...

The STL has a very nice templated list class already.

Share this post


Link to post
Share on other sites
Well of course :D. Just doing it for experience rather than for actual use.

Thanks for the heads up though,
I still have to read an intro STL book when I get a chance

Share this post


Link to post
Share on other sites
Quote:
Original post by mikfig
. However, I did take all of your other suggestions except for the one to not overload the () operator. I don't see why it doesn't make sense to overload this operator.
One good reason is that iterators are meant to act like pointers, if you change the meaning of the operators for an iterator then it becomes difficult to write code that works on both your iterators and raw pointers. With the existing STL (SC++L) iterators one can write generic template functions that will operate using either iterators or pointers; this is deliberate. In the abstract sense pointers are themselves just a type of iterator, but one that's built into the core of the language hence we model other iterators on pointers.

Quote:
P.S. Will compilers ever support defining functions in a template class outside of the class' declaration? As in, not having to define the functions inline. I thought that that was in the C++ Standard.
Maybe, maybe not, it's quite a difficult thing to achieve as it happens. The standard does support it but most compilers dont: linky.

The function definitions don't have to be literally inlined though, they must merely exist within the same translation unit. You could place the definitions below the class declaration if you'd rather, or even have them in a separate file and #include that below the class.

When you write template code it is really meta-coding, as such templates are really a language in their own right, almost, separate from normal C++ code; in fact templates are even Turing-complete. So I find it does help to think of them as being separate entities within a program; they actually are programs which execute at compile-time in order to generate programs that operate at run-time.

[Edited by - dmatter on December 26, 2008 7:38:54 PM]

Share this post


Link to post
Share on other sites
You've made some improvements, but there are some more oddities showing up too.
You haven't taken any of the advice about your ListNode constructors.

operator * would normally return a reference, and you would normally overload the -> operator as well:

ListNode<tDataType, tZeroVal>& operator*() { return *m_node; }
ListNode<tDataType, tZeroVal>* operator->() { return m_node; }

This makes the syntax (*myIter).m_data or myIter->m_data, rather than (**myIter).m_data or (*myIter)->m_data
You'd then have to fix your iterator comparison operators too.

If you're going to keep your operator [] then you should really make a const version too.

Your operator + and - return a reference to a temporary. You can't do that. They must return by value, and you just have to trust the compiler to make it as fast as it can.

When you overload + and - operators, it's nicer to use the two-parameter friend or static version. That way you can define an operator that allows you to go "int + iterator" as well as "iterator + int".
Unfortunately it isn't easy to subtract iterators to get back the distance between them (though it's entirely doable, if you're up to the challenge).

There is a lot of code that could be shortened as well. One particularly good example of this would be your remove function. To get you started there: Does m_iNodes--; really need to appear in 3 places?

There's tons more useful stuff that could be added: rbegin and rend, and the const versions as well. Operator <, <=, >, >= etc for if you ever want to use a list as a key in a map for exmaple. (I really have needed to do that before!)
I could go on, but I'm already trying to pass on too much to you at once, and I just don't have the time anyway. As you say, you really need to get a book on the SC++L, and you'll arguably also learn much from reading your standard library source code.
Best of luck with your journey into the world of C++ templates.

It is through reinventing the wheel that one comes to appreciate the conclusion that round wheels really are best. Today you've discovered that the triangle and square are inferrior to the pentagon. Tomorrow, you'll discover that the pentagon is inferrior to the hexagon.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement