阅读量:0
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 cur prev->_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 Iterator iterator begin() { return _pHead->_pNext; } iterator end() { return _pHead; } const_iterator begin() const { return _pHead->_pNext; } const_iterator end() const { return _pHead; } /// // List Capacity size_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 Access T& 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 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()); } // 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { Node* cur = pos._pNode; Node* newnode = new Node(val); Node* prev = cur->_pPre; // prev newnode cur prev->_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模拟实现》的学习就先到这里，如果有什么问题，还请指教指教，希望本篇文章能够对你有所帮助，我们下一篇见！！！
如你喜欢，点点赞就是对我的支持，感谢感谢！！！
