使用引用而不是指针在C++中实现链表

Question

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

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

- fons

---

只有在尝试将节点插入列表头之外的任何位置时才会出现问题。 - StoryTeller - Unslander Monica

你将如何表示最终节点？引用不能为空。 - Vlad

正如@Vlad所说，使用引用的问题在于您需要一个最终对象。好消息是，原则上，您仍然可以拥有一个循环列表。如果您有用它的地方。 - alfC

Answer 1

这是函数式语言中常见的cons列表的典型形式：

data List a = Empty | Node a (List a)

诀窍在于，List a 是一个完整的类型，可以引用空的或另一个节点（这就是它可以终止的原因）。

为了在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 并不是很面向对象，但通过标记使用的替代方案，它使事情更接近函数示例。

- Matthieu M.

---

或者只是使用 boost::variant<ListBase<T>, EmptyList> NextNode，与 struct ListNode<T>{ T Value; NextNode next; }; 不完全相同，因为您需要使用递归的 variant 语法来使其正常工作。EmptyList 不必与 ListBase<T> 相关。作为另一种选择，boost::optional<ListNode<T>> 可能更接近概念（为什么要标记为空，当您可以不拥有它？）。 - Yakk - Adam Nevraumont

@Yakk：是的，boost::optional<T> 是 Haskell 的 Maybe a 的直接映射，而 boost::variant<T,U> 则是 Haskell 的 Either a b 的直接映射，它们确实都可以消除继承。我认为它们也是稍微复杂一些的概念。 - Matthieu M.

Answer 2

请看sbi提供的这个例子，它似乎能够起作用：https://dev59.com/WXA75IYBdhLWcg3w-OVA#3003607。

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

- Leo Chapiro

---

你能举个例子来说明如何使用这个类吗？看起来需要逐个生成节点（处于某些无效状态），然后再逐个链接它们。 - alfC

我认为我对这个解决方案有了更深的理解。但它基本上所做的技巧就是通过放置新的技巧重新绑定引用。我不知道它是否是未定义行为，但它打败了使用引用作为链接的目的。它基本上将它们用作（可重新绑定的）指针。 - alfC

Answer 3

列表如何结束？

您至少需要两种类型：结束和非结束。您还需要进行生命周期管理。并且需要运行时或静态知识来确定类型。

可以进行完全静态的实现，其中每个节点都是其自己的类型，知道到达末尾的距离。

或者您可以只有一个未初始化的缓冲区，并以相反的顺序创建元素。

也可以使用循环。使第一个引用指向您构造的最后一个元素。

- Yakk - Adam Nevraumont

Answer 4

原因：

1. 如果nextNode是一个引用，您无法插入节点。
2. 如果这是列表尾部，nextNode应该指向什么？

- Chen

---

错误：1/问题涉及到一个不可修改的列表，2/你可以让最后一个元素来自于一个超类而不需要nextnode引用。 - Camion

Answer 5

避免具有引用的列表中出现“鸡蛋问题”的简单方法是记住首先分配对象内存，然后调用构造函数。此外，C++标准保证可以在构造函数内访问this指针。

解决此问题的巧妙方法：

struct node {
    int data;
    node& next;
    node(node& n, int d): next(n), data(d) {}
};

node tl(tl, 69); // tl is already in the scope!

- Eugene

---

这是一个新手问题，next(n)和data(d)是什么意思？它只是等同于next = n;吗？ - minh anh b

是的，你是正确的，这就是构造函数中的初始化列表。引用必须在那里初始化。 - Eugene

Answer 6

那有点棘手，但这个方法行得通：

#include <iostream>
#include <typeinfo>

class Last {
  public:

    int x;
    int last;

    Last(int i) {
      std::cout << "parent constructor(" << i << ")\n";
      x = i;
      last = 1;
    }
};

struct fourptr {
    int v1, v2;
    void *p1, *p2;
    };

class chain : public Last {
  public:

    chain(int i) : Last(i) {
    std::cout << "child constructor(" << i << ")\n";
    last = 0;
    }

