Круговая зависимость 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 в записи должен использоваться.

Источник

3 ответа

Решение

Вот реализация, использующая наследование, которая не страдает от вашей проблемы.

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;
};
Источник

Вот небольшая модификация решения для доступа к 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> >
{};
Источник

Эта проблема эквивалентна попытке сделать:

struct MyEntry2;

struct MyEntry1 {
    MyEntry2 a;
};

struct MyEntry2 {
    MyEntry1 b;
};

В приведенном выше случае компилятору необходимо знать размер структуры MyEntry2 при генерации MyEntry1. В вашем случае компилятору необходимо знать смещение узла в MyEntry2 при генерации MyEntry1.

У меня нет опыта в template-foo, но я думаю, что вместо того, чтобы делать Entry классом, вы хотите использовать указатель на класс.

Источник
Другие вопросы по тегам