# linked lists and templates, Oh My!!

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

## Recommended Posts

I'm having trouble getting my linked list to work. I tried making a linked list using templates to store any class or data type I needed, but the linker doesn't seem to be able to find the void std::list<t>::push_back(t* data) method, even though the compiler doesn't report any warnings this is main.cpp;
#include <iostream>
#include "mgllist.h"

int main()
{
std::list<std::Generic<int> > myList;
std::Generic<int>* alpha;
alpha->data=10;
myList.push_back(*alpha);
std::cout << "Hello world!" << std::endl;
system("pause");
return 0;
}


this is mgllist.h;
#ifndef _MGLLIST_H_
#define _MGLLIST_H_

#include <iostream>
#include <fstream>

namespace std{
template <class t>
struct list_node{
list_node(const list_node<t>* prev,const list_node<t>* next,const t& val):prev(prev),next(next),data(val){add_this(prev,next);}
list_node<t>* remove_this(){next->prev=prev;prev->next=next;return this;}

t data;
list_node<t>* next;
list_node<t>* prev;
};

template <class t>
class list{
protected:
list_node<t>* first;
list_node<t>* last;
list_node<t>* current;
public:
list():first(NULL),last(NULL),current(NULL){}
list(t value);
list(const list<t>& copy);
void push_back(t& value);
void push_front(t& value);
t pop_back();
};

template <class t>
class Generic{
public:
t data;
};
};

#endif //_MGLLIST_H_


and here is mgllist.cpp;
#include "mgllist.h"

using namespace std;

template <class t>
list<t>::list(t value)
{
list_node<t>* temp = new list_node<t>(NULL,NULL,value);
first = last = current = temp;
}

template <class t>
list<t>::list(const list<t>&copy)
{
current = copy.first;
do
{
list_node<t>* temp = new list_node<t>(current->prev,current->next,current->data);
}while(current != copy.last);
}

template <class t>
void list<t>::push_back(t& value){
list_node<t>* temp = new list_node<t>(last,NULL,value);
}

template <class t>
void list<t>::push_front(t& value){
list_node<t>* temp = new list_node<t>(NULL,first,value);
}

template <class t>
t list<t>::pop_back(){
list_node<t>* delitem=last;
t delitm_val = delitem->value;
delitem->remove_this();
delete delitem;
return delitm_val;
}


As always, I'm using the Code::Blocks IDE (nightly build, latest MinGW)

##### Share on other sites
Don't throw things into the std namespace willy nilly. Your additions are not standard, you shouldn't pretend they are.

There's already a linked list in the std namespace. Its called list. That makes your code outrageously confusing to anybody with even a passing knowledge of C++.

Why does Generic exist? It is completely pointless.

You have to include source code for templated code, it can't be compiled separately and linked in later [I think like one compiler supports that, but the major ones all refuse, on good grounds]. #include "glllist.cpp" [or whatever, I've already forgotten your file names] at the bottom of your header, and don't #include the header in the source file.

    std::Generic<int>* alpha;    alpha->data=10;

alpha doesn't point anywhere, dereferencing it is illegal.

push_front and push_back don't modify the values passed to them, so they should be passed as const references.

CM

##### Share on other sites
Don't put your own stuff into the std:: namespace.

Also, you don't need or want that Generic struct. Note that the real std::list doesn't require you to wrap things up like that, and it will work as well with ints as it does with most structs and classes (it does have to be default-constructible and so on). You know what special things they do to make that work? *Nothing at all*. :) Templates "just work" with that sort of thing.

Also, don't use 'protected' if you don't mean for your class to be derived from (and there really isn't a good reason you'd want to subclass list). Use 'private'.

Also, note that the real std::list offers a much richer interface, but a normal implementation won't involve any kind of 'current' pointer (which also wouldn't be helpful for implementing any of the functions you've shown). Iteration is handled by separate iterator objects. The standard library depends upon itself in a lot of ways, but is properly organized internally. Good examples of code design, here. (Unfortunately, most implementations are *horrible* examples of code *implementation* - at least as far as the variable names go).

But in terms of just getting it to link, RTFM and pay special attention to the exceptions noted about templates.

