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 ::節點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，也要知道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; 
}; 

這裏就是鏈表具有算符作爲第二 模板參數的溶液。我們使用模板化的 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; 
}; 

Answer 2

這個問題就等於要做：

struct MyEntry2; 

struct MyEntry1 { 
    MyEntry2 a; 
}; 

struct MyEntry2 { 
    MyEntry1 b; 
}; 

在上述情況下，編譯器需要生成MyEntry1當知道MyEntry2結構的大小。就你而言，編譯器需要在生成MyEntry1時知道MyEntry2中節點的偏移量。

我沒有在template-foo中體驗過，但我猜想不是讓Entry成爲一個類，而是想使用指向類的指針。

Answer 3

這是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> > 
{};