假设我想创建一个不可修改的链表(即,它只能被遍历,一旦它被创建,就不能添加或删除任何节点)。这可以通过以下方式轻松实现:
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;
}
发布于 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);
}
发布于 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
并不是面向对象的,但它使事情更接近于使用标记的函数示例。
发布于 2013-03-03 21:55:42
这个列表是如何结束的?
您至少需要两种类型: end和not。你还需要终生管理。以及哪种类型的运行时或静态知识。
可以完成一个完全静态的实现,其中每个节点都是它自己的类型,知道它离终点有多远。
或者,您可以只使用一个未初始化的buffer,并以相反的顺序在其上创建元素。
圆圈也是可能的。使第一个引用引用您构造的最后一个元素。
https://stackoverflow.com/questions/15186196
复制相似问题