目录
后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！ ——By 作者：新晓·故知
1. list的模拟实现
1.1 模拟实现list
list的模拟实现主要对常用的函数接口：构造函数、拷贝构造函数、析构函数、赋值重载函数、list迭代器、push_back、pop_back、insert、erase、pop_back、pop_front等。
重点学习const_iterator的实现，参考STL源码文档进行学习。
对list迭代器失效问题与vector迭代器失效问题进行对比、解决。
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。namespace bite { // List的节点类 template<class T> struct ListNode { ListNode(const T& val = T()) : _pPre(nullptr) , _pNext(nullptr) , _val(val) {} ListNode<T>* _pPre; ListNode<T>* _pNext; T _val; }; /* List 的迭代器 迭代器有两种实现方式，具体应根据容器底层数据结构实现： 1. 原生态指针，比如：vector 2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下 方法： 1. 指针可以解引用，迭代器的类中必须重载operator*() 2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->() 3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int) 至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可 以向前 移动，所以需要重载，如果是forward_list就不需要重载-- 4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=() */ template<class T, class Ref, class Ptr> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; public: ListIterator(PNode pNode = nullptr) : _pNode(pNode) {} ListIterator(const Self& l) : _pNode(l._pNode) {} T& operator*() { return _pNode->_val; } T* operator->() { return &(operator*()); } Self& operator++() { _pNode = _pNode->_pNext; return *this; } Self operator++(int) { Self temp(*this); _pNode = _pNode->_pNext; return temp; } Self& operator--(); Self& operator--(int); bool operator!=(const Self& l) { return _pNode != l._pNode; } bool operator==(const Self& l) { return _pNode != l._pNode; } PNode _pNode; }; 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() { CreateHead(); } 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(); // 用l中的元素构造临时的temp,然后与当前对象交换 list<T> temp(l.cbegin(), l.cend()); this->swap(temp); } list<T>& operator=(const list<T> l) { this->swap(l); return *this; } ~list() { clear(); delete _pHead; _pHead = nullptr; } /// // List Iterator iterator begin() { return iterator(_pHead->_pNext); } iterator end() { return iterator(_pHead); } const_iterator begin() { return const_iterator(_pHead->_pNext); } const_iterator end() { return const_iterator(_pHead); } /// // List Capacity size_t size()const; bool empty()const; // List Access T& front(); const T& front()const; T& back(); const T& back()const; // List Modify void push_back(const T& val) { insert(begin(), val); } void pop_back() { erase(--end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { erase(begin()); } // 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { PNode pNewNode = new Node(val); PNode pCur = pos._pNode; // 先将新节点插入 pNewNode->_pPre = pCur->_pPre; pNewNode->_pNext = pCur; pNewNode->_pPre->_pNext = pNewNode; pCur->_pPre = pNewNode; return iterator(pNewNode); } // 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos) { // 找到待删除的节点 PNode pDel = pos._pNode; PNode pRet = pDel->_pNext; // 将该节点从链表中拆下来并删除 pDel->_pPre->_pNext = pDel->_pNext; pDel->_pNext->_pPre = pDel->_pPre; delete pDel; return iterator(pRet); } void clear(); void swap(List<T>& l); private: void CreateHead() { _pHead = new Node; _pHead->_pPre = _pHead; _pHead->_pNext = _pHead; } private: PNode _pHead; }; }
1.2 对模拟的bite::list进行测试
// 正向打印链表 template<class T>void PrintList(const bite::list<T>& l) { auto it = l.cbegin(); while (it != l.cend()) { cout << *it << " "; ++it; } cout << endl; } // 测试List的构造 void TestList1() { bite::list<int> l1; bite::list<int> l2(10, 5); PrintList(l2); int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; bite::list<int> l3(array, array + sizeof(array) / sizeof(array[0])); PrintList(l3); bite::list<int> l4(l3); PrintList(l4); l1 = l4; PrintList(l1); PrintListReverse(l1); } // PushBack()/PopBack()/PushFront()/PopFront() void TestList2() { // 测试PushBack与PopBack bite::list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); PrintList(l); l.pop_back(); l.pop_back(); PrintList(l); l.pop_back(); cout << l.size() << endl; // 测试PushFront与PopFront l.push_front(1); l.push_front(2); l.push_front(3); PrintList(l); l.pop_front(); l.pop_front(); PrintList(l); l.pop_front(); cout << l.size() << endl; } void TestList3() { int array[] = { 1, 2, 3, 4, 5 }; bite::list<int> l(array, array + sizeof(array) / sizeof(array[0])); auto pos = l.begin(); l.insert(l.begin(), 0); PrintList(l); ++pos; l.insert(pos, 2); PrintList(l); l.erase(l.begin()); l.erase(pos); PrintList(l); // pos指向的节点已经被删除，pos迭代器失效 cout << *pos << endl; auto it = l.begin(); while (it != l.end()) { it = l.erase(it); } cout << l.size() << endl; }
2. list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
3.list模拟实现源码：
（1）list.h：
#pragma once #include<iostream> #include<list> #include<cassert> using namespace std; //自定义命名空间，防止与库里的冲突 namespace my { template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _data; list_node(const T& val) //或A:给个缺省值list_node(const T& val=T()) :_next(nullptr) ,_prev(nullptr) ,_data(val) {} }; template<class T,class Ref,class Ptr> //多个模板参数 struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T,Ref,Ptr> self; Node* _node; __list_iterator(Node*node) :_node(node) {} Ref operator*() { return _node->_data; } self& operator++() //默认为前置++ { _node = _node->_next; return *this; } self& operator++(int) //后置++ { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() //前置-- { _node = _node->_prev; return *this; } self& operator--(int) //后置-- { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self& it) { return _node!= it._node; } bool operator==(const self& it) { return _node == it._node; } //"->"重载 Ptr operator->() { return &(operator*());//等价于return &_node->_data; } }; 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; //迭代器 iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } //const迭代器:多模板参数，附用普通迭代器 const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } //构造函数 list() { _head = new Node(T()); //或A:_head = new Node(); A对应上面的A语句 _head->_next = _head; _head->_prev = _head; } //析构函数 ~list() { clear(); delete _head; _head = nullptr; } //lt2(lt1) //构造函数传统写法 //list(const list<T>& lt) //{ // _head = new Node(T()); //或A:_head = new Node(); A对应上面的A语句 // _head->_next = _head; // _head->_prev = _head; // for (auto e : lt) // { // push_back(e); // } //} //初始化 void empty_init() { _head = new Node(T()); //或A:_head = new Node(); A对应上面的A语句 _head->_next = _head; _head->_prev = _head; } template <class InputIterator> list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } //交换 void swap(list<T>& lt) { std::swap(_head, lt._head); } //构造函数——现代写法 list(const list<T>& lt) { empty_init(); list<T> tmp(lt.begin(), lt.end()); swap(tmp); } //赋值重载——现代写法 list<T>& operator=(list<T> lt) { swap(lt); return *this; } void clear() //clear清理数据，结构还在 { iterator it = begin(); while (it != end()) { it = erase(it); } } //尾插 void push_back(const T& x) { /*Node* tail = _head->_prev; Node* newnode = new Node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ //附用insert insert(end(), x); } //头插 void push_front(const T& x) { insert(begin(), x); } //insert插入在pos位置之前 iterator insert(iterator pos, const T& x) { Node* newNode = new Node(x); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newNode; newNode->_prev = prev; newNode->_next = cur; cur->_prev = newNode; return iterator(newNode); } //尾删 void pop_back() { erase(--end()); } //头删 void pop_front() { erase(begin()); } //删除 iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); } //总结：list::insert不存在迭代器失效问题 //list::erase存在野指针导致的迭代器失效 private: Node* _head; }; }（2）test.cpp:
#include "list.h" void TestList1() { my::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); my::list<int>::iterator it = lt.begin(); //实现的模拟迭代器 while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } void TestList2() { struct A { A(int a1=0,int a2=0) :_a1(a1) ,_a2(a2) {} int _a1; int _a2; }; my::list<A> lt; lt.push_back(A(1, 1)); lt.push_back(A(2, 1)); lt.push_back(A(3, 1)); lt.push_back(A(4, 1)); lt.push_back(A(5, 1)); //内置类型支持流I/O //自定义类型不直接支持，可以通过重载流I/O //迭代器模拟指针的行为 my::list<A>::iterator it = lt.begin(); while (it != lt.end()) { //cout << (*it)._a1 <<"," <<(*it)._a2<<endl; cout << it->_a1 << "," << it->_a2 << endl; //it.operate->()->_a1 编译器为了可读性进行了优化，本来是it->->a1,优化后省略了一个"->" ++it; } cout << endl; } void PrintList(const my::list<int>& lt) { my::list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } void TestList3() { my::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); my::list<int>::iterator it = lt.begin(); //实现的模拟迭代器 while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; PrintList(lt); } void TestList4() { my::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.push_front(9); lt.push_front(9); lt.push_front(9); my::list<int>::iterator it = lt.begin(); //实现的模拟迭代器 while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; } void TestList5() { //使用insert测试在偶数的前面插入这个偶数*10 my::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; auto it1 = lt.begin(); while (it1 != lt.end()) { if (*it1 % 2 == 0) { lt.insert(it1, *it1*10); } ++it1; } for (auto e : lt) { cout << e << " "; } cout << endl; } void TestList6() { //删除所有的偶数 my::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; auto it1 = lt.begin(); while (it1 != lt.end()) { if (*it1 % 2 == 0) { it1=lt.erase(it1); } else { ++it1; } } for (auto e : lt) { cout << e << " "; } cout << endl; } void TestList7() { my::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; lt.clear(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; } void TestList8() { my::list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); for (auto e : lt1) { cout << e << " "; } cout << endl; my::list<int> lt2(lt1); //拷贝构造 for (auto e : lt2) { cout << e << " "; } cout << endl; my::list<int> lt3; lt3 = lt1; for (auto e : lt3) { cout << e << " "; } cout << endl; } int main() { //TestList1(); //TestList2(); //TestList3(); //TestList4(); //TestList5(); //TestList6(); //TestList7(); TestList8(); return 0; }
后记：
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
——By 作者：新晓·故知
本文含有隐藏内容，请 开通VIP 后查看