0

我已经实现了这个侵入式链表：

template <class Entry>
struct LinkedListNode {
    Entry *next;
    Entry *prev;
};

template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
class LinkedList {
public:
    void init ();
    bool isEmpty () const;
    Entry * first () const;
    Entry * last () const;
    Entry * next (Entry *e) const;
    Entry * prev (Entry *e) const;
    void prepend (Entry *e);
    void append (Entry *e);
    void insertBefore (Entry *e, Entry *target);
    void insertAfter (Entry *e, Entry *target);
    void remove (Entry *e);

public:
    Entry *m_first;
    Entry *m_last;
};

...
template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
inline Entry * LinkedList<Entry, NodeMember>::next (Entry *e) const
{
    return (e->*NodeMember).next;
}
...

它可以这样使用：

struct MyEntry {
    int value;
    LinkedListNode<MyEntry> list_node;
};

LinkedList<MyEntry, &MyEntry::list_node> list;
list.init();
MyEntry entry1, entry2;
entry1.value = 3;
list.append(&entry1);
entry2.value = 5;
list.prepend(&entry2);

它可以正常工作，直到您需要两个包含彼此列表的对象：

struct MyEntry2;

struct MyEntry1 {
    int value;
    LinkedListNode<MyEntry1> node;
    LinkedList<MyEntry2, &MyEntry2::node> list;
};

struct MyEntry2 {
    int value;
    LinkedListNode<MyEntry2> node;
    LinkedList<MyEntry1, &MyEntry1::node> list;
};

每个MyEntry1 都持有一个MyEntry2 的列表，每个MyEntry2 只能出现在一个MyEntry1 的列表中；反之亦然。但是，这不会编译，因为成员指针 &MyEntry2::node 是在定义 MyEntry2 之前获取的：

prog.cpp:33:27: error: incomplete type 'MyEntry2' used in nested name specifier
prog.cpp:33:41: error: template argument 2 is invalid

这种有问题的布局实际上没有任何实际语义，这只是我发现的一个理论问题，它可能会限制通用链表的可用性。

有什么方法可以解决这个问题，这不会使列表变得更加不切实际吗？

编辑：这里所有数据结构的布局都是完全定义的。这是因为 LinkedList 的数据成员不依赖有问题的 NodeMember 模板参数；只有函数可以。问题似乎是该语言要求知道 &MyEntry2::node ，即使它当时并不真正需要知道。

编辑：必须可以使用此通用列表将结构添加到两个或多个列表中；这是 NodeMember 模板参数的用途 - 它指定要使用条目中的哪个 LinkedListNode。

4

3 回答 3

2

这是一个使用继承的实现，它不会受到您的问题的影响。

template <typename Entry>
struct LinkedListNode {
    Entry *next;
    Entry *prev;
};

template <class Entry>
class LinkedList {
public:
    void init ();
    bool isEmpty () const;
    Entry * first () const;
    Entry * last () const;
    Entry* next (Entry* e) const {
        return e->next;  
    }
    Entry * prev (Entry *e) const;
    void prepend (Entry *e);
    void append (Entry *e);
    void insertBefore (Entry *e, Entry *target);
    void insertAfter (Entry *e, Entry *target);
    void remove (Entry *e);
public:
    LinkedListNode<Entry> *m_first;
    LinkedListNode<Entry> *m_last;
};

struct MyEntry2;

struct MyEntry1 : public LinkedListNode<MyEntry1> {
    int value;
    LinkedList<MyEntry2> list;
};

struct MyEntry2 : public LinkedListNode<MyEntry2> {
    int value;
    LinkedList<MyEntry1> list;
};

这是一个解决方案，其中 LinkedList 有一个函子作为第二个模板参数。我们使用带有模板的访问器函子 operator()来删除代码重复并延迟名称的查找。注意：访问器实际上应该是一个成员，并使用空基优化处理。

template <class Entry>
struct LinkedListNode {
    Entry *next;
    Entry *prev;
};

template <class Entry, typename Func>
class LinkedList {
public:
    void init ();
    bool isEmpty () const;
    Entry * first () const;
    Entry * last () const;
    Entry * next (Entry *e) const {
      Func f;
      return f(e).next();
    }
    Entry * prev (Entry *e) const;
    void prepend (Entry *e);
    void append (Entry *e);
    void insertBefore (Entry *e, Entry *target);
    void insertAfter (Entry *e, Entry *target);
    void remove (Entry *e);

public:
    Entry *m_first;
    Entry *m_last;
};

struct MyEntry2;

struct node_m_access {
  template <typename T>
  LinkedListNode<T> operator()(T* t) const {
    return t->node;
  }
};

struct MyEntry1 {
    int value;
    LinkedListNode<MyEntry1> node;
    LinkedList<MyEntry2, node_m_access> list;
};

struct MyEntry2 {
    int value;
    LinkedListNode<MyEntry2> node;
    LinkedList<MyEntry1, node_m_access> list;
};
于 2012-10-02T23:20:04.777 回答
0

这个问题相当于尝试这样做：

struct MyEntry2;

struct MyEntry1 {
    MyEntry2 a;
};

struct MyEntry2 {
    MyEntry1 b;
};

在上述情况下，编译器在生成 MyEntry1 时需要知道 MyEntry2 结构的大小。在您的情况下，编译器在生成 MyEntry1 时需要知道 MyEntry2 中节点的偏移量。

我在 template-foo 方面没有经验，但我猜想不是让 Entry 成为一个类，而是使用一个指向类的指针。

于 2012-10-02T22:49:58.080 回答
0

这是 pmr 的访问器解决方案的一个小修改，以减少样板的数量。诀窍是首先提供访问器的不完整“结构”声明，用这些实例化 LinkedList，然后通过从模板访问器类继承来完成访问器。

template <class Entry>
struct LinkedListNode {
    Entry *next;
    Entry *prev;
};

template <class Entry, class Accessor>
class LinkedList {
public:
    void init ();
    bool isEmpty () const;
    Entry * first () const;
    Entry * last () const;
    Entry * next (Entry *e) const {
        return Accessor::access(e).next;
    }
    Entry * prev (Entry *e) const;
    void prepend (Entry *e);
    void append (Entry *e);
    void insertBefore (Entry *e, Entry *target);
    void insertAfter (Entry *e, Entry *target);
    void remove (Entry *e);

public:
    Entry *m_first;
    Entry *m_last;
};

template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
struct LinkedListAccessor {
    static LinkedListNode<Entry> & access (Entry *e)
    {
        return e->*NodeMember;
    }
};

struct MyEntry2;
struct Accessor1;
struct Accessor2;

struct MyEntry1 {
    int value;
    LinkedListNode<MyEntry1> node;
    LinkedList<MyEntry2, Accessor2> list;
};

struct MyEntry2 {
    int value;
    LinkedListNode<MyEntry2> node;
    LinkedList<MyEntry1, Accessor1> list;
};

struct Accessor1 : LinkedListAccessor<MyEntry1, &MyEntry1::node> {};
struct Accessor2 : LinkedListAccessor<MyEntry2, &MyEntry2::node> {};

这样，当循环依赖没有问题时，甚至可以创建一个便利类：

template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
class SimpleLinkedList
: public LinkedList<Entry, LinkedListAccessor<Entry, NodeMember> >
{};
于 2012-10-03T00:38:27.240 回答