C ++中的链接列表使用引用而不是指针 [英] Linked-list in C++ using references instead of pointers

问题描述

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

  struct ListNode 
 {
 int value; 
 ListNode * nextNode; 
} 
  

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

  struct ListNodeWithRefs 
 {
 int value; 
 ListNodeWithRefs& nextNode; 
} 
  

我不知道它会提供任何性能收益，但...这个问题在编码时弹出，我的答案是否，但我可能会缺少某些东西。

原则上，没有什么可以阻止你使用引用和构造列表优化：

  ListNodeWithRefs :: ListNodeWithRefs（ListNodeWithRefs& next）：
 nextNode 
 {} 
  

但是有一个鸡蛋和鸡蛋问题，因为 next 还强制执行其下一个元素在其创建时存在...等等...

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

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

解决方案

通过sbi，它似乎工作： http://stackoverflow.com/a/3003607/1758762

  //小心，未编译的代码！ 
 template< typename T> 
结构节点; 
 
模板< typename T> 
 struct links {
 node< T>&上一页
 node& T&下一个; 
 link（node< T> * prv，node< T> * nxt）; //省略
}; 
 
模板< typename T> 
 struct node {
 T data; 
链接< T> linked_nodes; 
 node（const T& d，node * prv，node * nxt）; //省略
}; 
 
 //技术上，这导致UB ... 
模板< 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）; 
} 
 
模板< 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 =新节点< T>（data，prev，next）; 
 
 link_nodes（prev，new_node）; 
 link_nodes（new_node，next）; 
} 
  

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)
{}

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

解决方案

Take a look at this example by sbi, it seems to work: http://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);
}

这篇关于C ++中的链接列表使用引用而不是指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！