泛型双链表复制构造函数的效率和链接

我在实现以下两个构造函数时遇到问题：

List(const List& other)
~List()

最初，复制构造函数被写成：

for (auto current = other._head._next; current != &other._head; current = current->_prev){
push_back(static_cast<T*>(current));
}

以上被认为是无效和低效。所以，我试着这样重写：

for (auto ptr = other._head._next; ptr != &other._head; ptr = ptr->_next)
{
T* item = new T(*dynamic_cast<T*>(ptr)));
Link<T>* current = &_head;
Link<T>* previous = &_head;
current->_next = item;
previous = current;
/*

// link to new head
_head._next = other._head._next;
_head._prev = other._head._prev;
// Link prev och next to correct head
_head._next->_prev = &_head;
_head._prev->_next = &_head;

*/
}

然而，我是一个完全的新手，了解如何在这个复制构造函数和析构函数的上下文中正确地将Next、Previ、Next Previ以及最终连接在一起。所以，我不确定为什么以上不起作用，我想问是否有人知道这一点，并可以在这里提供帮助。

链接.hpp

template<class T>
class Link {
template<class> friend class List;
Link* _next, * _prev;
public:
Link() : _next(this), _prev(this) {}
virtual ~Link() {}
T* next() const { return dynamic_cast<T*>(_next); }
T* prev() const { return dynamic_cast<T*>(_prev); }
T* insert_after(T* in)
{
in->_next = this;
in->_prev = m_prev;
_prev->_next = in;
_prev = in;
return in;
}
T* insert_before(T* in)
{
return _prev->insert_after(in);
}
T* remove()
{
_prev->_next = _next;
_next->_prev = _prev;
return dynamic_cast<T*>(this);
}
void splice_after(Link* f, Link* l)
{
if (f != l){
f->_prev->_next = l->_next;
last->_next->_prev = f->_prev;
f->_prev = this;
l->_next = this->_next;
_next->_prev = l;
_next = f;
}
}
void splice_before(Link* f, Link* l)
{
m_prev->splice_after(f, l);
}
T* erase_first()
{
Link* tmp = _next;
_next = _next->_next;
_next->_prev = this;
return static_cast<T*>(tmp);
}
T* erase_last() {
Link* tmp = _prev;
_prev = _prev->_prev;
_prev->_next = this;
return static_cast<T*>(tmp);
}
};

列表.hpp:

#include <string.h>
template<class T> 
class List {
template<class X> class ListIter {
template<class> friend class List;
Link<T>* _ptr;
public:
// Typedefs
typedef std::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef std::remove_const_t<X>  value_type;
typedef X* pointer;
typedef X& reference;
public:
ListIter() : _ptr{ nullptr } {}
ListIter(Link<T>* ptr) : _ptr{ ptr } {}
ListIter(const ListIter& other) : _ptr{other._ptr} {}
ListIter& operator=(const ListIter& other) 
{
_ptr = other._ptr;
return *this;
}
X& operator*() { return *dynamic_cast<T*>(_ptr); }
X* operator->() { return dynamic_cast<T*>(_ptr); }
ListIter& operator++() { _ptr = static_cast<T*>(_ptr->_next); return *this; }
ListIter& operator--(){ _ptr = static_cast<T*>(_ptr->_prev); return *this; }
ListIter operator++(int) { auto r(*this); operator++(); return r; }
ListIter operator--(int){ auto r(*this); operator--(); return r; }
difference_type operator-(const ListIter& other) {
return (_ptr - other._ptr);
}
friend auto operator<=>(const ListIter& lhs, const ListIter& rhs)
{
if ((lhs._ptr - rhs._ptr) < 0)
return std::strong_ordering::less;
else if ((lhs._ptr - rhs._ptr) > 0)
return std::strong_ordering::greater;
return std::strong_ordering::equivalent;
}
friend bool operator==(const ListIter& lhs, const ListIter& rhs)
{
return (lhs <=> rhs) == 0;
}
};
Link<T> _head;
public:
using iterator = ListIter<T>;
using const_iterator = ListIter<const T>;
List() 
{
_head._next = &_head;
_head._prev = &_head;
}

List(const List& other) // Problem here, does not work, not sure how to get this solved.
{
for (auto ptr = other._head._next; ptr != &other._head; ptr = ptr->_next)
{
T* item = new T(*dynamic_cast<T*>(ptr)));
Link<T>* current = &_head;
Link<T>* previous = &_head;
current->_next = item;
previous = current;
/*

// link to new head
_head._next = other._head._next;
_head._prev = other._head._prev;
// Link prev och next to correct head
_head._next->_prev = &_head;
_head._prev->_next = &_head;

*/
}
}

