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;
}
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.
最后但同样重要的是,请注意您违反了三条规则。