C++ Linked List using Templates

Question

I have the following class:

typedef struct Listable
{
    struct Listable *next;
    struct Listable *prev;

    // Lots of other class members not pertaining to the question excluded here
} Listable;

and I inherit from it like so:

typedef struct Object : Listable
{
} Object;

Problem is, when I do something like this:

Object *node;
for (node = objectHead; node; node = node->next);

I get an error with 'node = node->next', since node->next is of type Listable, while node is of type Object.

How can I use templates in the Listable base class to make the prev & next pointers change their type to the class being used?

Perhaps something like:

typedef struct Listable<T>
{
    struct Listable<T> *next;
    struct Listable<T> *prev;

    // Lots of other class members not pertaining to the question excluded here
} Listable;

and I inherit from it like so:

typedef struct Object : Listable<Object>
{
} Object;

I have over 10 years of C, but am fairly new to C++ features like templates. So I'm not sure what syntax I should be using.

Yes, I realize that these objects can only belong to one list at a time. This is by design. — user1054922, Aug 06 '13 at 01:47
No need to use `typedef struct` in C++. `struct` alone is sufficient. — Captain Obvlious, Aug 06 '13 at 01:52
The best way to define your list type is to separate it completely from the type it must hold: don't make a "listable" class which turn other classes into lists through inheritance, but make a container with list specific operations (add, remove, catenate). This will reduce your class complexity and avoid interferences between the list interface and the contained type. — didierc, Aug 06 '13 at 02:05
Besides, if you need to implement lists of lists (...), you will have to specialize your code. — didierc, Aug 06 '13 at 02:06
Good advice, although in this particular situation here I need to eliminate the overhead of having a container. By using the inheritance method, it restricts functionality, but offers speed. — user1054922, Aug 06 '13 at 02:07

score 3 · Accepted Answer · edited May 23 '17 at 12:14

3

The template syntax itself is fairly straight forward:

template <typename T>
struct Listable
{
    T *next;
    T *prev;

    // Lots of other class members not pertaining to the question excluded here
};

So, when it gets inherited by Object like this:

struct Object : Listable<Object>
{
};

Object will get the next and prev pointers.

Since Listable is managing pointers, you will need to pay attention to the Rule of Three. That is, you have to think about what needs to be done during destruction, copy construction, and assignment so that memory is managed properly.

edited May 23 '17 at 12:14

Community

1
1

answered Aug 06 '13 at 01:54

jxh

69,070
8
110
193

I try this, but get a compile error, 'typename' : is not a 'struct' (talking about the next and prev declarations) – user1054922 Aug 06 '13 at 12:14
1

@user1054922: Sorry, should be fixed now. [Works on IDEONE](http://ideone.com/0FPwMZ). – jxh Aug 06 '13 at 12:18
A big THANK YOU for directly answering my problem without telling me to use std::list, etc. I would give you more points if I could. Seems I'm having some issues now with the Add/Remove member functions not liking a base 'Listable' class as parameter, but the template syntax was the crux of my issue. – user1054922 Aug 06 '13 at 13:03

Carl · Answer 2 · 2013-08-06T02:42:33.023

Are you sure you would rather not just use:

Listable *node;
for (node = objectHead; node; node = node->next);

instead? That would work even if node is actually an Object, because Object inherits from Listable.

Also, as Jerry mentions, there already is a built-in templated, doubly linked list that is part of the C++ Standard Template Library. You would not need to manually write a for loop either, because you could also use std::foreach to operate on it:

#include <list>
#include <algorithm>
#include <iostream>

struct Sum {
    Sum() { sum = 0; }
    void operator()(int n) { sum += n; }

    int sum;
};

int main()
{
    std::list<int> nums{3, 4, 2, 9, 15, 267};

    Sum s = std::for_each(nums.begin(), nums.end(), Sum());

    std::cout << "sum: " << s.sum << '\n';
    std::cout << "elements:  ";

    //Or, you could use iterate over each node in the list like this
    for (auto n : nums) {
        std::cout << n << " ";
    }
    std::cout << '\n';
}

score 0 · Answer 3 · answered Aug 06 '13 at 02:25

You seem to be conflating the notion of of a linked list with that of a node in the linked list. Then you're adding in an Object that (supposedly) is one of these confused node/linked list things. At least to me, this sounds quite confused and confusing.

I'd prefer to see something like:

template <class T>
class linked_list { 
    class node {
        T data;
        node *next;
    public:
        node(T data, node *next = NULL) : data(data), next(next) {}    
    };

    node *head;
public:
    void push_back(T const &item);
    void push_font(T const &item);
    // etc.
};

Caveat: of course, for real code you 1) probably don't want to use a linked list at all, and 2) even if you do, it should probably be a std::list.

C++ Linked List using Templates

3 Answers3