List(const char* other)
{
for (size_t i = 0; i < strlen(other); ++i)
_head.insert_after(new T(other[i]));
}
~List()
{
while (_head._next != &_head)
{
pop_front();  // This isn't efficient. 
}
}
T* pop_front() 
{
return _head.erase_first();
}

T* pop_back() 
{
return _head.erase_last();
}
void push_front(T* node) { _head.insert_before(node);}
void push_back(T* node) { _head.insert_after(node);}
};

首先：我认为这里的设计是个糟糕的主意；看起来你在使用奇怪的重复模板模式，但如果是这样，依赖dynamic_cast是毫无意义的(重点是获得编译时多态性，这意味着从Link<T>到T的static_cast(它是Link<T>的子级)应该总是安全的，如果不是(因为你的_head可能是Link<T>类型的占位符，而不是T的实例？)，这是因为您编写的代码错误地将它们等同对待。我可能建议重构为三个组件：

T-用户选择的类型，不需要从任何给定的类继承，而当前使用奇怪的重复模板模式需要从Link<T>继承
Link<T>-链表的正向和反向链接元素的柏拉图式理想，没有关联值(仅用于_head)，其中_prev和_next是指向Link<T>的指针，除了指向_head的指针外，它们总是指向Node<T>s
Node<T>-Link<T>的一个子类，它添加了一个T数据成员，几乎没有其他成员(为了避免开销，几乎所有与T本身无关的行为都将在Link<T>上定义为非virtually)

有了这三种方法，再加上适当的emplace*方法，您就拥有了与当前相同的功能：

_head可以是纯Link<T>(不需要存储伪T，也不需要使用来定义默认构造函数)
所有其他元素都是Node<T>，并且具有与当前Link<T>相同的开销(T的一个实例加上两个指针)
T可以是任意类型(emplace*方法意味着T的构建可以推迟到创建Node<T>的那一刻，不需要复制或移动T)

其中#3是隐形改进，我将重复一遍：

T可以是任意类型，而不仅仅是Link<T>的子类

，您可以获得以下额外好处：

隐藏更多的实现(Link和Node可以是private助手类，其中Link现在必须是公共API的一部分)，避免了更多API公开可见时附带的大量后台约束

其次，您的代码非常有效，只是效率稍低(通过间接方式为每个新元素设置四个指针，而您可以为每个元素设置两个指针，最后再设置两个来建立List不变量)。这仍然是一个O(n)复制操作，而不是画家算法中的Schlemiel所涉及的O(n**2)操作。

除此之外，如果你相信其他一切都有效，那么你所需要做的就是编写一个最高效的复制构造函数：

从指向当前元素(_head)的指针开始，我将其称为current_tail(因为在复制的每个阶段，它都是迄今为止列表的逻辑尾部，如果没有找到其他元素，它将是真正的尾部)
对于从other:复制的每个新元素
1. 将其_prev设置为current_tail(因为current_tail是List的当前尾部，创建反向链接)
2. 将current_tail的_next设置为新元素(创建正向链接)
3. 将current_tail设置为新元素(因为现在它们已经完全链接在一起了；我们根本不需要previous)
按照步骤2复制完所有内容后，修复循环，将最后一个元素绑定到_head，反之亦然。

最终结果比您所写的更简单(因为您根本不需要previous指针)：

List(const List& other) // Problem here, does not work, not sure how to get this solved.
{
Link<T>* current_tail = &_head;   // 1. The tail of an empty list points to _head
for (auto ptr = other._head._next; ptr != &other._head; ptr = ptr->_next)
{
T* item = new T(*dynamic_cast<T*>(ptr)));
// We have validly forward linked list at each loop, so adding new element just means:
item->_prev = current_tail ;  // 2.1. Telling it the prior tail comes before it
current_tail->_next = item;   // 2.2. Telling the prior tail the new item comes after it
current_tail = item;          // 2.3. Update notion of current tail
}
current_tail->_next = &_head;     // 3. Real tail's _next points to _head to indicate end of list
_head._prev = current_tail;       // _head._prev is logical pointer to tail element, fix it up

}

你可能需要在其中加入几个演员阵容来处理List<T>也是T的奇怪之处(并将其以不同的类型存储在不同的地方)，但除此之外就这样了)。

Voila，当您重复push_back时，每个循环只有两次使用间接变量(两次写入；所有加载都来自本地)，而不是五次(四次写入，一次读取；每次引用_prev都隐含地间接使用this->_prev)。

对于奖励积分，为自己编写一个swap助手(使用复制和交换习惯用法)，它实际上只需要更改四个项目(_head的_next和_prev交换每个List的所有节点，尾部元素的_next和当前头部元素的_prev指向新拥有的List的_head)，大约六行简单的样板将为您提供一个廉价、高效、安全的移动构造函数和赋值运算符。

相关内容

最新更新

热门标签：