使用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，而節點的類型爲Object。

如何使用模板，在可列基類，使上一頁&下一個指針更改其類型的類被使用？

也許是這樣的：

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），即使你那麼，它應該可能是std::list。

Answer 3

你確定你寧願不只是使用：

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

呢？即使節點實際上是一個對象，也可以工作，因爲對象從Listable繼承。

此外，作爲傑裏提到，已經有一個內置的templated, doubly linked list這是標準模板庫的一部分。你不會需要手工編寫一個for循環或者，因爲你也可以使用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'; 
}