7

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

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

8 回答 8

4

这是函数式语言中典型的缺点列表：

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

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

为了在 C++ 中实现这一点，您可以利用union（但它没有得到很好的支持）或polymorphism。

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基类中的存在并不是OO，而是通过标记使用哪个替代项使事情更接近功能示例。

于 2013-03-03T14:16:12.600 回答
3

看看 sbi 的这个例子，它似乎工作：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-03T13:39:38.633 回答
2

清单如何结束？

你至少需要两种类型：结束和非。您还需要生命周期管理。以及哪种类型的运行时或静态知识。

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

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

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

于 2013-03-03T13:55:41.947 回答
1

没有。原因：

  1. 如果 nextNode 是引用，则不能插入节点。
  2. 如果这是列表尾， nextNode 应该指的是什么？
于 2013-03-03T13:41:38.150 回答
0

正如@Vlad 所说，引用的问题是您将需要一个最终对象。好消息是，原则上，你仍然可以拥有一个循环列表，如果你有它的用处。这是一个基本的事情，如果“下一个”元素是不可为空的引用，则意味着总是有下一个元素，也就是说，列表要么是无限的，要么更现实地说，它会自行关闭或关闭到另一个列表中。

进一步练习是相当有趣和奇怪的。基本上，似乎唯一可能的事情是定义 a 节点的等价物（它也代表列表）。

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（可能安全吗？）。（此时人们想知道这与模索引的堆栈数组引用有何不同。）

构造 /list 对象的方法只有一种node，即用它自己（或用其他预先存在的节点）关闭它。所以结果列表要么是圆形的，要么是“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

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

这是一个非常矛盾的对象，显然没有普遍的价值或引用语义。

欢迎任何意见或改进！

于 2018-06-01T18:23:54.297 回答
0

我可能不合时宜，但这有效

    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;

当然，只要所有 Node 都在范围内，我们都可以。否则不行。奇怪而美妙。实用性非常有限？

于 2019-03-08T07:25:19.367 回答
0

这很棘手，但这有效：

#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();
}
于 2019-05-01T15:36:41.380 回答
0

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

解决此问题的巧妙方法：

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!
于 2021-02-12T20:26:18.120 回答