C++ Связанный список, используя шаблоны

Question

У меня есть следующий класс:

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

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

и я наследовать от него так:

typedef struct Object : Listable 
{ 
} Object; 

Проблема заключается в том, когда я делаю что-то вроде этого:

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

Я получаю сообщение об ошибке с 'node = node-> next', поскольку node-> next имеет тип Listable, а node - типа Object.

Как использовать шаблоны в базовом классе Listable, чтобы превью & Следующие указатели меняют свой тип на используемый класс?

Может быть что-то вроде:

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; 

и я наследовать от него так:

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

У меня есть более 10 лет C, но я довольно новыми для C++ функций, таких как шаблоны. Поэтому я не уверен, какой синтаксис я должен использовать.

Answer 1

Сам шаблон синтаксис довольно прямо вперед:

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

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

Так что, когда он получает в наследство от Object так:

struct Object : Listable<Object> 
{ 
}; 

Object получит next и prev указатели.

С Listable управляющие указатели, вам необходимо обратить внимание на Rule of Three. То есть вы должны думать о том, что нужно делать во время уничтожения, создания копии и назначения, чтобы память управлялась должным образом.

Answer 2

Вы, кажется, сближаете понятие связанного списка с именем узла в связанного списка. Затем вы добавляете Object, который (предположительно) является одним из этих запутанных узлов/связанных вещей списка. По крайней мере, для меня это звучит довольно запутанно и запутанно.

Я бы предпочел, чтобы увидеть что-то вроде:

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

Предупреждение: конечно, для реального кода, 1), вероятно, не хотите использовать связанный список на всех, и 2), даже если вы do, вероятно, это должно быть std::list.

Answer 3

Вы уверены, что вы предпочли бы просто не использовать:

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

вместо этого? Это будет работать, даже если узел фактически является объектом, потому что Object наследует от Listable.

Кроме того, как отмечает Джерри, уже есть встроенный templated, doubly linked list, который является частью стандартной библиотеки шаблонов C++.Вам не нужно будет вручную написать цикл либо, потому что вы можете также использовать std::foreachto 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'; 
}