✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

目录

前言

一 list的介绍及使用

1.1 list的介绍

1.2 list的使用 

1.2.1 list的构造

1.2.2 list iterator的使用

1.2.3 list capacity 

1.2.4 list element access 

 1.2.5 list modifiers

1.2.6 list的迭代器失效 

 1.2.7 List中sort的效率测试

二、list的模拟实现

 2.1 正向迭代器的实现

2.1.1 正向迭代器的封装 

 2.1.2 迭代器的使用

2.2 list相关的成员函数

 2.2.1 构造函数

2.2.1.1 默认构造函数

 2.2.1.2 有参构造函数

 2.2.1.3 迭代器区间构造函数 

2.2.1.4 拷贝构造 

1.传统 

2.现代 

2.2.2 析构函数和clear

2.2.2.1 析构函数

2.2.2.2 clear()

 2.2.3 赋值重载

2.2.4 修改相关函数（Modifiers）

2.2.4.1 empty、size

 2.2.4.2 insert

2.2.4.3 erase 

2.2.4.4 尾插尾删头插头删 

2.3 反向迭代器的实现 

三 list模拟实现的全部代码

总结

---

前言

本篇详细介绍了list的使用和模拟实现，让使用者了解list，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

---

一 list的介绍及使用

1.1 list的介绍

list文本介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

1.2 list的使用 

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展 的能力。以下为list中一些常见的重要接口。

1.2.1 list的构造

构造函数（ (constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 

1.2.3 list capacity 

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

1.2.4 list element access 

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

 1.2.5 list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

list中还有一些操作，需要用到时大家可参阅list的文档说明。

1.2.6 list的迭代器失效 

前面说过，此处大家可将迭代器暂时理解成类似于指针

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值 l.erase(it); ++it; } } // 改正void TestListIterator() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { l.erase(it++); } }

 1.2.7 List中sort的效率测试

我们用一段代码来测试一下list中sort的性能

#include<iostream>#include<algorithm>#include<vector>#include<list>using namespace std;void test_op(){srand((unsigned int)time(NULL));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){int e = rand();lt1.push_back(e);lt2.push_back(e);}// 拷贝到vector排序，排完以后再拷贝回来int begin1 = clock();for (auto e : lt1){v.push_back(e);}sort(v.begin(), v.end());size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();//list调用自己的sortint begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);}

 

会发现哪怕我先拷贝到vector排完再拷贝回去效率都比list的sort效率高，所以list的sort实际中意义不是很大！！ 

二、list的模拟实现

 2.1 正向迭代器的实现

2.1.1 正向迭代器的封装 

我们在学习vector的时候，发现vector的迭代器就是一个原生指针T*，这得益于vector的空间的连续性

那我们还能像vector一样用原生指针去修饰迭代器吗？

不能，链表空间上是不连续的，那我们对一个节点指针进行加减，就很难说能不能找到下一个节点，更多的是找不到的情况

我们在数据结构中访问下一个节点，往往是利用当前节点存的下一节点的地址来进行访问的

所以我们可以将迭代器单独封装成一个类去管理节点

template<class T, class Ref, class Ptr> //Ref == T& Ptr == T*struct ListIterator //这里使用struct是因为我们要多次访问成员，也可使用class+public{ 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*() //解引用 { return _pNode->_val; } T* operator->() { return &_pNode->_val; } Self& operator++() //前置++ { _pNode = _pNode->_pNext; return *this; } Self operator++(int) //后置++ { Self temp(*this); _pNode = _pNode->_pNext; return temp; } Self& operator--() //前置-- { _pNode = _pNode->_pPre; return *this; } Self& operator--(int) //后置-- { Self temp(*this); _pNode = _pNode->_pPre; return temp; } bool operator!=(const Self& l) //不相等判断 { return _pNode != l._pNode; } bool operator==(const Self& l) //相等判断 { return !(*this != l); } PNode _pNode;};

 T* operator->()  大家可能有疑惑

 当我们的节点里存的是内置类型或者STL容器是，库里面的<<重载了这些来读取数据

