C++——STL之list详解-创新互联
- 🏐什么是list
- 🏐list的使用
- 🏀splice
- 🏀unique
- 🏀remove
- 🏀sort
- 🏐list的实现
- 🏀迭代器类（体会c++的优势）
- ⚽迭代器的构造
- ⚽迭代器的模板参数
- 💬总结
🏐什么是list👀先看这里👈
😀作者：江不平
📖博客：江不平的博客
📕学如逆水行舟，不进则退
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
❀本人水平有限，如果发现有错误的地方希望可以告诉我，共同进步👍
list是一个顺序容器，支持常数时间（也就是O(1)）内进行任意位置的插入删除，还支持双向迭代。
- list容器作为双向链表实现;双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置。
- 与其他基本标准序列容器（array, vector and deque）相比， list在容器内已经获得迭代器的任何位置插入、提取和移动元素时通常表现更好，因此在大量使用这些元素的算法中也是如此，例如排序算法。
- 与其他序列容器相比，主要缺点是它们无法通过其位置直接访问元素;例如，要访问列表中的第六个元素，必须从已知位置（如开始或结束）迭代到该位置，这需要这些元素之间的距离的线性时间。它们还会消耗一些额外的内存来保持与每个元素关联的链接信息（这可能是大型小型元素列表的重要因素）。
我们来看一些之前的模板没出现的接口（都不怎么常用）
splice，接合的意思可以理解为转移，从一个链表转移到另一个链表的某个位置处。
去重的接口，再用这个之前我们需要先进行排序，所以我们一搬不会去用，而排序是有消耗的。去重有更好的方法，我们以后再介绍
remove的功能其实可以用find+erase完成
库里已经有个sort了，为什么list自己还有个sort，因为库里的对list不适用，库里的sort是快排，针对连续的空间进行排序，包含三数取中一系列操作，知道两边找中间的操作显然对链表来说难以实现，所以对于list链表式的结构，冒泡插入归并排序都可，归并最好，list的sort就是这么来的
归并对于数组来说缺陷就是有空间复杂度，对于链表来说就不会了
假如说有百万个数据让你来排序，你会选择vector还是list呢？不假思索还是会选择vector，list链表式的不适合排序，还不如拷贝到vector中排序后再拷贝到list快。
templatestruct list_node
{T _data;
list_node* _next;
list_node* _prev;
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
}
struct __list_iterator
{typedef list_nodeNode;
Node* _node;
_list_iterator(node* pnode)
:_pnode(pnode)
{}
}
为什么要写一个迭代器类来实现list？string和vector就不需要。
因为string和vector对象的数据都存储在了一块连续的内存空间，我们通过对象的指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。而list的对象是结点，这里结点的指针并不能访问到数据，我们需要充分的利用c++的优势和特性——封装和运算符重载。
⚽迭代器的模板参数typedef _list_iteratoriterator;
typedef _list_iteratorconst_iterator; 为什么我们要用三个模板参数，原因就在于碰到不能修改的对象也就是const对象时，我们无法对其进行访问，因为用普通迭代器的话，在*迭代器对象(*it)时会出现权限的放大，我们这里通过对象实例化来解决，什么样的对象用什么样的迭代器，这也体现了泛型编程的优势，不然的话我们就出现重新写一个类，只有几个接口不一样的问题了，这是非常麻烦和不可取的，太冗余了。
💬总结- 迭代器类，就是对结点指针进行了封装，对其各种运算符进行了重载，让结点指针的各种行为看起来和普通指针一样。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前文章：C++——STL之list详解-创新互联
分享链接：http://6mz.cn/article/codggs.html