##### Share on other sites
Generic is simply to test that my list will hold a class without any modification.
It's just there for debug, and I'll remove it once I've got my class sorted out.

I'm not really bothered about using the name list, as only I'm going to use this, so I don't have to worry about confusing anyone.

And the ANSI standard says that Template and function code being separate is fully acceptable, so if the "major ones" all refuse to allow it, that just makes the whole lot of them non ANSI-compliant.

As for a richer interface, to be brutally honest, I don't care. The idea is, if I can't get this to work, why should I use someone else's? I don't want to do that. If I can roll my own, just enough to get the major ideas down, then I'll think about using the standard library version.

current is in there for later planned methods, btw.

##### Share on other sites
I'm totally sorry if i'm taking the wrong perspective on this but... using STL's std::list to make your own linked list is the greatest of ironies; borderline sacrilegious. If this is a learning excercise i understand. But otherwise, please, just use the std::list. Now, if you like std::list but want some extra bells and whistles, consider subclassing it.

##### Share on other sites
I'm not using the standard library list template, I'd just put my own implementation (also called list) in the std namespace. note the lack of
#include <list>
anywhere in the code

##### Share on other sites
Quote:
 Original post by webwraithI'm not using the standard library list template, I'd just put my own implementation (also called list) in the std namespace. note the lack of #include anywhere in the code

As predicted, your foolish naming convention has caused confusion.

CM

##### Share on other sites
Are you trying to get something posted on The Daily WTF?

##### Share on other sites
Your code doesn't link because the template functions are implemented in the source file, not the header file.

You can't do that unless your compiler supports the export keyword, which yours doesn't (you'd also need to use the export keyword in your code, so you still wouldn't be able to compile your code on a 100% compliant compiler).

Yes - almost all compilers are not iso/ANSI compliant on this issue.

-Your main function uses an unitialised pointer (alpha)
-Your list class leaks memory. All over the place. It allocates memory in the constructor, but it doesn't even have a destructor.
-Your push_back function will crash (next->prev = this; when next==NULL)
-Your push_back function will crash (prev->next = this; when prev==NULL)
-Your pop_back function will crash (next->prev = prev; when next==NULL)

So out of the 6 functions in your list class, 3 of them cause memory leaks and the other 3 crash.

##### Share on other sites
Quote:
 Also, note that the real std::list offers a much richer interface, but a normal implementation won't involve any kind of 'current' pointer (which also wouldn't be helpful for implementing any of the functions you've shown). Iteration is handled by separate iterator objects.

I wanted to comment that binding implementation of iteration functionality to the list itself (this is what I'd assume "current" is for) is an extremely bad idea, because then a given list can be iterated only once at a time; attempting to iterate the same list from two different locations (which is possible even in single-threaded contexts) will cause serious problems.

Quote:
 I'm not really bothered about using the name list, as only I'm going to use this, so I don't have to worry about confusing anyone.

Wrong. You've posted this code here asking for help, meaning you yourself are no longer its sole consumer. The fully-qualified name for your class (std::list) conflicts with real std::list. Your code is not standard, so it should not be in the std namespace. It doesn't matter whether or not you have some kind of stubborn, short-sighted opinion that nobody else will ever see your code (already disproven) or that since it is for your own use you can apply poor software development methodology. Adherance to such doctrine produces bad (as somebody else already mentioned, dailywtf-worthy) developers. Do you really want to do that to yourself?

All you have to do to correct the problem is use your own namespace instead of std so you are not pretending like your code is standard.

I notice, too, that your interface seems very similar to (the real) std::list. Perhaps you have placed yours into the std namespace so you can easily do benchmark tests with the same test harness? This is probably not the greatest idea (it restricts your interface, which may restrict your implementation, which may prevent you from making certain optimizations you could make to become faster than std::list in certain circumstances; for similar reasons it can also bloat your results because you may have achieved faster performance than std::list using its own interface, but in doing so have violated some performance guarantee required of std::list that you didn't know about).

However, the proper way to do that would be:
#if defined(USE_MY_LIST)#include "mylist.h"using my::list;#else#include <list>using std::list;#endifint main(void){list< int >  test;    /* use list here... */}

Quote:
 And the ANSI standard says that Template and function code being separate is fully acceptable, so if the "major ones" all refuse to allow it, that just makes the whole lot of them non ANSI-compliant.

Every compiler out there is ANSI compliant on the separation of template code declaration and definition. This refers only to the ability to do
// declaretemplate< typename T_ > void foo(const T_ &bar);/* ... */// definetemplate< typename T_ > void foo(const T_ &bar){  /* ... */}

that's all. The definition must be available in full to any translation unit that will use the template, prior to the specific use in that translation unit. It is true that pretty much every compiler out there does not support the "export" keyword, but that's because
1) it's really hard to implement
2) it doesn't actually solve the real problems
so there is precious little reason for anybody to bother supporting it.

