0

私はこの邪魔なリンクリストを実装しました：

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

相互のリストを含む2つのオブジェクトが必要になるまで、問題なく機能します。

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は1つのMyEntry1のリストにのみ表示できます。とその逆。ただし、MyEntry2が定義される前にメンバーポインタ＆MyEntry2 :: nodeが取得されるため、これはコンパイルされません。

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を認識していることを要求していることのようです。

編集：この汎用リストを使用して、構造を2つ以上のリストに追加できる必要があります。これがNodeMemberテンプレートパラメータの目的です。エントリ内のどのLinkedListNodeを使用するかを指定します。

4

3 に答える 3

2

これは、問題に悩まされない継承を使用した実装です。

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 が 2 番目のテンプレート引数としてファンクターを持つソリューションです。テンプレート化されたアクセサーファンクターを使用して、 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;
};
于 2012-10-02T23:20:04.777 に答える
0

この問題は、次のことを試みるのと同じです。

struct MyEntry2;

struct MyEntry1 {
    MyEntry2 a;
};

struct MyEntry2 {
    MyEntry1 b;
};

上記の場合、コンパイラは MyEntry1 を生成するときに MyEntry2 構造体のサイズを知る必要があります。あなたの場合、コンパイラは MyEntry1 の生成中に MyEntry2 のノードのオフセットを知る必要があります。

私は template-foo の経験はありませんが、 Entry をクラスにする代わりに、クラスへのポインターを使用したいと思います。

于 2012-10-02T22:49:58.080 に答える
0

これは、ボイラープレートの量を減らすために 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> >
{};
于 2012-10-03T00:38:27.240 に答える