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
– user1054922, Commented Aug 6, 2013 at 1:47
No need to use typedef struct in C++. struct alone is sufficient. — Captain Obvlious
– Captain Obvlious, Commented Aug 6, 2013 at 1: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
– didierc, Commented Aug 6, 2013 at 2:05

Community · Accepted Answer · 2017-05-23 12:14:06Z

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, 2017 at 12:14

CommunityBot

11 silver badge

answered Aug 6, 2013 at 1:54

jxh

70.8k8 gold badges116 silver badges203 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user1054922 Over a year ago

I try this, but get a compile error, 'typename' : is not a 'struct' (talking about the next and prev declarations)

jxh Over a year ago

@user1054922: Sorry, should be fixed now. Works on IDEONE.

user1054922 Over a year ago

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.

Carl · Accepted Answer · 2013-08-06 02:42:33Z

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';
}

Jerry Coffin · Accepted Answer · 2013-08-06 02:25:53Z

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.

Collectives™ on Stack Overflow

C++ Linked List using Templates

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related