具有侵入式链表的 C++ 循环依赖

Question

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

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。

Answer 1

这是一个使用继承的实现，不会受到你的问题。

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