🔒 Locked

generic linked list -template?

Started by robolee Jun 11, 2010 at 8:33 PM 4 replies 1.6k views

Original Post

Jun 11, 2010 at 8:33 PM

Hi, I've looked into templates before when I was still grasping the very basics of c++, and I thought at the time that templates were worthless and only used for data functions like sorting numbers and stuff. Basically I have a few linked lists that work fine but there's a lot of duplicate code for the linked list functions so I decided to look into generic programming and it was the only thing I found, so I thought I might as well look into it again and I thought that it might be possible to get what I want out of it.

So here's my attempt at making a template struct that is no doubt completely wrong(the format is almost identical to my other linked lists, except my other linked lists have a lot more data):
http://pastebin.com/SSGKmSWA
...

So, basically I want to know how/if I can use this template (my attempts to use it failed), or if there's some other method, just so that I don't have to write out the linked list functions for each list (particles, objects, entities, collision surfaces... it's a lot of repeat code with just changes in names). I'm okay with having to keep writing out all these list functions, but some kind of generic linked list template would be better. (For now I just put them all at the bottom of my "datastructures" header to increase the struct readability)

jflanglois

Jun 11, 2010 at 8:41 PM

The best way is to use the standard library. std::list is a doubly linked list in most implementations, as far as I know (its complexity requirement basically mandate it, if I remember correctly, but I haven't developed C++ code in a long time). The benefit of going with the stdlib is that it deals with use cases that you may not have thought about (e.g. (de)allocation), and the code is likely very well tested.

robolee

Jun 11, 2010 at 9:12 PM

I don't think you understand, I already have a linked list implementation I was just hoping for some kind of templateized version just to cut down on code repeat, though I will have a look at the code behind the std list implementation.

JonConley

Jun 11, 2010 at 9:17 PM

1.template
2.struct List{
3. struct Node{
4. T i;
5. Node *Next;
6. Node *Previous;
7. void Add();
8. void Remove(Node *n);
9. void CleanList();
10. };
11. List *FirstNode;
12. List *LastNode;
13. List *CurrentNode;
14.};

Lines 11,12 and 13 are wrong. Right now your list has 3 lists inside of it, but they should only be pointers to nodes. So it should be

Node* FirstNode;
Node* LastNode;
Node* CurrentNode;

These are pointers to the nodes at the front and end. So therefore should not be a list.

jflanglois

Jun 11, 2010 at 9:21 PM

I realized that you had your own implementation, but unless you're writing a linked list implementation for academic purposes, you should be leveraging the standard library (and some other well regarded libraries) as much as possible.

But to answer your specific question: yes, you would use templates in this case. I should warn you that the implementation for std::list in your stdlib probably won't be readable. I would look instead at the C++ standard documents to find out what the requirements for the stdlib container classes are.

Zakwayda

Jun 11, 2010 at 9:45 PM

Quote:
I was just hoping for some kind of templateized version just to cut down on code repeat

That's exactly what std::list is.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.