我正在尝试用 C++ 编写一个基本的单链表类。几年前我在我的数据结构课上做过,但我不记得细节了。
我的 Node 类应该有一个复制构造函数吗?它有一个 Node* 作为成员变量,据我所知,您总是应该为具有动态成员的类编写复制构造函数、析构函数和赋值运算符。但是从我在网上看到的情况来看,List 类负责节点的复制。真的是这样吗?如果是这样,为什么?
我正在尝试用 C++ 编写一个基本的单链表类。几年前我在我的数据结构课上做过,但我不记得细节了。
我的 Node 类应该有一个复制构造函数吗?它有一个 Node* 作为成员变量,据我所知,您总是应该为具有动态成员的类编写复制构造函数、析构函数和赋值运算符。但是从我在网上看到的情况来看,List 类负责节点的复制。真的是这样吗?如果是这样,为什么?
对于基本的单链表类,我建议:
如果您没有定义它们,C++ 会生成一个默认的复制构造函数和赋值运算符。我建议您禁用这些默认值,将它们声明为私有而不实现它们。
但是从我在网上看到的情况来看,List 类负责节点的复制。真的是这样吗?如果是这样,为什么?
它负责复制节点,因为它支持复制(制作副本)整个列表(这意味着制作列表中每个节点的副本)。
您不需要支持复制节点,除非您支持复制整个列表。
你可以做的比复制sgi 的 slist的设计更糟糕——sgi 的模板库(“stl”)是 C++ 标准库部分的基础,它通常仍然(在技术上不正确;-)称为“stl”。不幸的是slist
没有成功(它的双重表亲list
OTOH确实成功了,并成为了std::list
)但我确实喜欢它。
如果您不想对有效负载类型和分配器进行模板化,我猜可以对它们进行硬编码;但要保留的关键点是“节点”是一个内部实现细节——你只公开容器类型,具有所有好的、规范的方面(当然负载类型必须是已知的——模板化并不难,顺便说一句;-),并且您在 .h 中将“节点”设为一个不透明的类(它只包含一个class node;
, 和指向它的指针class slist
)。
如果你有一个单链表:
A1 -> B1 -> C1
并且您编写了自己的复制构造函数,然后调用内部 Node* 成员上的复制构造函数,然后您将得到:
A1 -> B1 -> C1
A2 -> B2 -> C2
您不应该做的是调用不会执行级联复制的隐式生成的复制构造函数,您将得到的是:
A2
|
v
A1 -> B1 -> C1
因此,要么编写自己的复制构造函数来进行深度复制,要么定义一个实现无操作的私有复制构造函数。
顺便说一句,std::list 实现了双向链表并实现了深拷贝语义。