但如果是我们自己写的类型（如class CH），<<并不能读取该类型的数据

因此我们要取来节点自定义类的指针，来访问该类的内部的数据（因为最底层都是内置类型

 2.1.2 迭代器的使用

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: iterator begin() { return iterator(_pHead->_pNext); } iterator end() { return iterator(_pHead); } const_iterator begin()const { return const_iterator(_pHead->_pNext); } const_iterator end()const { return const_iterator(_pHead); }private： PNode _pHead; }

这边我们用到了匿名对象。 

这里的const迭代器为什么不能直接用const修饰普通迭代器？？

 因为typedef碰到const的话，就不是简单的字符串替换  实际上你以为的const T* ，在这里变成了T*const ，因为迭代器我们是希望他可以进行++和--的，而我们只是不希望他指向的内容给改变，所以我们的const要修饰的是指针的内容，而不是修饰指针。

2.2 list相关的成员函数

 2.2.1 构造函数

2.2.1.1 默认构造函数

list(){ _pHead = new Node; _pHead->_pPre = _pHead; _pHead->_pNext = _pHead;}

因为无论如何都要有哨兵节点(方便我们不用判空，所以我们直接封装一个 

void CreateHead(){ _pHead = new Node; _pHead->_pPre = _pHead; _pHead->_pNext = _pHead;}

 2.2.1.2 有参构造函数

list(int n, const T& value = T()) { CreateHead(); for (int i = 0; i < n; ++i) push_back(value); }

 2.2.1.3 迭代器区间构造函数 

template <class Iterator>list(Iterator first, Iterator last){ CreateHead(); while (first != last) { push_back(*first); ++first; }}

2.2.1.4 拷贝构造 

1.传统 

//拷贝构造函数传统写法list(const list<T>& l){CreateHead();for (auto e : l)push_back(e);}

2.现代 

void swap(list<T>& l){ std::swap(_pHead, l._pHead);}list(const list<T>& l){ CreateHead(); // 用l中的元素构造临时的temp,然后与当前对象交换 list<T> temp(l.begin(), l.end()); swap(temp);}

2.2.2 析构函数和clear

2.2.2.1 析构函数

~list(){ clear(); delete _pHead; _pHead = nullptr;}

2.2.2.2 clear()

void clear(){ iterator p = begin(); while (p != end()) { p = erase(p); } _pHead->_pPre = _pHead; _pHead->_pNext = _pHead;}

 2.2.3 赋值重载

list<T>& operator=(const list<T> l){ swap(l); return *this;}

2.2.4 修改相关函数（Modifiers）

2.2.4.1 empty、size

size_t size()const{ size_t size = 0; ListNode* p = _pHead->_pNext; while (p != _pHead) { size++; p = p->_pNext; } return size;}bool empty()const{ return size() == 0;}

 2.2.4.2 insert

// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){ PNode newnode = new Node(val); PNode cur = pos._pNode; PNode prev = cur->_pPre; newnode->_pPre = prev; newnode->_pNext = cur; prev->_pNext = newnode; cur->_pPre = newnode; return iterator(newnode);}

2.2.4.3 erase 

// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){ assert(pos != end()); PNode prev = pos._pNode->_pPre; PNode next = pos._pNode->_pNext; prev->_pNext = next; next->_pPre = prev; delete pos._pNode; return iterator(next);//利用匿名对象返回}

2.2.4.4 尾插尾删头插头删 

// List Modify void push_back(const T& val) { insert(end(), val); } void pop_back() { erase(--end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { erase(begin()); }

2.3 反向迭代器的实现 

 sgi版本下的反向迭代器，其实就是将构建一个反向迭代器的类将正向迭代器封装起来，这个时候正向迭代器的++就是反向迭代器的--

namespace bit{// 适配器 -- 复用template<class Iterator, class Ref, class Ptr> //Ref == T& Ptr == T*struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator temp = _it;--temp;return *temp;}Self& operator++(){--_it;return *this;}Self operator++(int){Iterator tmp = _it;--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){iterator temp = _it;++_it;return temp;}bool operator!=(const Self& s){return _it != s._it;}bool operator==(const Self& s){return _it == s._it;}Iterator _it;};}

 为什么解引用的是前一个位置的元素？？？

 

 from C++：List的使用和模拟实现-CSDN博客 图来源

三 list模拟实现的全部代码

#pragma oncenamespace ch{ // 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的迭代器类 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*() { return _pNode->_val; } T* operator->() { return &_pNode->_val; } Self& operator++() { _pNode = _pNode->_pNext; return *this; } Self operator++(int) { Self temp(*this); _pNode = _pNode->_pNext; return temp; } Self& operator--() { _pNode = _pNode->_pPre; return *this; } Self& operator--(int) { Self temp(*this); _pNode = _pNode->_pPre; return temp; } bool operator!=(const Self& l) { return _pNode != l._pNode; } bool operator==(const Self& l) { return !(*this != l); } PNode _pNode; }; template<class Iterator, class Ref, class Ptr> //Ref == T& Ptr == T* struct Reverse_iterator { typedef Reverse_iterator<Iterator, Ref, Ptr> Self; Reverse_iterator(Iterator it) :_it(it) {} Ref operator*() { Iterator temp = _it; --temp; return *temp; } Self& operator++() { --_it; return *this; } Self operator++(int) { Iterator tmp = _it; --_it; return tmp; } Self& operator--() { ++_it; return *this; } Self operator--(int) { iterator temp = _it; ++_it; return temp; } bool operator!=(const Self& s) { return _it != s._it; } bool operator==(const Self& s) { return _it == s._it; } Iterator _it; }; //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; //反向迭代器 typedef Reverse_iterator<iterator, T&, T*> reverse_iterator; typedef Reverse_iterator<iterator, const T&, const T*> const_reverse_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.begin(), l.end()); swap(temp); } list<T>& operator=(const list<T> l) { 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()const { return const_iterator(_pHead->_pNext); } const_iterator end()const { return const_iterator(_pHead); } //反向迭代器(可读可写) reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } //反向迭代器（可读不可写） const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } /// // List Capacity size_t size()const { size_t size = 0; ListNode* p = _pHead->_pNext; while (p != _pHead) { size++; p = p->_pNext; } return size; } bool empty()const { return size() == 0; } // List Access T& front() { assert(!empty()); return _pHead->_pNext->_val; } const T& front()const { assert(!empty()); return _pHead->_pNext->_val; } T& back() { assert(!empty()); return _pHead->_pPre->_val; } const T& back()const { assert(!empty()); 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) { insert(begin(), val); } void pop_front() { erase(begin()); } // 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { PNode newnode = new Node(val); PNode cur = pos._pNode; PNode prev = cur->_pPre; newnode->_pPre = prev; newnode->_pNext = cur; prev->_pNext = newnode; cur->_pPre = newnode; return iterator(newnode); } // 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos) { assert(pos != end()); PNode prev = pos._pNode->_pPre; PNode next = pos._pNode->_pNext; prev->_pNext = next; next->_pPre = prev; delete pos._pNode; return iterator(next);//利用匿名对象返回 } void clear() { iterator p = begin(); while (p != end()) { p = erase(p); } _pHead->_pPre = _pHead; _pHead->_pNext = _pHead; } void swap(list<T>& l) { std::swap(_pHead, l._pHead); } private: void CreateHead() { _pHead = new Node; _pHead->_pPre = _pHead; _pHead->_pNext = _pHead; } PNode _pHead; };}

---

总结

✨✨✨各位读友，本篇分享到内容是否更好的让你理解了C++的list，如果对你有帮助给个👍赞鼓励一下吧！！

🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。

感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！。