通用双向链表复制构造函数效率和联动
Generic doubly linked list copy constructor efficiency and linkage
我在实施以下两个 构造函数 时遇到问题：
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、Prev、Next Prev 和最终连接在一起的理解，我完全是个新手。所以，我不确定为什么上面的方法不起作用，我想问问是否有人知道这个并且可以在这里提供帮助。
Link.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);
}
};
List.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 是没有意义的（重点是获得 compile-time 多态性，这意味着 static_cast 来自 Link<T> 到 T （这是 Link<T> 的 child）应该总是安全的，如果不是（因为你的 _head 可能是 [= 类型的占位符13=]，不是 T?) 的实例，这是因为您编写的代码错误地同等对待它们。我可能建议重构为三个组件：
T - 用户选择的类型，不需要从任何给定的 class 继承，目前您使用奇怪的重复模板模式需要它从 Link<T>[ 继承=132=]
Link<T> - 没有关联值的链表的正向和反向链接元素的柏拉图理想（仅用于 _head），其中 _prev 和 _next 是指向 Link<T> 的指针，除了指向 _head 的指针外，它始终指向 Node<T>s.Node<T> - Link<T> 的 child class 添加一个 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 帮助程序 classes，现在 Link 必须是你的一部分public API), 避免了更多 API publicly visible 带来的很多 back-compat 限制
其次，您的代码非常有效，只是效率低下（通过间接为每个新元素设置四个指针，而您可以为每个元素设置两个指针，最后再设置两个指针以建立 List不变）。它仍然是一个 O(n) 复制操作，而不是 Schlemiel the Painter 算法所涉及的 O(n**2) 操作。
除此之外，按照您的说法，其他一切都有效，编写最高效的复制构造函数所需要做的就是：
以指向当前元素 (_head) 的指针开始，我将其称为 current_tail（因为在复制的每个阶段，它都是到目前为止的列表，如果没有找到其他元素，它将是真正的尾巴）
对于从 other 复制的每个新元素：
- 将其
_prev设置为current_tail（因为current_tail是List的当前尾部，创建反向链接）
- 将
current_tail 的 _next 设置为新元素（创建正向链接）
- 将
current_tail 设置为新元素（因为现在它们已完全相互链接；我们根本不需要 previous）
当您按照第 2 步复制所有内容后，修复循环，将最后一个元素绑定到 _head 和 vice-versa.
最终结果比你写的更简单（因为你根本不需要 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 的怪异现象（并将其以不同的类型存储在不同的地方），但除此之外就是这样了）。
瞧，每个循环只有两次使用间接变量（都是写入；所有加载都来自本地）而不是五次（四次写入，一次读取；每个对 _prev 的引用都是隐式间接使用 this->_prev) 当你重复 push_back 时参与。
为了加分，给自己写一个swap帮手（使用the copy-and-swap idiom），其实只需要改变四项（_head的_next和_prev交换每个List的所有节点，尾元素的_next，当前头元素的_prev指向的_head新拥有的 List)，以及大约六行简单的样板代码将为您提供廉价、高效且安全的移动构造函数和赋值运算符。
我在实施以下两个 构造函数 时遇到问题：
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、Prev、Next Prev 和最终连接在一起的理解，我完全是个新手。所以，我不确定为什么上面的方法不起作用，我想问问是否有人知道这个并且可以在这里提供帮助。
Link.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);
}
};
List.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 是没有意义的（重点是获得 compile-time 多态性，这意味着 static_cast 来自 Link<T> 到 T （这是 Link<T> 的 child）应该总是安全的，如果不是（因为你的 _head 可能是 [= 类型的占位符13=]，不是 T?) 的实例，这是因为您编写的代码错误地同等对待它们。我可能建议重构为三个组件：
T- 用户选择的类型，不需要从任何给定的 class 继承，目前您使用奇怪的重复模板模式需要它从Link<T>[ 继承=132=]Link<T>- 没有关联值的链表的正向和反向链接元素的柏拉图理想（仅用于_head），其中_prev和_next是指向Link<T>的指针，除了指向_head的指针外，它始终指向Node<T>s.Node<T>-Link<T>的 child class 添加一个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>的子class类型
您还可以获得以下额外好处：
- 隐藏更多实现（
Link和Node可以是private帮助程序 classes，现在Link必须是你的一部分public API), 避免了更多 API publicly visible 带来的很多 back-compat 限制
其次，您的代码非常有效，只是效率低下（通过间接为每个新元素设置四个指针，而您可以为每个元素设置两个指针，最后再设置两个指针以建立 List不变）。它仍然是一个 O(n) 复制操作，而不是 Schlemiel the Painter 算法所涉及的 O(n**2) 操作。
除此之外，按照您的说法，其他一切都有效，编写最高效的复制构造函数所需要做的就是：
以指向当前元素 (
_head) 的指针开始，我将其称为current_tail（因为在复制的每个阶段，它都是到目前为止的列表，如果没有找到其他元素，它将是真正的尾巴）对于从
other复制的每个新元素：- 将其
_prev设置为current_tail（因为current_tail是List的当前尾部，创建反向链接） - 将
current_tail的_next设置为新元素（创建正向链接） - 将
current_tail设置为新元素（因为现在它们已完全相互链接；我们根本不需要previous）
- 将其
当您按照第 2 步复制所有内容后，修复循环，将最后一个元素绑定到
_head和 vice-versa.
最终结果比你写的更简单（因为你根本不需要 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 的怪异现象（并将其以不同的类型存储在不同的地方），但除此之外就是这样了）。
瞧，每个循环只有两次使用间接变量（都是写入；所有加载都来自本地）而不是五次（四次写入，一次读取；每个对 _prev 的引用都是隐式间接使用 this->_prev) 当你重复 push_back 时参与。
为了加分，给自己写一个swap帮手（使用the copy-and-swap idiom），其实只需要改变四项（_head的_next和_prev交换每个List的所有节点，尾元素的_next，当前头元素的_prev指向的_head新拥有的 List)，以及大约六行简单的样板代码将为您提供廉价、高效且安全的移动构造函数和赋值运算符。