7

変更不可能なリンク リストを作成したいとします (つまり、トラバースのみ可能で、最初に作成されたノードは追加または削除できません)。これは、次の方法で簡単に実装できます。

struct ListNode
{
  int value;
  ListNode* nextNode;
}

私の質問は....ポインターの代わりに参照を使用することは可能でしょうか?

struct ListNodeWithRefs
{
  int value;
  ListNodeWithRefs &nextNode;
}

パフォーマンスがまったく向上するかどうかはわかりませんが...コーディング中にこの質問がポップアップし、これまでの私の答えは「いいえ」ですが、何かが欠けている可能性があります。

原則として、参照を使用したり、次のようなリスト要素を作成したりすることを妨げるものは何もありません。

ListNodeWithRefs::ListNodeWithRefs(ListNodeWithRefs &next):
  nextNode(next)
{}

しかし、作成時にその要素が存在することnextを強制するなど、鶏が先か卵が先かという問題があります...next

注：私の質問は、リストを次のように定義することにも適用できると思います。

struct ListNodeConst
{
  int value;
  const ListNode* nextNode;
}
4

8 に答える 8

4

これは、関数型言語のcons-listの典型です。

data List a = Empty | Node a (List a)

秘訣はList a、完全な型であり、または別Emptyのノードを参照できることです (これが、終了できる理由です)。

C++ でこれを実現するには、union (ただし、あまりサポートされていません) またはpolymorphismのいずれかを利用できます。

template <typename T>
struct ListBase {
    enum class Kind { Empty, Node };
    explicit ListBase(Kind k): _kind(k) {}

    Kind _kind;
};

その後：

template <typename T>
struct EmptyList: ListBase<T> {
    EmptyList(): ListBase<T>(Kind::Empty) {}
};

template <typename T>
struct ListNode: ListBase<T> {
    ListNode(T const& t, ListBase<T>& next):
        ListBase<T>(Kind::Node), _value(t), _next(next) {}

    T _value;
    ListBase<T>& _next;
};

そして今、鶏と卵の問題はもうありません。のインスタンス化から開始するだけですEmptyList<T>。

注:_kind基本クラスに が存在することは OO ではありませんが、どの代替が使用されているかをタグ付けすることで、物事を機能例に近づけます。

于 2013-03-03T14:16:12.600 に答える
3

sbi によるこの例を見てください。

// Beware, un-compiled code ahead!
template< typename T >
struct node;

template< typename T >
struct links {
  node<T>& prev;
  node<T>& next;
  link(node<T>* prv, node<T>* nxt); // omitted
};

template< typename T >
struct node {
  T data;
  links<T> linked_nodes;
  node(const T& d, node* prv, node* nxt); // omitted
};

// technically, this causes UB...
template< typename T >
void my_list<T>::link_nodes(node<T>* prev, node<T>* next)
{
  node<T>* prev_prev = prev.linked_nodes.prev;
  node<T>* next_next = next.linked_nodes.next;
  prev.linked_nodes.~links<T>();
  new (prev.linked_nodes) links<T>(prev_prev, next);
  next.linked_nodes.~links<T>();
  new (next.linked_nodes) links<T>(next, next_next);
}

template< typename T >
void my_list<T>::insert(node<T>* at, const T& data)
{
  node<T>* prev = at;
  node<T>* next = at.linked_nodes.next;
  node<T>* new_node = new node<T>(data, prev, next);

  link_nodes(prev, new_node);
  link_nodes(new_node, next);
}
于 2013-03-03T13:39:38.633 に答える
2

リストはどのように終了しますか?

エンドとノットの少なくとも 2 つのタイプが必要です。生涯管理も必要です。そして、どのタイプの実行時または静的な知識です。

完全に静的な実装を行うことができます。各ノードは、最後までの距離を認識している独自のタイプです。

または、初期化されていないバッファを使用して、逆の順序で要素を作成することもできます。

サークルも可能です。最初の参照が、作成した最後の要素を参照するようにします。

于 2013-03-03T13:55:41.947 に答える
1

いいえ。理由：

  1. nextNodeが参照の場合、ノードを挿入することはできません。
  2. これがリストテールである場合、nextNodeは何を参照する必要がありますか？
于 2013-03-03T13:41:38.150 に答える
0

それはかなりトリッキーでしたが、これはうまくいきました：

#include <iostream>
#include <typeinfo>

class Last {
  public:

    int x;
    int last;

    Last(int i) {
      std::cout << "parent constructor(" << i << ")\n";
      x = i;
      last = 1;
    }
};

struct fourptr {
    int v1, v2;
    void *p1, *p2;
    };

class chain : public Last {
  public:

    chain(int i) : Last(i) {
    std::cout << "child constructor(" << i << ")\n";
    last = 0;
    }

    void viewandnext() {
      struct fourptr *fp = (struct fourptr *) this;
      std::cout << x << ", this = " << this
                << ", sizeof *this = "<< sizeof * this
                << ", * this = {" << fp->v1 << ", " << fp->v2 << ", "
                << fp->p1 << ", " << fp->p2 << "}"
                << "\n";
      if (last == 0) ((chain &)next).viewandnext();
    }

  Last & fn(int x) {
    Last * e = (x>0) ? new chain(x-1) : new Last(x-1);
    return *e;
  }

    Last & next = fn(x); // This is not a pointer but a reference
};



int main(void) {
  chain &l = *(new chain(8));
  std::cout << "sizeof l = "<< sizeof l << "\n";
  l.viewandnext();
}
于 2019-05-01T15:36:41.380 に答える