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.

Answer 1

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.

Answer 2

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