问题描述
假设我想创建一个不可修改的链表(即它只能被遍历,一旦它最初被创建就不能添加或删除节点).这可以通过以下方式轻松实现:
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);
}
这篇关于C++ 中的链表使用引用而不是指针的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!