Templated Linked List

[Josh]

I wrote my own LinkedList class that is a lot simpler than messing around with STL iterators. It uses the Leadwerks3D Object class for the link values. I'd like to be able to create lists for entities, integers, strings, or whatever else. Does anyone know how to use templates to make this declarable like stl lists are?:

LinkedList<Entity*> list;

linkedlist.rar

[Furbolg]

Should work like this : (from MSDN, i only recommend using the MSDN http://msdn.microsoft.com/en-us/library/ffef594x%28v=vs.80%29.aspx )

// class_templates.cpp
template <class T, int i> class TempClass
{
public:
   TempClass( void );
   ~TempClass( void );
   int MemberSet( T a, int b );
private:
   T Tarray[i];
   int arraysize;
};
int main()
{
}

[Roland]

But why... can't see the genius in doing that! But its your engine, not mine

 

However, think it will be something like this...

Have not tested, just written.

 

 

 

Link.h

#pragma once
namespace Leadwerks3D
{
template<typename T>
class LinkedList;

template <typename T>
class Link
{
friend class LinkedList<T>;
T* value;
Link* prev;
Link* next;
LinkedList<T>* list;
public:
Link()
: value(nullptr),
prev(nullptr),
next(nullptr),
list(nullptr)
{}
~Link()
{
if (list->firstlink==this) list->firstlink=next;
if (list->lastlink==this) list->lastlink=prev;
if (prev) prev->next=next;
if (next) next->prev=prev;
value=nullptr;
}


Link* NextLink() const
{
return next;
}
Link* PrevLink() const
{
return prev;
}
T* GetValue() const
{
return value;
}
};
}

 

LinkedList.h

#include "Link.h"
namespace Leadwerks3D
{
template <typename>
class Link;
template <typename T>
class LinkedList
{
friend class Link<T>;

Link<T>* firstlink;
Link<T>* lastlink;
public:
LinkedList()
: firstlink(nullptr),
lastlink(nullptr)
{}
~LinkedList()
{
Link<T>* link = firstlink;
Link<T>* nextlink;
while (link!=nullptr)
{
nextlink=link->next;
link->next=nullptr;
link->prev=nullptr;
delete link;
}
}
Link<T>* GetFirstLink() const
{
return firstlink;
}
Link<T>* GetLastLink() const
{
return lastlink;
}

Link<T>* AddLast(T* o)
{
Link<T>* link = new Link<T>;
link->value = o ;
link->prev = lastlink ;
link->list = this;
if (lastlink)
{
lastlink->next=link;
}
else
{
firstlink=link;
}
lastlink = link;
return link;
}
Link<T>* AddFirst(T* o)
{
Link<T>* link = new Link<T>;
link->value= o;
link->next = firstlink;
link->list = this;
if (firstlink)
{
firstlink->prev=link;
}
else
{
lastlink=link;
}
firstlink = link;
return link;
}

static LinkedList<T>* Create()
{
return new LinkedList<T>;
}
};
}

 

Use like this

 

#include "LinkedList.h"
using namespace Leadwerks3D;

class ABC
{
};

int main(int argc, char* argv[])
{
LinkedList<ABC> list;
list.AddFirst(new ABC() );
list.AddLast(new ABC() );

return 0;
}

[smashthewindow]

I wrote my own LinkedList class that is a lot simpler than messing around with STL iterators.

Why not just use STL?

Using STL interator isn't that hard, and I find that a lot more people will be familiar with it. (Not sure about that but I'm pretty sure I would be.)

[Roland]

Using STL is quite standard and would be a positive thing. There are many advantages with STL iterators, as the ability to have several iterators operation on the same list at once, it also have a bunch of nice features that I would miss. So my recommendation is STL, but Josh has the internal overview of the code and may have some reason to use non-standard lists.

[Rick]

If this stuff is ever to be exposed to the user then I would say use iterators because the C++ programmers will be familiar with it and there are a bunch of algorithms already available to work with those containers. Why write your own?

[Furbolg]

Please dont say Performance

For Release Mode you can write this :

#define _SECURE_SCL 0

 

Which turns off checks (http://msdn.microsoft.com/en-us/library/aa985965%28v=vs.80%29.aspx) within the iterators (range, null etc.) but just do it on your own risk.

[Josh]

STL lists suck because they return iterators as objects, not pointers. With pointers, you know if a value is NULL it is no good:

 

Link* link = list.AddLast(o);
delete link;
link=NULL;

 

With STL iterators, you have no idea whether an iterator is valid or not:

std::list<Object*>::iterator it = list.begin();
list.erase(it);
//it still hangs around, can't be changed to NULL

[Furbolg]

You do it wrong.

 

With STL iterators, you have no idea whether an iterator is valid or not:

std::list<Object*>::iterator it = list.begin();
list.erase(it);
//it still hangs around, can't be changed to NULL

 

Do it like this: (MSDN: std::list.erase http://msdn.microsoft.com/en-us/library/1fef72t6%28v=vs.80%29.aspx )

std::list<Object*> list;
list.push_back(new Object());
std::list<Object*>::iterator it = list.begin();
it = list.erase(it);
if (it == list.end()) // similiar to == null
{
   std::cout << "no more entry" << std::endl;
}

 

ps. Im sorry to refer so much to the MSDN but its the best source for (v)c++ documentation.

[Roland]

Besides the to be or not to be discussion. Did my example solve your problem Josh?

[Josh]

You do it wrong.

 

 

 

Do it like this: (MSDN: std::list.erase http://msdn.microsof...6(v=vs.80).aspx )

std::list<Object*> list;
list.push_back(new Object());
std::list<Object*>::iterator it = list.begin();
it = list.erase(it);
if (it == list.end()) // similiar to == null
{
std::cout << "no more entry" << std::endl;
}

 

ps. Im sorry to refer so much to the MSDN but its the best source for (v)c++ documentation.

That's somewhat better, but I still don't like this because you always have to have the list and the iterator. Why can't the iterator just remember which list it belongs to?

 

Besides the to be or not to be discussion. Did my example solve your problem Josh?

Haven't got to try it yet, but I have the solution here so I can go back to it later.

[Furbolg]

That's somewhat better, but I still don't like this because you always have to have the list and the iterator. Why can't the iterator just remember which list it belongs to?

 

Whats the problem ? Since the iterator is created on stack, you can just create new instance when you need it.

[smashthewindow]

As long as this thing is just used internally within the engine I wouldn't mind (Do your magic Josh, you're the genius.).

But for the users I think it would be a lot better to use the STL, creating a new system would make it difficult for new users to adapt.

[Josh]

I'm not using this in the engine, at the moment. It's going in the bin of stuff I may do later, maybe as part of Codewerks.

[tjheldna]

Thanks Josh I'll give this a go. Thanks!!

[Canardia]

I think STL::list is faster than a self-made simple list with pointers. I noticed that when I made one in Fortran, but I haven't speed tested yet how much speed difference there is in C++.

[smashthewindow]

I think STL::list is faster than a self-made simple list with pointers. I noticed that when I made one in Fortran, but I haven't speed tested yet how much speed difference there is in C++.

 

There's been a speed test between STL classes and Doom 3's implementation of the respective classes, STL's classes showed significantly faster speed.

 

I would suggest to use STL for primitive containers such as lists or vectors, which are probably the fastest implementation out there.