CODEWITHSUNDEEP
c++templates
user1054922
user1054922

Reputation: 2165

C++ Linked List using Templates

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.

Upvotes: 3

Views: 1903

Answers (3)

jxh
jxh

Reputation: 70392

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.

Upvotes: 3

Carl
Carl

Reputation: 44448

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

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490098

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.

Upvotes: 0

Related Questions