C++list類模擬實作
- list類的基本結構
- 結點類
- 成員變數
- 成員函式
- 迭代器類
- 成員函式
- 1、解參考運算子多載
- 2、箭頭運算子多載
- 3、迭代器前置++
- 4、迭代器后置++
- 5、迭代器的比較
- 鏈表類
- 成員變數
- 成員函式
- 1、建構式
- 2、拷貝構造
- 3、賦值多載
- 4、解構式
- 5、clear
- 6、begin（）、end（）
- 7、insert
- 8、erase
- 其他小型介面
list類的基本結構
xxxxSTL中list是一個雙向帶頭回圈鏈表，除了頭結點不存盤有效資訊外，其余node結點存盤有效資訊，同時，為了防止代碼冗余，對于存盤資訊型別不同的問題，將采用模板的方式解決，
xxxxlist需要創建3個類：結點類、迭代器類和鏈表類，
結點類
成員變數
xxxx就像C語言中鏈表的創建，C++的鏈表也需要構建一個類（類似于C的結構體）包含節點中資料資訊、下一節點地址和上一節點的地址三部分資訊，
結點類成員變數如下：
template<class T>
struct _list_node_
{
T _val; //存盤資料
_list_node_<T>* _next;
_list_node_<T>* _prev;
};
成員函式
xxxx分析我們需要寫的成員函式：發現只有建構式需要寫，因為在new新的結點時，會自動呼叫它的建構式，如果不寫就會產生隨機值，但是結點不會拷貝構造，不會賦值，并且節點的釋放是list控制，所以不需要寫拷貝構造、賦值運演算法多載和解構式，
結點類完整代碼如下：
解釋:由于結點類的成員變數需要被其他類直接訪問，所以要將成員變數設定成公有，所以直接用struct（默認內容為公有public），下面迭代器類同理
迭代器類
xxxx不同于string、vector兩種容器，list的迭代器并不是原生的指標，而是封裝結點指標成了一個類，
迭代器類代碼如下：
template<class T, class Ref, class Ptr>
struct _list_iterator_ //迭代器就是需要淺拷貝，不需要重新寫拷貝構造或者復制
{ //解構式：迭代器只是存一下指標，指標指向的結點由鏈表管理，不需要迭代器去釋放空間
typedef _list_node_<T> node;
typedef _list_iterator_<T, Ref, Ptr> self;
_list_iterator_(node* pnode = nullptr)
:_pnode(pnode)
{}
Ref operator*() //不加參考就是回傳一個臨時變數，不可更改具有常屬性
{
return _pnode->_val;
}
Ptr operator->()
{
return &_pnode->_val; //it->->_year it->獲得T*，T*->獲得T類中的內容
}
bool operator==(const self& s) const
{
return _pnode == s._pnode;
}
bool operator!=(const self& s) const
{
return _pnode != s._pnode;
}
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self operator++(int) //回傳的是臨時物件，所以不回傳參考
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
self operator--(int) //回傳的是臨時物件，所以不回傳參考
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
//成員變數
node* _pnode;
};
xxxx問題一：為什么要這樣做呢？因為由于list并不是序列型容器，而是一個一個結點通過地址連接起來的，而為了保證所有容器迭代器使用方法的統一性，都要有對迭代器++/–/*等操作，++/–會直接訪問上一個結點或者下一個結點的資料；解參考操作則會直接訪問當前結點存盤的資料，如果我們使用原生指標（結點的指標），則無法達到迭代器所要求的結果，因此，我們需要將結點的指標包裝成類，通過運算子多載改變它的行為，達到這樣的目的，
xxxx問題二：為什么迭代器類不寫拷貝構造、賦值多載和解構式呢？因為迭代器在拷貝構造和賦值的時候，就是希望做到淺拷貝，就是將值進行拷貝，讓他們指向同一塊空間，而不是將指向的內容進行深拷貝，因此編譯器自動生成的淺拷貝就夠了，其次，由于迭代器并沒有自己開辟空間，因此無空間的釋放，所以不需要解構式，結點的釋放是鏈表的任務
xxxx問題三:迭代器的模板中，為何需要三個模板引數？三個模板引數分別代表什么意思？，我們都知道，list的迭代器不同于string和vector的原生指標型別的迭代器，他是一個類，對于原生指標來說，被const修飾和不被const修飾的兩種指標就是兩種型別，因此對于正常的思維來說，迭代器就應該實作成兩種類，一個是iterator，一個是const_iterator，兩種分開寫，因為如果還是想string、vector一樣單純把const和非const兩種迭代器看作一種，在list類里typedef成const和非const型別的迭代器，這樣就會導致const無效，還是可以更改內容，因為，迭代器仍然是非const，你只是把迭代器的型別名改成了const_iterator，并沒有改變迭代器的實質，所以當呼叫解參考的運算子多載時，還是會回傳T&，還是可以更改，所以第一種解決方法就是將iterator和const_iterator兩種迭代器型別分成兩個類來寫，這樣const修飾的鏈表就會去呼叫const_iterator的類，非const鏈表就會呼叫iterator的類，但是這樣就會造成大量代碼的冗余，
xxxx于是，就出現了利用模板的方法，來區分兩種迭代器，
xxxx第一個引數模板class T：代表的是資料的型別，
xxxx第二個引數模板class Ref：代表的是結點中資料的參考，
xxxx第三個引數模板class Ptr：代表的是結點中資料的指標，
具體如下圖：
如果還是有不理解可以通過下面成員函式的決議再次加深理解，
成員函式
1、解參考運算子多載
Ref operator*() //不加參考就是回傳一個臨時變數，不可更改具有常屬性
{
return _pnode->_val;
}
xxxx對于string、vector迭代器是原生指標的容器來說，他們的迭代器就是資料的地址，因此解參考可以直接拿到資料，而list并不是，所以需要運算子多載來改變它的行為，可以通過對迭代器解參考直接獲取資料，所以return _pnode->val
xxxx同時，對于回傳值，我們需要回傳的是一個參考，否則，回傳的就是一個臨時變數，具有常屬性，不可改變，并且，如果迭代器是const_iterator所以它的Ref就是const T&就不能對資料進行寫，只能讀，const型別迭代器回傳的是T&，就可讀可寫了，
2、箭頭運算子多載
Ptr operator->()
{
return &_pnode->val;
}
xxxx若迭代器為原生指標，則it->就可以直接獲取it的內容，但是list的迭代器不可以，所以就需要運算子多載改變行為，
xxxx值得注意的是
3、迭代器前置++
typedef _list_iterator_<class T, class Ref, class Ptr> self
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
xxxxself是一個型別，回傳的就是迭代器自己，self是typedef出來的，前置–類似就是將_next換成_prev，
4、迭代器后置++
self operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
xxxx因為回傳的是tmp，是臨時變數，所以不能回傳參考，因為回傳的值是改變之前的值，所以要報錯原來的值，回傳再將*this改變，后置–類似，就是將_next換成_prev，
5、迭代器的比較
xxxx迭代器的比較比較簡單，所以就不細說了，
鏈表類
template<class T>
class list
{
typedef _list_node_<T> node;
public:
typedef _list_iterator_<T, T&, T*> iterator;
typedef _list_iterator_<T, const T&, const T*> const_iterator;
list()
{
_head = (node*)malloc(sizeof(node));
_head->_next = _head;
_head->_prev = _head;
}
list(const list<T>& lt)
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
for (const T& e:lt)
{
push_back(e);
}
}
list<T>& operator=(list<T> lt) //現代寫法
{
swap(_head, lt._head);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
iterator begin()
{
return _head->_next;
}
const_iterator begin() const
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator end() const
{
return _head;
}
void push_back(const T& x)
{
node* tail = _head->_prev;
node* newnode = new node(x); //呼叫node的建構式
tail->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;
newnode->_prev = tail;
}
void insert(iterator pos, const T& x)
{
assert(pos._pnode);
node* cur = pos._pnode;
node* prev = cur->_prev;
node* newnode = new node(x);
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
}
iterator erase(iterator pos)
{
assert(pos._pnode);
assert(pos != end());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
delete pos._pnode;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
it++;
sz++;
}
return sz;
}
bool empty()
{
return begin() == end();
}
private:
node* _head;
};
成員變數
xxxx成員變數就是一個頭結點，同時還需要typedef出結點、const_iterator和iterator
成員函式
1、建構式
list()
{
_head = (node*)malloc(sizeof(node));
_head->_next = _head;
_head->_prev = _head;
}
xxxx注意_head需要使用malloc來開辟空間，因為頭結點不需要存盤資料，所以不需要初始化，如果用new的話存在一個問題，就是如果出現資料型別T也是list，那么用new開辟頭結點空間時，就會自動迪呼叫建構式初始化，初始化就要呼叫建構式，呼叫建構式就要new并且初始化，就會出現一個無限回圈，所以就需要malloc來開辟空間，
xxxx對于空鏈表來說，應該是頭結點的next和prev都指向自己，
2、拷貝構造
list(const list<T>& lt)
{
_head = (node*)malloc(sizeof(node));
_head->_next = _head;
_head->_prev = _head;
for(const auto& e : lt)
{
push_back(e);
}
}
xxxx可以復用代碼，使用push_back，但是push_back之前，必須是規范的空鏈表，必須初始化，
3、賦值多載
list<T>& operator=(const list<T> lt)
{
swap(_head, lt._head);
return *this;
}
xxxx這是一種現代寫法，很簡單，先利用拷貝構造，構造出一個完全相同的，這樣把*this的_head與拷貝構造出來的_head一換，這樣就直接把拷貝構造出來的內容的給了this
4、解構式
~list()
{
clear();
delete _head;
_head = nullptr;
}
xxxx同樣的道理，也是復用，先用clear，將鏈表置空（所有的結點都被釋放掉），然后再釋放掉頭結點，
5、clear
void clear()
{
iterator it = begin();
while(it != end())
{
it = erase(it);
}
}
xxxx挨個釋放所有結點就是復用erase，同時，因為釋放結點后，就無法找到該結點后的結點，所以it要接受erase的回傳值（即：被釋放結點后結點的迭代器）
6、begin（）、end（）
iterator begin()
{
return _head->_next;
}
const_iterator begin() const
{
return _head->_next;
}
iterator end()
{
return _head->_prev;
}
const_iterator end() const
{
return _head->_prev;
}
7、insert
void insert(iterator pos, const T&x)
{
assert(pos._pnode);
node* cur = pos._pnode;
node* prev = cur->_prev;
node* newnode = new node(x);
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
}
xxxxprev、cur、next三個結點的鏈接關系搞清楚即可，由于是帶頭雙向回圈，所以，不需要考慮結點之間連接的順序，也不需要考慮多種情況，需要考慮的就是pos除是否為空，空的位置不能操作，斷言一下，提高安全性，
8、erase
iterator erase(iterator pos)
{
assert(pos._pnode);
assert(pos != end());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
delete pos._pnode;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
xxxx洗掉后，為了防止迭代器失效，所以要把下一位置的的迭代器當做回傳值回傳，這是STL中容器的普遍做法，
其他小型介面
xxxx其余的介面都比較比較簡單，直接看代碼就能明白，代碼在上面的list類完整版部分，
xxxx
xxxx
xxxx
xxxx
xxxx如果讀者還有任何疑問，可以評論留言，或者私信我，我們一起探討，一起進步
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296879.html
標籤：其他