首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >C++中使用引用而不是指针的链表

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

Stack Overflow用户
提问于 2013-03-03 21:33:26
回答 8查看 7.4K关注 0票数 7

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

代码语言:javascript
复制
struct ListNode
{
  int value;
  ListNode* nextNode;
}

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

代码语言:javascript
复制
struct ListNodeWithRefs
{
  int value;
  ListNodeWithRefs &nextNode;
}

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

原则上,没有什么能阻止你使用引用,并像这样构造列表元素:

代码语言:javascript
复制
ListNodeWithRefs::ListNodeWithRefs(ListNodeWithRefs &next):
  nextNode(next)
{}

但是有一个鸡和蛋的问题,因为next还强制它的next元素在它的创建时存在,等等……

注意:我想我的问题也可以用来定义这个列表:

代码语言:javascript
复制
struct ListNodeConst
{
  int value;
  const ListNode* nextNode;
}
EN

回答 8

Stack Overflow用户

回答已采纳

发布于 2013-03-03 21:39:39

看看印度国家银行的这个例子,它似乎是有效的:https://stackoverflow.com/a/3003607/1758762

代码语言:javascript
复制
// 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);
}
票数 3
EN

Stack Overflow用户

发布于 2013-03-03 22:16:13

这是函数式语言中典型的cons-list:

代码语言:javascript
复制
data List a = Empty | Node a (List a)

不过,诀窍是,List a是一个完整的类型,它可以将指向Empty或另一个节点(这就是它可以终止的原因)。

为了在C++中实现这一点,您可以利用联合(但它没有得到很好的支持)或多态性。

代码语言:javascript
复制
template <typename T>
struct ListBase {
    enum class Kind { Empty, Node };
    explicit ListBase(Kind k): _kind(k) {}

    Kind _kind;
};

然后:

代码语言:javascript
复制
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并不是面向对象的,但它使事情更接近于使用标记的函数示例。

票数 3
EN

Stack Overflow用户

发布于 2013-03-03 21:55:42

这个列表是如何结束的?

您至少需要两种类型: end和not。你还需要终生管理。以及哪种类型的运行时或静态知识。

可以完成一个完全静态的实现,其中每个节点都是它自己的类型,知道它离终点有多远。

或者,您可以只使用一个未初始化的buffer,并以相反的顺序在其上创建元素。

圆圈也是可能的。使第一个引用引用您构造的最后一个元素。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/15186196

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档