C++中使用引用而不是指针的链表
假设我想创建一个不可修改的链表(即，它只能被遍历，一旦它被创建，就不能添加或删除任何节点)。这可以通过以下方式轻松实现：
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;
}回答 8
Stack Overflow用户
发布于 2013-03-03 21:39:39
看看印度国家银行的这个例子，它似乎是有效的：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);
}Stack Overflow用户
发布于 2013-03-03 22:16:13
这是函数式语言中典型的cons-list：
data List a = Empty | Node a (List a)不过，诀窍是，List a是一个完整的类型，它可以将的指向Empty或另一个节点(这就是它可以终止的原因)。
为了在C++中实现这一点，您可以利用联合(但它没有得到很好的支持)或多态性。
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并不是面向对象的，但它使事情更接近于使用标记的函数示例。
Stack Overflow用户
发布于 2013-03-03 21:55:42
这个列表是如何结束的？
您至少需要两种类型: end和not。你还需要终生管理。以及哪种类型的运行时或静态知识。
可以完成一个完全静态的实现，其中每个节点都是它自己的类型，知道它离终点有多远。
或者，您可以只使用一个未初始化的buffer，并以相反的顺序在其上创建元素。
圆圈也是可能的。使第一个引用引用您构造的最后一个元素。
https://stackoverflow.com/questions/15186196
复制相似问题
腾讯云开发者