The idiomatic solution is to include the implementation file into the header file via the preprocessor #include directive. Note that when doing this, it is usually a good idea to rename the implementation file so that it has a non-standard C++ extension (.inl or .cpp.inl are common). This is because most compilers would still attempt to compile the .cpp file if it is included in the project/makefile/whatever, which will result in all sorts of compile and/or link-time errors.

##### Share on other sites
The ENTIRE REASON namespace std exists in the first place is so that all standard library elements can be safely placed in namespace std, and be GUARANTEED not to conflict with any user developed code. It is not acceptable to use std:: for anything of your own, period - as such would violate the recommendations of the standard and, in addition to confusing readers, very likely be incompatible with valid implementations of the standard library - current or future.

Using namespace std is like using nothing but global variables, completely missing the whole point of C++.

as for the header file / code file problem. As far as I know, there is only 1 compiler that even partially supports the export keyword, because the export keyword is a mistake. Just like exception signatures, the C++ standard commitee made a mistake (well both of these mistakes). And in this area, the compiler writers simply refused to follow along. The historical C style compilation model of starting compilation of each unit with a fresh symbol table, followed by the running of a preprocessor, and then the parsing of a (now complete) source file, cannot possibly support the idea intended by the export keyword. It just isn't possible in C++ without completely changing nearly all the assumptions of compilation (and introducing enourmous new areas for bugs, unexpected results and significant required validation).

There are 3 managable ways to organize template in C++ - none of which need export:

1. Put the whole class into a single file (the header).
2. Put the class in seperate files, but use the preprocessor to merge them by #including the source file at the bottom of the header file (backwards from non-template files)
3. Put them in seperate files like normal, but #include the source file from client code.

