河北省建设注册中心网站首页,it培训机构都有哪些,中国制造网的网络营销方式,搭建网站架构怎么做目录 前言1. list介绍及使用1.1 list介绍1.2 list使用 2. list模拟实现2.1 迭代器功能分类2.2 list迭代器模拟实现2.2.1 普通迭代器2.2.2 const迭代器 3. list和vector区别4. 源码 前言 这篇文章我们继续STL中容器的学习#xff0c;这篇文章要讲解的是list。 1. list介绍及使用… 目录 前言1. list介绍及使用1.1 list介绍1.2 list使用 2. list模拟实现2.1 迭代器功能分类2.2 list迭代器模拟实现2.2.1 普通迭代器2.2.2 const迭代器 3. list和vector区别4. 源码 前言 这篇文章我们继续STL中容器的学习这篇文章要讲解的是list。 1. list介绍及使用
1.1 list介绍 list文档 list的底层实现就是数据结构学过的带头双向循环链表 1.2 list使用
我们来看一下几个常用的接口 首先看一下构造函数 这里几个都是我们熟悉的默认构造、n个val构造、迭代器区间构造以及拷贝构造。 我们再来看一下迭代器 我相信之前的文章对迭代器的介绍已经很详细了这里我们就不过多赘述了。 我们再来看一下修改操作 这里list与string和vector区别在于 list没有重载[]也就是说我们要遍历和访问list就只能用迭代器。迭代器才是通用的方式所有的容器都可以用迭代器而[]只是针对特定容器的特殊方式。 遍历
int main()
{listint l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(3);l.push_back(5);for (auto it l.begin(); it ! l.end(); it)cout *it ;cout endl;for (auto e : l)cout e ;cout endl;for (auto rit l.rbegin(); rit ! l.rend(); rit)cout *rit ;cout endl;return 0;
} 我们再来看几个之前没怎么用过的接口 这里的splice 它可以把链表的一部分转移到另一个链表 remove就是删除指定的元素 merge可以合并两个有序链表 2. list模拟实现
2.1 迭代器功能分类 1、单向迭代器只能不能- -。例如单链表哈希表 2、双向迭代器既能也能--。例如双向链表 3、随机访问迭代器能 - -也能和-。例如vector和string。 迭代器是内嵌类型内部类或定义在类里 2.2 list迭代器模拟实现
2.2.1 普通迭代器 在模拟实现string、vector时是使用的原生指针没有将迭代器用类进行封装但是STL标准库也是用类封装了迭代器。而在模拟实现list迭代器时不能用原生指针了因为list的节点地址是不连续的。 templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, 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;}};
2.2.2 const迭代器 我们先来看一下错误写法 在这里插入代码片typedef __list_iteratorT iterator; const listT::iterator itlt.begin(); 在STL库中是通过类模板多给一个参数来实现这样同一份类模板就可以生成两种不同的类型的迭代器 templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;iterator begin(){//return _head-_next;return iterator(_head-_next);}iterator end(){return _head;//return iterator(_head);}const_iterator begin() const{//return _head-_next;return const_iterator(_head-_next);}const_iterator end() const{return _head;//return const_iterator(_head);}
3. list和vector区别
vectorlist底 层 结 构动态顺序表一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素效率O(N)插 入 和 删 除任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为O(1)空 间 利 用 率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层结点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭 代 器原生态指针对原生态指针进行封装迭 代 器 失 效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效带头结点的双向循环链表使 用 场 景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问
4. 源码
list.h
#includeiostream
using namespace std;
namespace w
{templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _val;list_node(const T val T()):_next(nullptr), _prev(nullptr), _val(val){}};// typedef __list_iteratorT, T, T* iterator;// typedef __list_iteratorT, const T, const T* const_iterator;templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, 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;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;iterator begin(){//return _head-_next;return iterator(_head-_next);}iterator end(){return _head;//return iterator(_head);}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;_size 0;}list(){empty_init();}// lt2(lt1)list(const listT lt)//list(const list lt){empty_init();for (auto e : lt){push_back(e);}}void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}listT operator(listT lt)//list operator(list lt){swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}void push_back(const T x){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);prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;_size;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;--_size;return next;}size_t size(){return _size;}private:Node* _head;size_t _size;};void Print(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}}
