【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迭代器

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，感谢观看！！！