Personally I use the .hpp extension when I use option 1 or option 2 (because to the client these are just normal C++ headers, that happen to contain templates.

I use .hxx for the source file of option 3, since even though it is a source file it must be used as a header file.

Course that's just my personal habits, you can use any extentions you like.

##### Share on other sites
I'm fairly certain that putting anything in namespace std is forbidden by the standard. Even writing "namespace std {}" is illegal. Only the standard library itself may open that namespace.

##### Share on other sites
Quote:
 Original post by DeyjaI'm fairly certain that putting anything in namespace std is forbidden by the standard. Even writing "namespace std {}" is illegal. Only the standard library itself may open that namespace.

You are allowed to provide overloads and template specializations of existing components.

##### Share on other sites
>I'm fairly certain that putting anything in namespace std is forbidden by the >standard. Even writing "namespace std {}" is illegal. Only the standard library >itself may open that namespace.

You are supposed to put the std::numeric_limits specializations into std namespace. Recommended reading: ISO IEC 14882.

##### Share on other sites
Quote:
 Original post by DeyjaI'm fairly certain that putting anything in namespace std is forbidden by the standard. Even writing "namespace std {}" is illegal. Only the standard library itself may open that namespace.

Is it wrong to forward declare std classes/functions? I think I remember doing this at one stage...

##### Share on other sites
Quote:
Original post by rip-off
Quote:
 Original post by DeyjaI'm fairly certain that putting anything in namespace std is forbidden by the standard. Even writing "namespace std {}" is illegal. Only the standard library itself may open that namespace.

Is it wrong to forward declare std classes/functions? I think I remember doing this at one stage...

I can't see any reason why you would want to.

##### Share on other sites
I admit it was dumb of me to put it in the std namespace, fair enough, I've removed it now. I also noticed the problems with the crashable functions, also modified (noticed them last night).
I've yet to impement the destructor, OK, I'll get on with that in a mo.

If there's anything I've missed, I'll edit this post later.

Also, how am I expected to learn anything more complex if I can't even make a linked list. This isn't me being ignorant, just trying to learn. Also, as said above, I'm fully aware that others will see my code now that I've put it up here. I'm not that stupid. The reason that I'm not too bothered about the name is that it will only exist as list in this prog. If I was going to use it in a proper program, I'd rename it, and probably modify it to suit the needs of said program.

Finally, what I find funny is the fact that you seem to think that linked lists are an "unsolvable problem"

(Edit: references to anonymous troll removed. -- Kylotan)

[Edited by - Kylotan on October 17, 2006 5:03:44 AM]

##### Share on other sites
What they're trying to point out is that when you come to make an "actual program" that you should use the STL list in most cases.

##### Share on other sites
Quote:
 Original post by CeoddynWhat they're trying to point out is that when you come to make an "actual program" that you should use the STL list in most cases.

True, but on the other hand, it never hurts to know how it is implemented and be able to do it yourself (in a basic sense of the implementation at least).

##### Share on other sites
Quote:
 Finally, what I find funny is the fact that you seem to think that linked lists are an "unsolvable problem"

Actually, most of us think that efficent, bug-free linked lists in C++ is not unsolvable - it's already solved by std::list

However, a linked list is an interesting learning exercise for low level C++ - so don't give up.

##### Share on other sites
Quote:
Original post by rip-off
Quote:
 Original post by DeyjaI'm fairly certain that putting anything in namespace std is forbidden by the standard. Even writing "namespace std {}" is illegal. Only the standard library itself may open that namespace.

Is it wrong to forward declare std classes/functions? I think I remember doing this at one stage...

Nope. That's why there's standard headers like <iosfwd>, which provide forward declarations for you.

See, there's no guarantee that your standard library's implementation is exactly as shown in the standard. For example, the implementation is allowed to provide additional (defaulted) template arguments.

The nasty bit is that all this standard header compilation can slow down a build. That's why every compiler vendor out there worth their salt has implemented precompiled headers, which pretty much obviate the need for the export keyword implementation in a way that actually implementing the export keyword could never do.

##### Share on other sites
@Nitage:

That comment was directed at a rather abusive AP, who's post has (thankfully) been deleted, now (thanks, Kylotan).

I have nothing against the standard library, and I know that this will probably get a few more people posting to tell me I'm wrong in doing this, but the other reason I wanted to roll my own was in an attempt to minimize the actual size of the code that would be produced. OK, OK, there's bound to be someone who's going to tell me that it doesn't matter for x number of reasons, fair enough. I'm not too bothered about all that, I'd just like to be able to make a linked list as a starting point

##### Share on other sites
writing code is never wrong ... only using the code you've written can be wrong :)

seriously, if you boil down the std vs custom argument, that is the result of the way we on gamedev feel.

Anytime you are doing something that duplicates existing functionality and you know this, and are doing it on purpose, and don't want game dev people to waste all our time posting about how you shouldn't be doing it like that .. then just add statements like "this is a learning exercise" or "I know the (whatever) already does this, but I'm trying to improve my programing skills by doing it myself - will investigate / use the (whatever) after I've finshed my learning expercise".

Sure you shouldn't have to explain this much to just ask a question, but unfortunatly internet forums have almost no context, we don't know anything about you or your situation, so without such statements people cannot properly navigate the different ways they might respond to a question. (and answer to a beginner about MMOs would be different than an answer to a Blizzard employee about the scalability of a partciluar networking system for use in an MMO).

These C++ standards purist can get kinda nazi on you ... and so can the write-everything-themselves posters who are constantly asking questions about how to do X correctly, even though X is not necessary at all (either already done or a less than ideal solution in the first place).

##### Share on other sites
@Xai: Thanks for that, will do from now on.

##### Share on other sites
Right, so lets scratch the posts so far(with the exception of a few, notably Nitage and Xai) and start again.

*************************
* THIS IS A LEARNING EXERCISE *
*************************

and for those that (probably don't) want to know, most of my stuff ends up with "mgl" on the front for "my gaming library" (not much of one, ATM)

could someone pleaser explain to me why the following will compile and link, but then give me an error message?

Be polite, as stated above: THIS IS A LEARNING EXERCISE!!

main.cpp;
#include <iostream>#include "mgllist.h"int main(){    mglList<int> mylist;    return 0;}

mglList.h;
#ifndef MGL_LIST_H_#define MGL_LIST_H_template <class T>class mglList{    protected:        /* the node structure*/        struct node{            node* prev;            node* next;            T* data;            node(node*prev,node*next,T*data):prev(prev),next(next),data(data){if(next!=NULL)next->prev=this;if(prev!=NULL)prev->next=this;}            node* remove(){next->prev=prev;prev->next=next;return this;}        };        node* first;        node* last;        unsigned int _size;    public:        enum position{MLIST_NPOS,MLIST_FIRST,MLIST_LAST};        void push_back(T* data)        {            if(size==0)            {                first=new node(NULL,NULL,data);                last=first;                size++;            }            else            {                node* temp=new node(last,NULL,data);                last->next=temp;                last=temp;                size++;            }        }        void push_front(T* data)        {            if(size==0)            {                first=new node(NULL,NULL,data);                last=first;                size++;            }            else            {                node* temp=new node(NULL,first,data);                first->prev=temp;                first=temp;                size++;            }        }        T* pop_back()        {            T* temp=last->data;            erase(0,MLIST_LAST,1);            return temp;        }        T* pop_front()        {            T* temp=first->data;            erase(0,MLIST_FIRST,1);            return temp;        }        void insert(unsigned int offset,position pos,T* data)        {            unsigned int count=0;            node* temp,*ins;//temp is used to find the right node, ins is the node to be inserted            if(pos==MLIST_FIRST)            {                temp=first;                while(count!=offset || temp!=last)                {                    temp=temp->next;                    count++;                }                ins=new node(temp,temp->next,data);            }            else if(pos==MLIST_LAST)            {                temp=last;                count=offset;                while(count!=0 || temp!=first)                {                    temp=temp->prev;                    count--;                }                ins=new node(temp,temp->next,data);            }            size++;        }        void erase(int offset,position pos,unsigned int num=0)        {            node*temp;            node*t2;// t2 is used to delete a node after moving on to the next,new_last is set before deleting the nodes            int check;            if(pos==MLIST_FIRST)            {                temp=first;                check=0;            }            else if(pos==MLIST_LAST)            {                temp=last;                check=-offset;            }            while(check!=offset)            {                temp=temp->next;                check++;            }            if(num==0)// special case, delete all nodes from offset forward            {                node*new_last;                while(temp!=last)                {                    t2=temp;                    if(temp->prev!=NULL)// if the previous node isn't NULL(ie, start of list)..                        new_last=temp->prev;// ..new_last becomes the node prior to temps starting value                    else new_last=NULL;// don't use new_last                        temp->remove();// get the node to remove itself from the list                    temp=temp->next;                    delete t2;                }                temp=last;// time to delete the last node                if(new_last!=NULL)//check to see if new_last is being used                    last=new_last;// it is, so set last to point to its new node                delete temp;// delete the previously last node            }            else// delete a range. This range may reach, or even surpass the end of the list,so we have to check for this            {                bool reach_end=false;// set to true if last is reached                unsigned int check=_size+offset+num;                (check>=_size)?reach_end=true:reach_end=false;//if check is greater or equal to size, then the user is attempting to go past the end of the list.                if(reach_end)// the num reaches the end of the list                {                    erase(offset,pos);// call this function with num=0 to delete all from this point onwards                    return;// job done                }                // job not done, so..                while(num==0)                {                    t2=temp;                    temp=temp->next;                    t2->remove();                    delete t2;                    num--;                }            }        }        unsigned int size()        {            return _size;        }        ~mglList()        {            erase(0,MLIST_FIRST);        }};#endif //MGL_LIST_H_

I would appreciate any help with this topic. as I feel that I shouldn't try to program anything more complicated until I can program a linked list.

BTW, I am aware of std::list.