我在實作以下兩個建構式時遇到問題：
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 和 finally 連接。所以，我不確定為什么上述方法不起作用，我想問是否有人知道這一點并可以在這里提供幫助。
鏈接.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);}
};
uj5u.com熱心網友回復：
首先：我認為這里的設計是一個糟糕的想法；看起來你正在使用奇怪的重復模板模式，但dynamic_cast如果是這樣的話，依賴是沒有意義的（重點是獲得編譯時多型性，這意味著static_castfrom Link<T>to T（它是 的孩子Link<T>）應該始終是安全的，并且如果不是（因為你可能_head是 type 的占位符Link<T>，而不是T? 的實體），那是因為您撰寫的代碼錯誤地將它們等同對待。我可能建議將其重構為三個組件：
T- 用戶選擇的型別，不需要從任何給定的類繼承，目前您使用奇怪的重復模板模式需要它繼承自Link<T>Link<T>- 沒有關聯值的鏈表的正向和反向鏈接元素的柏拉圖式理想（僅用于_head），其中_prev和_next是指向Link<T>該元素的指標，除了指向 的指標之外_head，始終指向Node<T>s。Node<T>- 它的子類Link<T>添加了一個T資料成員，幾乎沒有其他內容（為了避免開銷，幾乎所有與自身無關的行為都T將被定義為 non -virtually onLink<T>）
使用這三個，再加上適當的emplace*方法，您將擁有與當前相同的功能：
_head可以是普通的Link<T>（不需要存盤 dummyT，也不需要使用定義默認建構式）- 所有其他元素都是
Node<T>, 并且具有與當前相同的開銷Link<T>（一個實體T加兩個指標） T可以是任意型別（emplace*方法意味著 a 的構造T可以推遲到Node<T>創建的那一刻，不需要復制或移動T）
其中#3 是我將重復的隱身改進：
T可以是任意型別，而不僅僅是Link<T>
您還可以獲得以下額外好處：
- 隱藏更多的實作（
Link并且Node可以是private幫助類，現在Link必須是公共 API 的一部分），避免更多公開可見的 API 帶來的許多反向兼容約束
其次，您的代碼非常有效，只是效率稍低（通過每個新元素的間接設定四個指標，而每個元素只能設定兩個，最后再設定兩個以建立List不變數）。它仍然是一個O(n)復制操作，而不是O(n**2)Schlemiel the Painter 的演算法所涉及的操作。
除此之外，相信其他一切都有效，撰寫一個最有效的復制建構式所需要做的就是：
從指向當前元素 ( ) 的指標開始
_head，我將呼叫它current_tail（因為在復制的每個階段，它都是迄今為止串列的邏輯尾部，如果沒有找到其他元素，它將是真正的尾部）對于從 復制的每個新元素
other：- 將其設定
_prev為current_tail（因為current_tail是 的當前尾部List，創建反向鏈接） - 將
current_tail's設定_next為新元素（創建前向鏈接） - 設定
current_tail為新元素（因為現在它們完全相互鏈接；我們根本不需要 aprevious）
- 將其設定
當您按照步驟 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（并將其以不同的型別存盤在不同的地方），但除此之外就是這樣）。
瞧，當你重復時，每個回圈只有兩次使用間接變數（兩次寫入；所有負載都來自本地），而不是五次（四次寫入，一次讀取；每次參考_prev都是隱式間接使用）。this->_prevpush_back
為了加分，給自己寫一個swap助手（使用復制和交換習語），它實際上只需要更改四個專案 (并交換每個節點的所有節點，_head尾部元素的和當前的head 元素指向新擁有的)，大約六行簡單的樣板檔案將為您提供廉價、高效和安全的移動建構式和賦值運算子。_next_prevList_next_prev_headList
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/465306.html
下一篇：為什么這個代碼片段有效？lambda的引數應該是一個左值參考，而`std::bind`傳遞一個右值（即`std::move(ptr)`）給它