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基类中使用模板，使得prev和next指针可以根据使用的类更改其类型？

也许可以尝试像这样：

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++特性还比较新。因此，我不确定应该使用什么语法。

- user1054922

---

是的，我意识到这些对象一次只能属于一个列表。这是出于设计考虑。 - user1054922

知道就好，这里有一个内置的链表。 - aaronman

在C++中不需要使用typedef struct，只需使用struct即可。 - Captain Obvlious

这种方法比内置的链表更快。 - user1054922

定义列表类型的最佳方式是将其与它所持有的类型完全分离：不要创建一个“可列举”的类，通过继承将其他类转换为列表，而是创建一个具有列表特定操作（添加、删除、连接）的容器。这将减少类的复杂性并避免列表接口和包含类型之间的干扰。 - didierc

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正在管理指针，因此您需要注意三大法则。也就是说，在销毁、复制构造和赋值过程中需要考虑如何正确管理内存。

- jxh

---

我尝试了这个，但是出现了编译错误，“typename”：不是“struct”（谈论next和prev声明）。 - user1054922

@user1054922：抱歉，现在应该已经修复了。在IDEONE上运行。 - jxh

非常感谢您直接回答我的问题，而不是告诉我使用std::list等。如果可以的话，我会给您更多的积分。现在似乎我遇到了一些问题，Add/Remove成员函数不喜欢一个基本的“Listable”类作为参数，但模板语法是我的问题的关键。 - user1054922

Answer 2

你确定你真的不想使用：

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

那么使用这种方式呢？即使node实际上是一个对象，因为对象继承自Listable，所以也可以工作。

此外，正如Jerry提到的那样，C++标准模板库中已经有一个内置的带模板的双向链表。您也不需要手动编写for循环，因为您还可以使用std::foreach对其进行操作：

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

- Carl

Answer 3

你似乎把链表的概念和链表中的节点混淆了。然后你又加入了一个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.
};

注意：当然，对于真正的代码，你可能根本不想使用链表，并且即使你使用，它也应该是一个std::list。

- Jerry Coffin