【C++杂货铺】详解list容器
时间:2024-04-03 11:40:35 来源:网络cs 作者:晨起 栏目:卖家故事 阅读:
目录
🌈前言🌈
📁 介绍
📁 使用
📂 构造
📂 迭代器iterator
📂 capacity
📂 modifiers
📂 迭代器失效
📁 模拟实现
📂 迭代器的实现
📂 代码展示
📁 和vector的区别
📁 总结
🌈前言🌈
欢迎收看本期【C++杂货铺】,本期内容将讲解STL中关于list的内容,会分为一下几个方面进行讲解:第一,什么是list,和其他容器的比较;第二,list的常用接口的介绍;第三,从底层除法,模拟实现简易版list;最后,对比和vecotr的主要区别。
以上就是本期要讲解的全部内容了,讲解之前需要你有数据结构中链表的储备知识,是为了更好的理解讲解内容。此外,模拟实现需要类和对象,模板等储备知识,如果只是想简单使用可以只看前两章。
如果你还没有类和对象及模板的知识,可以阅览下面这几篇文章:【C++杂货铺】详解类和对象 [上]-CSDN博客
【C++杂货铺】详解类和对象 [中]-CSDN博客
【C++杂货铺】详解类和对象 [下]-CSDN博客
【C++杂货铺】模板-CSDN博客
📁 介绍
list是可以在常熟范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
list底层是双向链表结构,双向链表中每个元素存储在互不关联的独立节点中,在节点通过指针指向其前一个元素和后一个元素。
和其他的序列式容器相比(vector,array,deque),list通常在任意位置进行插入,移动元素的执行效率更好。
与之相对的,list的最大缺陷是不支持在任意位置的随机访问。
📁 使用
list接口较多,这里简单介绍一些常用的重要接口。
下面是官方文档的链接,对于容器的学习还是要多看文档的。
list - C++ Reference (cplusplus.com)
📂 构造
📂 迭代器iterator
📂 capacity
📂 modifiers
📂 迭代器失效
迭代器失效即迭代器所指向的节点无效,即该节点被删除。因为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); }}
📁 模拟实现
对于list的模拟实现最难实现的就是迭代器的实现。所以下面将重点讲解迭代器内容。
📂 迭代器的实现
迭代器就是通过模拟指针,提供一种统一的方法来使用容器。
对于vecotr这样的容器,迭代器可以直接是指针,但对于list这样的容器,不能直接使用原生指针,因为底层内存地址不是连续的。
指针++,并不能实现node = node->next这样的操作。这里就要用到C++的重要组成部分了,运算符重载和实现了类。通过将指针封装成类,来实现运算符重载。
这里迭代器使用三个模板参数,第一个表示数据data的类型,第二表示数据data的引用,第三个表示数据data的地址。
template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T,Ref,Ptr> iterator;//构造函数ListIterator(Node* node):_node(node){}Ref operator*(){return _node->data;}Ptr operator->(){return &_node->data;}//++ititerator& operator++(){_node = _node->_next;return *this;}iterator operator++(int){iterator temp(*this);_node = _node->_next;return temp;}//--ititerator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator temp(*this);_node = _node->_prev;return temp;}// != bool operator!=(const iterator& it){return _node != it._node;}bool operator==(const iterator & it){return _node == it._node;}Node* _node;};
📂 代码展示
下面将list的实现,放在exercise命名空间中。
namespace exercise{//节点类template<class T>struct ListNode{typedef ListNode<T> Node;Node* _next;Node* _prev;T data;ListNode(const T& val = T()):_next(nullptr),_prev(nullptr),data(val){}};template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T,Ref,Ptr> iterator;//构造函数ListIterator(Node* node):_node(node){}Ref operator*(){return _node->data;}Ptr operator->(){return &_node->data;}//++ititerator& operator++(){_node = _node->_next;return *this;}iterator operator++(int){iterator temp(*this);_node = _node->_next;return temp;}//--ititerator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator temp(*this);_node = _node->_prev;return temp;}// != bool operator!=(const iterator& it){return _node != it._node;}bool operator==(const iterator & it){return _node == it._node;}Node* _node;};//list类template<class T>class list{typedef ListNode<T> Node;public:typedef ListIterator<T,T&,T*> iterator;typedef ListIterator<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>& l){empty_init();for (auto& e : l){push_back(e);}}void swap(list<T>& temp){std::swap(_head,temp._head);std::swap(_size, temp._size);}list<T>& operator=(list<T> temp) {swap(temp);return *this;}void clear(){iterator it = _head->_next;while (it != _head){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;_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 push_back(const T& val){Node* newnode = new Node(val);Node* tail = _head->_prev;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;tail->_next = newnode;}*/void push_back(const T& val){insert(end(), val);}void insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* prev = pos._node->_prev;Node* next = pos._node;newnode->_prev = prev;prev->_next = newnode;newnode->_next = next;next->_prev = newnode;_size++;}iterator erase(iterator pos){Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;_size--;return next;}void pop_back(){erase(--end());}size_t size(){return _size;}private:Node* _head;size_t _size;};}
📁 和vector的区别
📁 总结
以上,就是本期【C++杂货铺】的主要内容了,包含了list的介绍,list常用接口以及模拟实现list。
如果感觉本期内容有帮助到你,欢迎点赞,收藏,关注Thanks♪(・ω・)ノ
阅读本书更多章节>>>>本文链接:https://www.kjpai.cn/gushi/2024-04-03/153198.html,文章来源:网络cs,作者:晨起,版权归作者所有,如需转载请注明来源和作者,否则将追究法律责任!
上一篇:后端处理一个较大的json文件返回数据给前端太慢该如何优化?
下一篇:返回列表