I've implemented this intrusive linked list:
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;
}
...
It can be used like this:
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);
It works all right, until you need two objects which contain lists of one another:
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;
};
Each MyEntry1 holds a list of MyEntry2's, and each MyEntry2 can only appear in the list of one MyEntry1; and the converse. However, this doesn't compile, because the member pointer &MyEntry2::node is taken before MyEntry2 is defined:
prog.cpp:33:27: error: incomplete type 'MyEntry2' used in nested name specifier
prog.cpp:33:41: error: template argument 2 is invalid
There isn't really any practical semantic to this problematic layout, it is only a theoretical problem I've found which may limit the usability of the generic linked list.
Is there any way around this which doesn't make the list considerably more impractical?
EDIT: the layout of all data structures here is completely defined. This is because the data members of LinkedList do not depend on the problematic NodeMember template parameter; only the functions do. The problem seems to be that the language is demanding that &MyEntry2::node be known even though it does not really need to be known at the time.
EDIT: it must be possible to use this generic list to add a structure into two or more lists; this is the purpose of the NodeMember template parameter - it specifies which LinkedListNode within the entry is to be used.
Here is an implementation using inheritance that does not suffer from your problem.
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;
};
Here is a solution where the LinkedList has a functor as second
template argument. We use an accessor functor with a templated
operator()
to remove code duplication and to delay look-up of the
name. Note: The accessor should actually be a member and treated with an
empty base optimization.
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;
};