шаблоны — круговая зависимость 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;
};
Другие решения
Эта проблема эквивалентна попытке сделать:
struct MyEntry2;
struct MyEntry1 {
MyEntry2 a;
};
struct MyEntry2 {
MyEntry1 b;
};
В приведенном выше случае компилятору необходимо знать размер структуры MyEntry2 при генерации MyEntry1. В вашем случае компилятору необходимо знать смещение узла в MyEntry2 при генерации MyEntry1.
У меня нет опыта в template-foo, но я думаю, что вместо того, чтобы делать Entry классом, вы хотите использовать указатель на класс.
Вот небольшая модификация решения для доступа к PMR, чтобы уменьшить количество шаблонов. Хитрость заключается в том, чтобы сначала предоставить неполное «struct» объявление методов доступа, создать экземпляр 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> >
{};