深入理解C++stl::list底层实现+模拟实现

欢迎来到干货小仓库!!!               "人生没有 Ctrl - Z ，但永远可以 push 新版本"

1.list的介绍

①stl::list的底层实现是带头双向循环链表结构。

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

③双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

2.list的使用 2.1list的构造 构造函数接口说明list(size_t n , const T& val = T())构造的list中包含n个值的val 元素list()构造空的listlist(const list& x)拷贝构造函数list(InputIterator first ,InputIterator last)用[ first , last) 区间中的元素构造list int main() { list<int> lt1; // 构造空的lt1 list<int> lt2(4, 100); // lt2中放4个值为100的元素 list<int> lt3(l2.begin(), l2.end()); // 用lt2的[begin(), end()）左闭右开的区间构造lt3 list<int> lt4(l3); // 用l3拷贝构造lt4 return 0; } 2.2 list iterator的使用

注意:list的迭代器的底层是链表的节点,其访问链表中的数据，是通过操作符重载的方式来进行实现的。

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

2.3 list 关于容量的函数 函数声明接口说明empty()检测 list 是否为空，是返回  true ，不是则返回 false。size()返回 list 有效节点的个数。 #include<iostream> #include<list> using namespace std; int main() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); cout <<"size:"<< lt.empty() << endl; cout <<"empty:"<< lt.size() << endl; return 0; } 2.4 list 中的数据访问函数 函数声明接口说明front返回 list 的第一个节点中的引用back返回 list 的最后一个节点中的值的引用 2.5 list 关于数据的函数 函数声明接口说明push_front在 list 首元素前插入值为 val 的元素pop_front删除 list 中的第一个元素push_back在 list 尾部插入值为 val 的元素pop_back删除 list 中最后一个元素insert在 list 的 pos  位置中插入值为 val 的元素erase删除 list 中 pos 位置的元素swap交换 两个 list  中的元素clear清空 list 中的有效元素 // list插入和删除 // push_back/pop_back/push_front/pop_front void TestList3() { int array[] = { 1, 2, 3 }; list<int> L(array, array + sizeof(array) / sizeof(array[0])); // 在list的尾部插入4，头部插入0 L.push_back(4); L.push_front(0); PrintList(L); // 删除list尾部节点和头部节点 L.pop_back(); L.pop_front(); PrintList(L); } // insert /erase void TestList4() { int array1[] = { 1, 2, 3 }; list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0])); // 获取链表中第二个节点 auto pos = ++L.begin(); cout << *pos << endl; // 在pos前插入值为4的元素 L.insert(pos, 4); PrintList(L); // 在pos前插入5个值为5的元素 L.insert(pos, 5, 5); PrintList(L); // 在pos前插入[v.begin(), v.end)区间中的元素 vector<int> v{ 7, 8, 9 }; L.insert(pos, v.begin(), v.end()); PrintList(L); // 删除pos位置上的元素 L.erase(pos); PrintList(L); // 删除list中[begin, end)区间中的元素，即删除list中的所有元素 L.erase(L.begin(), L.end()); PrintList(L); } // resize/swap/clear void TestList5() { // 用数组来构造list int array1[] = { 1, 2, 3 }; list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0])); PrintList(l1); // 交换l1和l2中的元素 list<int> l2; l1.swap(l2); PrintList(l1); PrintList(l2); // 将l2中的元素清空 l2.clear(); cout << l2.size() << endl; } 2.6 list 迭代器失效

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

示例:

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

list 中的 sort 底层实现是 归并排序 实现的。(时间复杂度高，效率低)

算法库中的 sort 底层是 快排 实现的。(时间复杂度低，效率高)

效率测试和对比：

4.list的模拟实现及正向和反向迭代器解析 4.1list的迭代器封装

list 的迭代器 和 string和vector迭代器的区别：

首先我们得清楚，list 中每一个节点，在空间都是非连续存储的，不像string 和 vector 的迭代器一样直接对迭代器++/-- 即可，由于其底层是内置类型的指针形似而它们在内存中存储数据又是在连续的空间上存储的，不需要我们进行因此我们在对迭代器做 ++/ -- 等操作的时候重载运算符。

我们应该怎么办呢？

通过封装迭代器，对++、--等运算符实现重载。

迭代器的成员变量的解析:

4.2迭代器模板参数的解析

4.3正向迭代器模拟实现 template<class T> struct list_node { list_node<T>* _next=nullptr; list_node<T>* _prev=nullptr; T _val; list_node(const T& val = T()) :_val(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->_val; } Ptr operator->() { return &_node->_val; } 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) const { return _node != it._node; } bool operator==(const Self& it) const { return _node == it._node; } }; 4.4反向迭代器模拟实现

原理和正向迭代器差不多，反向迭代器的成员变量的类型是 正向迭代器，通过操作符重载的方式实现逻辑变化，反向迭代器的操作符重载实现，底层原理都是去调用 正向迭代器 的操作符重载，唯一区别就是逻辑不同。

template<class iterator,class Ref,class Ptr> struct Reverse_iterator { public: typedef Reverse_iterator<iterator, Ref, Ptr> Self; iterator _it; Reverse_iterator(iterator it) :_it(it) { } Self operator++() { --_it; return *this; } Self operator--() { ++_it; return *this; } Ref operator*() { iterator tmp = _it; return *(--tmp); } Ptr operator->() { return &(operator*()); } bool operator!=(const Self& s) const { return _it != s._it; } }; 4.5 list 函数模拟实现 template<class T> struct list_node { list_node<T>* _next=nullptr; list_node<T>* _prev=nullptr; T _val; list_node(const T& val = T()) :_val(val) {} }; 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; typedef Reverse_iterator<iterator, T&, T*> reverse_iterator; typedef Reverse_iterator<const_iterator, const T&,const T*> reverse_const_iterator; //反向迭代器 reverse_iterator rbegin() { return reverse_iterator(_head); } reverse_iterator rend() { return reverse_iterator(_head->_next); } //const 反向迭代器 reverse_const_iterator rbegin() const { return reverse_const_iterator(_head); } reverse_const_iterator rend() const { return reverse_const_iterator(_head->_next); } //正向迭代器 iterator begin() { //return _head->_next; return iterator(_head->_next); } iterator end() { return _head; //return iterator(_head); } //const 正向迭代器 const_iterator begin() const { //return _head->_next; return const_iterator(_head->_next); } const_iterator end() const { //return _head; return const_iterator(_head); } void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; _sz = 0; } list() { empty_init(); } list(const list<T>& lt) { empty_init(); auto it = lt.begin(); while (it != lt.end()) { push_back(*it); ++it; } } void swap( list<T>& lt) { std::swap(_head, lt._head); std::swap(_sz, lt._sz); } list<T>& operator=(list<T> lt) { swap(lt); return *this; } 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(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } //pos之前插入 iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); cur->_prev = newnode; newnode->_prev = prev; prev->_next = newnode; newnode->_next = cur; ++_sz; return newnode; } 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; --_sz; return next; } size_t size() { return _sz; } void clear() { list<T>::iterator it = begin(); while (it != end()) { it = erase(it); } _sz = 0; } ~list() { clear(); delete _head; _head = nullptr; } private: Node* _head; size_t _sz; //用于记录list中有效数据的个数 }; 5. list 和 vector的对比 vectorlist底层结构动态顺序链表，一段连续空间带头结点的双向循环链表随机访问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)插入和删除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N),插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低迭代器原生态指针对原生态指针(节点指针)进行封装迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

---

觉得不错的，大家可以点点赞 +  收藏!!! 谢谢大家的支持。