【C++】STL——list
前言
本篇博客我们接着来理解一个STL库里的list链表的结构,根据前面数据结构的铺垫,理解这个结构相对比较容易。我们来一起看看吧
💓 个人主页:小张同学zkf
⏩ 文章专栏:C++
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
目录
1.list介绍
2.list使用
2.1list的构造
2.2list capacity
2.3list element access
2.4list modifiers
3.list迭代器
4.list模拟实现
5.list与vector对比
1.list介绍
文档:list
2.list使用
2.1list的构造
2.2list capacity
2.3list element access
2.4list modifiers
3.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 ++ ); // it = l.erase(it);}}
4.list模拟实现
#include<iostream>
#include<assert.h>
using namespace std;
namespace zkf
{template<class T>struct list_node{T _date;list_node<T>* _next;list_node<T>* _prev;list_node(const T& s=T()):_date(s), _next(nullptr), _prev(nullptr){}};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->_date;}self& operator++(){_node = _node->_next;return *this;}self& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}self& operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const self& s){return _node!= s._node;}ptr operator->(){return &_node->_date;}};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;void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(const list<T>& s){empty_init();for (auto& it : s){push_back(it);}}void swap(list<T>& s){std::swap(_head, s._head);std::swap(_size, s._size);}list<T>& operator=(list<T> s){swap(s);return *this;}iterator insert(iterator it, const T& s){node* newnode = new node(s);node* tail=(it._node)->_prev;newnode->_prev = tail;newnode->_next = it._node;tail->_next = newnode;(it._node)->_prev = newnode;++_size;return newnode;}iterator erase(iterator it){assert(it != end());node* prev = (it._node)->_prev;node* next = (it._node)->_next;prev->_next = next;next->_prev = prev;delete it._node;--_size;return next;}void push_back(const T& s){insert(end(), s);}void push_front(const T& s){insert(begin(), s);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_t size()const{return _size;}bool empty()const{return _size == 0;}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}void clear(){iterator it = begin();while (it != end()){it=erase(it);}}~list(){clear();delete _head;_head = nullptr;}private:node* _head; size_t _size;};
5.list与vector对比
结束语
list总结到这里,下篇准备STL库里的queue和stack
OK,感谢观看!!!