Jump to content
  • Advertisement
Sign in to follow this  
webwraith

linked lists and templates, Oh My!!

This topic is 4346 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'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);}
        void add_this(list_node<t>* _prev,list_node<t>* _next){if(prev!=_prev)prev=_prev;if(next!=_next)next=_next;prev->next=this;next->prev=this;}
        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 this post


Link to post
Share on other sites
Advertisement
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.

Whitespace is your friend.

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

CM

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by webwraith
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

As predicted, your foolish naming convention has caused confusion.

CM

Share this post


Link to post
Share on other sites
The answer to your question:
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.

Problems with your code that haven't already been mentioned:
-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 this post


Link to post
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;
#endif

int 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

// declare
template< typename T_ > void foo(const T_ &bar);

/* ... */

// define
template< 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 this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!