C++ 中的链表使用引用而不是指针

2022-01-01 00:00:00 linked-list data-structures reference c++

假设我想创建一个不可修改的链表(即它只能被遍历，一旦它最初被创建就不能添加或删除节点).这可以通过以下方式轻松实现:

Suppose I want to create an unmodifiable linked-list (i.e. it can only be traversed, no nodes can be added or removed once it was initially created). This could be easily implemented by:

struct ListNode
{
  int value;
  ListNode* nextNode;
}

我的问题是......是否可以使用引用而不是指针?

My question is .... Would it be possible to use references instead of pointers?

struct ListNodeWithRefs
{
  int value;
  ListNodeWithRefs &nextNode;
}

我不确定它是否会提供任何性能提升，但是......在编码时出现了这个问题，到目前为止我的答案是没有，但我可能会遗漏一些东西.

I am not sure it would provide any performance gain at all but ... this question popped up while coding and my answer so far is no but I could be missing something.

原则上，没有什么可以阻止您使用引用，并像这样构建列表元素:

In principle, nothing prevents you from using references, and constructing list elments like this:

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

但是存在先有鸡还是先有蛋的问题，因为 next 还强制其 next 元素在其创建时就存在，依此类推...

But there is a chicken and egg problem because next also enforces its next element to exist at its creation and so on ...

注意:我认为我的问题也可以应用于将列表定义为:

Note: I think my question can also be applied to defining the list as:

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

推荐答案

看看 sbi 的这个例子，它似乎有效:https://stackoverflow.com/a/3003607/1758762

Take a look at this example by sbi, it seems to work: https://stackoverflow.com/a/3003607/1758762

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

相关文章