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

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

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。

最佳答案

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

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

关于c++ - 具有侵入式链表的C++循环依赖，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12699452/