网站建设优化项目,wordpress列表翻页有page,企业网站如何优化,文化集团网站模板STL标准库之list list类的简介常用的list类的接口构造迭代器容量访问修改 list和vector的区别 list类的简介
list是一种序列式容器#xff0c;可以在任意位置插入和删除元素#xff0c;并且其时间复杂度为O(1)#xff0c;在底层#xff0c;list是双向链表结构#xff0c;… STL标准库之list list类的简介常用的list类的接口构造迭代器容量访问修改 list和vector的区别 list类的简介
list是一种序列式容器可以在任意位置插入和删除元素并且其时间复杂度为O(1)在底层list是双向链表结构每个节点通过指针指向下一个节点因此最大的缺陷是不支持随机访问必须从已知位置开始迭代到该位置同时节点除了存储val值之外还要存储指针因此需要一些额外的空间。 由于双向带头循环链表的存在使得list在找尾时无需从头开始遍历这样就有效降低了查找时候的时间复杂度。头节点不存储数据只是记录了当前list的第一个节点的地址和最后一个节点的地址
常用的list类的接口
构造
函数名称功能list(size_type n, const value_type val value_type())n个值为value的元素list()空列表list(const list x)拷贝构造list(InputIterator first, InputIterator last)用first和last进行区间构造
对应写法
listint l(10, 5);
listint l2();
listint l3(l2);int arr[] {1,2,3,4,5};
int n sizeof(arr)/sizeof(arr[0]);
listint l4(arr, arrn);迭代器
函数名称功能begin()end()返回第一个元素的迭代器和最后一个元素的迭代器rbegin()rend()返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的reverse_iterator,即begin位置 从迭代器的在list中的位置可以看到begin()实际上在第一个有效节点的位置而end()在头节点的位置那么为何要这样设置呢 实际上这样设置迭代器后就可以很快速的找到当前链表的头和尾了当需要找尾时使用end()指向节点中的prev就可以快速找到如果需要判断当前列表是否为空呢实际上直接判断end()指向的值和begin()指向的值是否相等如果相等意味着head节点就是当前列表中唯一的节点那么就说明当前列表为空。 判读是否为空就可以直接判断end和begin是否相等因为当只有一个头节点的时候prev和next指向的都是头节点。 容量
函数名称功能empty判断是否为空列表size计算当前列表中有多少个有效节点
访问
函数名称功能front返回第一个节点中值的引用back返回最后一个节点中值的引用 如果需要进行遍历由于list特性是不支持直接使用[]进行随机访问的需要我们通过头节点逐个迭代。 修改
函数名称功能push_front头插一个元素pop_front头删一个元素push_back尾插一个元素pop_back尾删一个元素insertpos位置插入元素erasepos位置删除元素swap交换两个list中的元素clear清空list中的元素 请注意针对迭代器失效的问题在vector中我们说任何可能会导致扩容的操作都可能会导致迭代器失效同时删除也会导致删除当前位置以及后续所有的迭代器失效。但是在list中由于使用链式存储方式因此不存在扩容的情况因此扩容不会导致迭代器失效而删除操作会导致当前位置的迭代器失效并不会影响后续的迭代器。 list和vector的区别
由于vector和list两个容器的底层结构不同导致其特性以及应用场景不同。
vectorlist底层结构动态的顺序表一段连续空间带头节点的双向循环链表随机访问支持随机访问访问效率O(1)不支持访问效率O(n)插入和删除在任意位置插入和删除的效率低需要整个搬移元素时间复杂度为O(n)插入时可能要增容效率低支持在任意位置的插入和删除时间复杂度都为O(1)并且无需扩容拷贝元素效率高空间利用率底层为连续空间不易造成内存碎片空间利用率高缓存利用率高底层动态开辟节点小节点容易造成内存碎片空间利用率低缓存利用率低迭代器例如需要进行迭代器为原生态的指针指针也就是向后偏移一个元素需要对指针进行封装因为迭代器本身是不能通过访问到下一个元素的元素之间使用指针相连迭代器失效插入元素时可能会导致扩容这样就会使得所有的迭代器都失效因此需要对迭代器重新赋值删除元素时也需要重新赋值否则也会失效插入元素不会扩容只有删除元素会导致当前位置迭代器失效其他位置迭代器没有影响使用场景需要高效存储支持随机访问的场景不关心插入删除的效率涉及到大量的插入和删除不关心随机访问
