动态分配双向链接循环列表类实例segfault C ++

Using this template class works perfectly fine when main operates with constructed variables of type dlring, yet my goal is to allow dynamic allocation, so I can handle a non-predefined number of doubly linked circular lists to allow usage of such functions as:

当main使用类型为dlring的构造变量进行操作时,使用此模板类可以正常工作,但我的目标是允许动态分配,因此我可以处理非预定义数量的双向链接循环列表,以允许使用以下函数:

Splitting a list into two by either using a node position (via
iteration) or value entry.

通过使用节点位置(通过迭代)或值输入将列表拆分为两个。

Same goes for linking two lists into one with a single head/tail pair.

将两个列表链接到一个具有单个头/尾对的列表也是如此。

Node exporting from one list (instance) to another.

节点从一个列表(实例)导出到另一个列表。

Etc.

I'm pretty much sure there is an elegant workaround which is simply not known by me yet, but I don't think it's nice to come up with a question for the community if you didn't struggle enough to resolve. (checked google

我非常确定有一个优雅的解决方法,但我还不知道,但如果你没有足够的解决方法,我认为为社区提出一个问题并不好。 (检查谷歌

So with that goals I'm supposed to dynamically allocate memory (via constructor calls) using some kind of pointer-to-pointer, AFAIK. If there is a smarter way to implement these, please let me know. My solution attempt is given in the end of this snippet. Feel free to criticize all of the below.

因此,有了这些目标,我应该使用某种指针指针AFAIK动态分配内存(通过构造函数调用)。如果有更聪明的方法来实现这些,请告诉我。我的解决方案尝试在此片段的末尾给出。随意批评以下所有内容。

Doubly linked circular list class header (simplified)

template <typename T>
class dlring
{
    struct node
    {
        T data;
        node* prev;
        node* next;
        node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
    };
    node* head;
    node* tail;
public:
    dlring():head(nullptr), tail(nullptr){}
    bool empty() const { return ( !head || !tail ); }
//operator bool() const { return !empty(); }
    void Push(T);
    T pop_back();
    ~dlring()
    {
        while(head)
        {
            node* temp(head);
            head=head->next;
            delete temp;
        }
    }
};

Should I use the commented out operator bool overload?

我应该使用注释掉的操作符bool重载吗?

pop_back and Push methods:

template <typename T>
void dlring<T>::Push(T data)
{
    head = new node(data, tail, head); 
    if( head->next )
    {
        head->next->prev = head;
        tail->next = head;
    }
    if( empty() )
    {
        tail = head;
        head->next=tail;
        head->prev=tail;
        tail->next=head;
        tail->prev=head;
    }
}
template<typename T>
T dlring<T>::pop_back()
{
    if( empty() )
        std::cout<<"List empty";
    node* temp(tail);
    T data( tail->data );
    tail = tail->prev ;
    if (tail != temp)
    {
        tail->next->next = head; 
        head->prev = tail;
    }
    else
    {
        head = nullptr;
        tail = nullptr;
    }
    delete temp;
    temp = nullptr;
    return data;
}

My attempt doesn't have the right behaviour: When I'm trying to show all the lists via a iteration the code fails, segfaulting on head->data access attempt of dlist[0], where 0 is an iteration of k. Here is the snippet:

我的尝试没有正确的行为:当我试图通过迭代显示所有列表时,代码失败,在头部上进行分区 - > dlist [0]的数据访问尝试,其中0是k的迭代。这是片段:

   int main()
    {
    int k;
      std::cout<<"Rings count?"<<std::endl;
      std::cin>>k;
        dlring<int>* dlist = new dlring<int>[k]; //I suppose I'm allocating *k*
     //dlring<int> elements. this line is not confirmed to call the constructor.
    (dlist[0]).Push(10);
    (dlist[0]).Push(13);
    (dlist[1]).Push(99);
    /*{
    while(!dlist[0].empty())
    std::cout<<(dlist[0]).pop_back()<<" ";
    std::cout<<std::endl;
    while(!dlist[1].empty())
    std::cout<<(dlist[1]).pop_back()<<" ";
    }*/
    //this section works perfectly fine, while this
      for(int i=0;i<k;i++)
      {
        while(!dlist[k].empty())
        std::cout<<(dlist[k]).pop_back()<<" ";
        std::cout<<std::endl;
      }
    //is causing a segmentation fault while attempting to access dlist[*0*].tail->data.
    std::cout<<(dlist[0]).head->data;
    //line was checked and is confirmed to be functional, 
    //I suppose dlist[variable] has some trick I don't know yet.
    //what I wish to look like an instance call would be *
    return 0;
    }

Best regards. Again, feel free to criticize any of my code/logics.

最好的祝福。再次,随意批评我的任何代码/逻辑。

1 个解决方案

#1

  for(int i=0;i<k;i++)
  {
    while(!dlist[k].empty())
    std::cout<<(dlist[k]).pop_back()<<" ";
    std::cout<<std::endl;
  }

Is not using the iterator i. It should be:

是不是使用迭代器我。它应该是:

  for(int i=0;i<k;i++)
  {
    while(!dlist[i].empty())
    std::cout<<(dlist[i]).pop_back()<<" ";
    std::cout<<std::endl;
  }

Since dlist is an array of size k, the original code produces an out-of-bounds access.

由于dlist是大小为k的数组,因此原始代码会产生越界访问。

Since the aforementioned loop makes every list in the dlist array empty, the head of all of them will be a null pointer. Note that you shouldn't be able to access it at all, since it is a private member. If you do, you'll get an segfault when dereferencing it:

由于上述循环使dlist数组中的每个列表都为空,因此所有列表的头部都是空指针。请注意,您根本无法访问它,因为它是私有成员。如果你这样做,你将在解除引用时得到段错误:

std::cout<<(dlist[0]).head->data;

If this compiles, at this point in the program, dlist[0].head == nullptr, therefore segfault.

如果这个编译,在程序的这一点,dlist [0] .head == nullptr,因此segfault。

Also note that you're leaking memory since you're not releasing the dynamically allocated dlist. Append to the end of you program:

另请注意,由于您未发布动态分配的dlist,因此泄漏了内存。附加到您的程序结束:

delete[] dlist;

With those changes, I don't get any segfaults, or issues, or reports from clang's address sanitizer.

通过这些更改,我不会从clang的地址清理程序中获得任何段错误,问题或报告。

Another issue (that doesn't manifest in your main) is the set-up of tail in pop_back. I'll try to use some ASCII art for illustration. A box

另一个问题(在你的主要部分没有表现出来)是在pop_back中设置tail。我将尝试使用一些ASCII艺术作为插图。一个盒子

   D ->
<- D

denotes a node with Data, a next pointer and a prev pointer. All arrows are pointers.

表示具有Data的节点,下一个指针和prev指针。所有箭头都是指针。

A nonempty list:

非空列表:

   +-----------------------------+
   v                             |
   D ->    D -> ..    D ->    D -+
+- D    <- D    .. <- D    <- D
|                             ^
+-----------------------------+
   ^                          ^
   |head                      |tail

head->prev points to the same object as tail, and similarly, tail->next points to the same object as head.

head-> prev指向与tail相同的对象,类似地,tail-> next指向与head相同的对象。

Now, an "animation" of the pop_back function.

现在,pop_back函数的“动画”。

template<typename T>
T dlring<T>::pop_back()
{
    if( empty() )
        std::cout<<"List empty";
    node* temp(tail);

    /*
       +-----------------------------+
       v                             |
       D ->    D -> ..    D ->    D -+
    +- D    <- D    .. <- D    <- D
    |                             ^
    +-----------------------------+
       ^                          ^
       |head                      |tail
                                  |temp
    */

    T data( tail->data );
    tail = tail->prev ;

    /*
       +-----------------------------+
       v                             |
       D ->    D -> ..    D ->    D -+
    +- D    <- D    .. <- D    <- D
    |                             ^
    +-----------------------------+
       ^                  ^       ^
       |head              |tail   |temp
    */

    if (tail != temp)
    {
        tail->next->next = head; 

        /*
           +-----------------------------+
           v                             |
           D ->    D -> ..    D ->    D -+  (A)
        +- D    <- D    .. <- D    <- D
        |                             ^
        +-----------------------------+
           ^                  ^       ^
           |head              |tail   |temp

        The pointer (A) is what is changed when writing to tail->next->next.
        Yes, nothing has actually changed in the list!
        */

        head->prev = tail;

        /*
           +-----------------------------+
           v                             |
           D ->    D -> ..    D ->    D -+
        +- D    <- D    .. <- D    <- D
        |                     ^
        +---------------------+
           ^                  ^       ^
           |head              |tail   |temp
        */

    }
    else
    {
        head = nullptr;
        tail = nullptr;
    }
    delete temp;

    /*
       D ->    D -> ..    D ->
    +- D    <- D    .. <- D
    |                     ^
    +---------------------+
       ^                  ^       ^
       |head              |tail   |temp
    */

    temp = nullptr;
    return data;
}

Note that in the last "picture", tail->next is an invalid pointer.

请注意,在最后一个“图片”中,tail-> next是无效指针。

Instead, it should be:

相反,它应该是:

    if (tail != temp)
    {
        tail->next = head; 

        /*
           +---------------------+-------+
           v                     |       |
           D ->    D -> ..    D -+    D -+
        +- D    <- D    .. <- D    <- D
        |                             ^
        +-----------------------------+
           ^                  ^       ^
           |head              |tail   |temp

After deletion of temp (no further changes), it will look like this:

删除temp(没有进一步的更改)后,它将如下所示:

        /*
           +---------------------+
           v                     |
           D ->    D -> ..    D -+
        +- D    <- D    .. <- D
        |                     ^
        +---------------------+
           ^                  ^       ^
           |head              |tail   |temp

Last but not least, please be aware that you're violating the Rule of Three.

最后但同样重要的是,请注意您违反了三条规则。

#1

  for(int i=0;i<k;i++)
  {
    while(!dlist[k].empty())
    std::cout<<(dlist[k]).pop_back()<<" ";
    std::cout<<std::endl;
  }