hello，各位小伙伴，本篇文章跟大家一起學習《C++：list模擬實現》，感謝大家對我上一篇的支持，如有什么問題，還請多多指教 ！
如果本篇文章對你有幫助，還請各位點點贊！！！
話不多說，開始進入正題
🍁list的邏輯結構以及節點代碼
是一個雙指針帶頭鏈表，所以我選擇用一個結構體ListNode來維護節點，如下：
// List的節點類
template<class T>
struct ListNode
{ListNode(const T& val = T()):_val(val),_pPre(nullptr),_pNext(nullptr){}ListNode<T>* _pPre;// 指向前一個結點ListNode<T>* _pNext;// 指向后一個節點T _val;// 該結點的值
};
我對ListNode<T>改一個名字：Node：
typedef ListNode<T> Node;
typedef Node* PNode;
🍁list類
🍃私有成員變量_pHead和私有成員函數CreateHead()
private:void CreateHead()// 創建頭節點并且初始化{_pHead = new Node();_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}PNode _pHead;
🍃尾插函數和插入函數
尾插只是插入的其中一種方式，所以實現了插入函數，就能夠實現尾插函數。
插入思路圖解：在pos位置前插入值為val的節點
創建新節點值為value后；
使prev節點的_pNext指針指向newnode，newnode的節點的_pPre指向prev；
使cur節點的_pPre指針指向newnode，newnode的節點的_pNext指向cur；
最后返回iterator(newnode);
itearator為迭代器，后面會實現
- 插入
// 在pos位置前插入值為val的節點
iterator insert(iterator pos, const T& val)
{Node* cur = pos._pNode;Node* newnode = new Node(val);Node* prev = cur->_pPre;// prev newnode curprev->_pNext = newnode;newnode->_pPre = prev;newnode->_pNext = cur;cur->_pPre = newnode;return iterator(newnode);
}
- 尾插
void push_back(const T& val)
{insert(end(), val);
}
🍃構造函數
- 無參構造
list(const PNode& pHead = nullptr)
{CreateHead();/*_pHead = new Node();_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;*/
}
- 帶參構造（數值）
list(int n, const T& value = T())
{CreateHead();for (int i = 0; i < n; ++i)push_back(value);
}
- 帶參構造（迭代器）
template <class Iterator>
list(Iterator first, Iterator last)
{CreateHead();while (first != last){push_back(*first);++first;}
}
- 拷貝構造
list(const list<T>& l)
{CreateHead();// 復用帶參構造（迭代器）list<T> temp(l.cbegin(), l.cend());// 與*this的頭節點pHead交換指向swap(temp);
}
🍃析構函數
clear()為其中的成員函數，功能：清理list中的數據
~list()
{clear();delete _pHead;_pHead = nullptr;/*Node* cur = _pHead->_pNext;Node* tmp = cur->_pNext;while (cur != _pHead){delete cur;cur = tmp;tmp = tmp->_pNext;}tmp = cur = nullptr;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;*/
}
🍃迭代器模擬
邏輯上并不難，也許難理解于模板
//List的迭代器結構體
template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l){_pNode = l._pNode;}T& operator*(){assert(_pNode != _pNode->_pNext);return _pNode->_val;}T* operator->(){return &(*this);}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){PNode* tmp = _pNode;_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){PNode* tmp = _pNode;_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return !(*this != l);}PNode _pNode;
};
這段代碼定義了一個模板結構 ListIterator，用于表示List類的迭代器。讓我們來解釋模板聲明部分：
template<class T, class Ref, class Ptr>;
這一行是模板聲明，定義了一個模板類 ListIterator，它有三個模板參數：T、Ref 和 Ptr。讓我們逐個解釋這些參數的作用：
1.T: 這是一個模板參數，表示迭代器指向的元素類型。在使用 ListIterator 時，你需要提供實際的類型作為 T 的值。
2.Ref: 這也是一個模板參數，表示迭代器的引用類型。通常情況下，當你通過迭代器解引用（使用 * 運算符）時，你希望得到的是元素的引用類型。所以 Ref 通常被設定為 T&，表示引用類型為 T 的元素。
3.Ptr: 這是迭代器的指針類型。與 Ref 類似，當你通過迭代器解引用（使用 -> 運算符）時，你希望得到的是元素的指針類型。因此，通常情況下 Ptr 被設定為 T*，表示指針類型為 T 的元素。
通過將這些參數設定為模板參數，ListIterator 類可以適用于不同類型的元素，同時也可以提供不同的引用和指針類型。這樣做使得 ListIterator 類更加靈活，能夠適用于不同的使用場景。
- 封裝的意義
將迭代器的實現從 List 類中分離出來，有幾個重要的意義和優勢：
- 模塊化設計：通過將迭代器封裝為單獨的類，可以實現更模塊化的設計。這意味著 List 類的實現與迭代器的實現可以分開，每個類都專注于自己的職責。這樣的設計使得代碼更易于理解、維護和測試。
- 可重用性：通過將迭代器設計為獨立的類，可以在不同的容器類中重復使用相同的迭代器實現。例如，如果你有另一個類似于 List 的容器類，也需要迭代器來遍歷其中的元素，你可以直接重用相同的迭代器實現，而無需重新編寫。
- 靈活性：將迭代器設計為獨立的類使得它們的實現更加靈活。你可以在迭代器類中添加額外的功能或改變迭代器的行為，而不會影響到容器類的實現。這樣的設計使得容器和迭代器的職責分離，每個類可以獨立地演化和改進。
- 通用性：獨立的迭代器類可以設計成通用的，適用于多種容器類型。這意味著你可以為不同的容器類實現相同的迭代器接口，使得用戶在使用不同的容器時無需學習不同的迭代器接口，提高了代碼的一致性和可用性。
總的來說，將迭代器封裝為獨立的類使得代碼更加模塊化、可重用、靈活和通用，提高了代碼的可維護性、可擴展性和可讀性。
🍃list類中迭代器的使用
public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;
- begin()和end()
// List Iterator
iterator begin()
{return _pHead->_pNext;
}iterator end()
{return _pHead;
}const_iterator begin() const
{return _pHead->_pNext;
}const_iterator end() const
{return _pHead;
}
- erase
刪除pos位置的節點，返回該節點的下一個位置
iterator erase(iterator pos)
{assert(pos._pNode != _pHead);Node* Prev = pos._pNode->_pPre;Node* Next = pos._pNode->_pNext;delete pos._pNode;Prev->_pNext = Next;Next->_pPre = Prev;return iterator(Next);
}
🍃List Modify
void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T& val)
{ assert(!empty());insert(begin(), val);
}
void pop_front() { erase(begin()); }
🍁全部代碼
#pragma once
#include<assert.h>
#include<iostream>
using namespace std;namespace My_List
{// List的節點類template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPre(nullptr),_pNext(nullptr){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器類template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l){_pNode = l._pNode;}T& operator*(){assert(_pNode != _pNode->_pNext);return _pNode->_val;}T* operator->(){return &(*this);}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){PNode* tmp = _pNode;_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){PNode* tmp = _pNode;_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return !(*this != l);}PNode _pNode;};//list類template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:///// List的構造list(const PNode& pHead = nullptr){CreateHead();/*_pHead = new Node();_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;*/}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i)push_back(value);/*int cnt = 0;while (cnt < n){PNode _first = new Node(value);PNode tmp = _pHead->_pPre;tmp->_pNext = _first;_first->_pPre = tmp;_first->_pNext = _pHead;_pHead->_pPre = _first;++cnt;}*/}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}/*while (first != last){PNode _first = new Node(*first);PNode tmp = _pHead->_pPre;tmp->_pNext = _first;_first->_pPre = tmp;_first->_pNext = _pHead;_pHead->_pPre = _first;++first;}*/}list(const list<T>& l){CreateHead();list<T> temp(l.cbegin(), l.cend());swap(temp);/*iterator first = l._pHead->_pNext;iterator last = l._pHead;while (first != last){PNode _first = new Node(*first);PNode tmp = _pHead->_pPre;tmp->_pNext = _first;_first->_pPre = tmp;_first->_pNext = _pHead;_pHead->_pPre = _first;++first;}*/}list<T>& operator=(const list<T> l){CreateHead();swap(l);return *this;/*iterator first = l._pHead->_pNext;iterator last = l._pHead;while (first != last){PNode _first = new Node(*first);PNode tmp = _pHead->_pPre;tmp->_pNext = _first;_first->_pPre = tmp;_first->_pNext = _pHead;_pHead->_pPre = _first;++first;}return *this;*/}~list(){clear();delete _pHead;_pHead = nullptr;/*Node* cur = _pHead->_pNext;Node* tmp = cur->_pNext;while (cur != _pHead){delete cur;cur = tmp;tmp = tmp->_pNext;}tmp = cur = nullptr;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;*/}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin() const{return _pHead->_pNext;}const_iterator end() const{return _pHead;}///// List Capacitysize_t size()const{Node* cur = _pHead->_pNext;size_t cnt = 0;while (cur != _pHead){++cnt;cur = cur->_pNext;}return cnt;}bool empty()const{return size() == 0;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPre->_val;}const T& back()const{return _pHead->_pPre->_val;}// List Modifyvoid push_back(const T& val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T& val) { assert(!empty());insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值為val的節點iterator insert(iterator pos, const T& val){Node* cur = pos._pNode;Node* newnode = new Node(val);Node* prev = cur->_pPre;// prev newnode curprev->_pNext = newnode;newnode->_pPre = prev;newnode->_pNext = cur;cur->_pPre = newnode;return iterator(newnode);}// 刪除pos位置的節點，返回該節點的下一個位置iterator erase(iterator pos){assert(pos._pNode != _pHead);Node* Prev = pos._pNode->_pPre;Node* Next = pos._pNode->_pNext;delete pos._pNode;Prev->_pNext = Next;Next->_pPre = Prev;return iterator(Next);}void clear(){iterator cur = begin();while (cur != end()){cur = erase(cur);}_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}void swap(list<T>& l){/*list<T> tmp = l;l = *this;*this = tmp;*/PNode tmp = _pHead;_pHead = l._pHead;l._pHead = tmp;}private:void CreateHead(){_pHead = new Node();_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}PNode _pHead;};
};
你學會了嗎？
好啦，本章對于《C++：list模擬實現》的學習就先到這里，如果有什么問題，還請指教指教，希望本篇文章能夠對你有所幫助，我們下一篇見！！！
如你喜歡，點點贊就是對我的支持，感謝感謝！！！
-閉包、裝飾器)