    void viewandnext() {
      struct fourptr *fp = (struct fourptr *) this;
      std::cout << x << ", this = " << this
                << ", sizeof *this = "<< sizeof * this
                << ", * this = {" << fp->v1 << ", " << fp->v2 << ", "
                << fp->p1 << ", " << fp->p2 << "}"
                << "\n";
      if (last == 0) ((chain &)next).viewandnext();
    }

  Last & fn(int x) {
    Last * e = (x>0) ? new chain(x-1) : new Last(x-1);
    return *e;
  }

    Last & next = fn(x); // This is not a pointer but a reference
};



int main(void) {
  chain &l = *(new chain(8));
  std::cout << "sizeof l = "<< sizeof l << "\n";
  l.viewandnext();
}

- Camion

Answer 7

正如Vlad所说，引用的问题在于您需要一个最终对象。 好消息是，原则上，如果您有使用它的话，仍然可以拥有循环列表。 这是一件基本的事情，如果“下一个”元素是非空引用，则意味着总是有下一个元素，即列表要么是无限的，要么更现实的是，它会封闭在自身或另一个列表中。

进一步探究这个问题非常有趣而奇怪。 基本上唯一可能的事情是定义等效的节点（也代表列表）。

template<class T>
struct node{
    T value; // mutable?
    node const& next;
    struct circulator{
        node const* impl_;
        circulator& circulate(){impl_ = &(impl_->next); return *this;}
        T const& operator*() const{return impl_->value;}
        friend bool operator==(circulator const& c1, circulator const& c2){return c1.impl_ == c2.impl_;}
        friend bool operator!=(circulator const& c1, circulator const& c2){return not(c1==c2);}
    };
    circulator some() const{return circulator{this};}
};

元素必须存在于堆栈中，而列表是静态的（好吧，引用无论如何都不能重新绑定），并且链接必须是const引用！最终，value可以显然地变为mutable（可能是安全的？）。（此时，人们会想知道这与通过模数索引引用堆栈数组有何不同。）

构建node/list对象的唯一方法是使用自身（或其他预先存在的节点）关闭它。因此，生成的列表要么是循环的，要么是“rho”形状。

    node<int> n1{5, {6, {7, n1}}};
    auto c = n1.some();
    cout << "size " << sizeof(node<int>) << '\n';
    do{
        cout << *c << ", ";
        c.circulate();
    }while(c != n1.some()); //prints 5, 6, 7

我无法创建一个不是平凡可构造的节点（聚合体？）。 （添加任何基本构造函数都会因为我无法理解的原因在gcc和clang中产生分段错误）。 我也无法将节点封装在“容器”对象中，出现了同样奇怪的问题。 因此，对我来说，创建可以像这样构造的对象是不可能的：

circular_list<int> l{1,2,3,4}; // couldn't do this for obscure reasons

最后，由于无法构建适当的容器，因此不清楚这个对象的语义是什么，例如当两个“列表”相等时意味着什么？什么不意味着分配？或在不同大小的列表之间进行分配？

它是一个相当自相矛盾的对象，似乎没有一般价值或引用语义。

欢迎任何评论或改进！

- alfC

Answer 8

我可能有点离谱，但这个可以工作

    struct Node;
struct Node {

    using link = std::reference_wrapper<Node>;

    Node( char data_  =  0) 
        : next({*this})
        , data( data_ == 0 ? '?' : data_ ) 
    {}

    bool is_selfref() const noexcept {
        return (this == & next.get());
    }

    char data;
    link next;
};

通常的测试

 Node A('A');     
 Node B('B');     
 Node C('C');     
 assert( A.is_selfref() == B.is_selfref() == C.is_selfref());

 A.next = B;  B.next = C;

 assert(! A.is_selfref() && ! B.is_selfref() );
 assert(  C.is_selfref() );

 assert( 'A' == A.data );
 assert( 'B' == A.next.get().data );
 assert( 'C' == A.next.get().next.get().data );

 // C.next == C

 // for those who feel safe seeing the END
 Node END(127);
 C.next = END;

当然，只要所有节点都保持在范围内，我们就没问题。否则不行。奇怪而美妙。实用性非常有限？

- Chef Gladiator