感谢大佬的光临各位，希望和各人一起进步，望得到你的三连，互三支持，一起进步
数据结构习题_LaNzikinh篮子的博客-CSDN博客
初阶数据结构_LaNzikinh篮子的博客-CSDN博客
收入专栏：C++_LaNzikinh篮子的博客-CSDN博客
其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客
个人主页：LaNzikinh-CSDN博客
文章目录
- 前言
- 一.迭代器
- 二.list的底层实现
- 三.list利用和细节
- 总结
前言
颠末前面两个容器的解说，实在已经对许多接口的利用都了解的差不多了，容器之间接口的利用真的都是大体相同的，但是底层的实现是不同的，本日我们来看看列表是怎样实现这个功能的，在解说列表的实现之前，我们先要再次来解说这个迭代器
一.迭代器
迭代器的功能分为四种迭代器，反向迭代器，常数迭代器，反向常数迭代器，他的性子有三种，单向迭代器，双向迭代器和随机迭代器，性子的意思就是底层结构，底层结构可以决定可以用哪些算法
举个例子来说，好比说我们之前学过的排序算法，他在库内里就一个专门这样子的函数sort，他支持的就是随机的代替其他不支持，所以说在list创建的类就不能用这个库内里的算法，只能自己实现一个，又好比说逆置算法reverse（需要++/--）他支持双向迭代器，所以说随机的也可以，但是单向的就不行
我们的list就是双向迭代器，我们之前学过的vector和string就是随机迭代器，那我们后面的栈和队列是什么呢？
答案是根本不支持迭代,栈的特性是先进后出，队列的特性是先进先出，如果都满意了迭代器的遍历，那这些特性就不存在了，你支持了迭代器，那你的特性的意义在什么地方呢
二.list的底层实现
我们之前讲过了库函数的利用，直接看文档即可，在这里就不做多的了解了，和之前的利用string，vector是大抵相同的，主要照旧来看list的底层，他是一个带头双向循环列表，不是我们以前C语言学过的单链表
接下来了，我们先要来定义两个结构体，一个就是节点本身，另有一个就是指向节点的指针，即便它是一个带头双向循环列表，这两个也是必不可少的
2.1定义两个结构体
结点
const T& data = T()；利用缺省参数来进行初始化
- template<class T>
- struct list_node
- {
- T _data;
- list_node<T>* _next;
- list_node<T>* _prev;
- list_node(const T& data = T())
- :_data(data)
- , _next(nullptr)
- , _prev(nullptr)
- {}
- };
留意：这里获取的迭代器，就是一个节点的指针
由于他是一个指针，所以说我们要用函数重载来定义它的加加减减和判断即是，另有解引用
- template<class T>
- struct list_iterator
- {
- typedef list_node<T> Node;
- typedef list_iterator<T> Self;
- Node* _node;
- list_iterator(Node* node)
- :_node(node)
- {}
- T& operator*()
- {
- return _node->_data;
- }
- Self& operator++()
- {
- _node = _node->_next;
- return *this;
- }
- Self& operator--()
- {
- _node = _node->_prev;
- return *this;
- }
- bool operator!=(const Self& s) const
- {
- return _node != s._node;
- }
- bool operator==(const Self& s) const
- {
- return _node == s._node;
- }
- };
迭代器失效标题
前面说过，此处各人可将迭代器临时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。由于list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
insert（）
- void insert(iterator pos, const T& x)
- {
- Node* cur = pos._node;
- Node* prev = cur->_prev;
- Node* newnode = new Node(x);
- // prev newnode cur
- newnode->_next = cur;
- cur->_prev = newnode;
- newnode->_prev = prev;
- prev->_next = newnode;
- ++_size;
- }
只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
- void erase(iterator pos)
- {
- assert(pos != end());
- Node* prev = pos._node->_prev;
- Node* next = pos._node->_next;
- prev->_next = next;
- next->_prev = prev;
- delete pos._node;
- --_size;
- }
- 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);
- }
直接复用就可以了
- void push_back(const T& x)
- {
- insert(end(), x);
- }
- void push_front(const T& x)
- {
- insert(begin(), x);
- }
- iterator begin()
- {
- return _head->_next;
- }
- iterator end()
- {
- return _head;
- }
- list()
- {
- _head = new Node;
- _head->_next = _head;
- _head->_prev = _head;
- _size = 0;
- }
- private:
- Node* _head;
- size_t _size;
照旧增补几个list一些独特的函数利用方式和一些利用它的细节
emplace：构造和插入元素
他是支持直接传构造函数对象的参数的
- list<A> lt;
- A a1(1,1);
- lt.push_back(3,3);//不合理，不存在
- lt.emplace_back(3,3);//可以
留意：前提要有序不然删不完全
merge：归并排序列表
留意：归并排序列表，v1会被滞空
补：
如果要在pos的位置插入一个30大小的元素
- auto it = lt.begin();
- int k = 3;
- while (k--)
- {
- ++*it;
- }
- it.insert(it, 30);
总结
链表容器结构到这里就结束了，下一章，我们将引入一个适配器的概念去完成栈与队列的知识
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
