首页 > C++学习篇(8)-序列式容器list
头像
文刀刘+1
编辑于 2021-01-09 10:20
+ 关注

C++学习篇(8)-序列式容器list

本篇内容主要介绍STL中序列式容器list,它是一种环状双向链表,只支持双向顺序访问,在任何位置进行插入或删除操作速度都很快,但是查找速度较慢,时间复杂度为O(n)。如果对文章内容感兴趣,欢迎大家多多关注微信公众号"爱折腾的码农",另外本人将自己在秋招过程中遇到的一些算法题和总结的典型代码题汇总成word文档和pdf文档。里面内容包括但不限于数据结构中的冒泡、堆排、归并、快排等排序方法,二叉树遍历、前缀树、哈希表、LRU、股票买卖、C++读取输入方法的实现方法等内容,如果感兴趣的话可以微信公众号后台回复“算法题”,欢迎大家关注。原文链接:https://mp.weixin.qq.com/s/r5kcNSTHScwmdHIGRLXQgA

list

个人认为list相当于数据结构里面的双向链表,但是实现功能更加复杂。它的好处是每次插入或删除元素时,就要配置或释放一个元素空间,因此,对空间不会产生浪费,对于任何位置的元素插入或删除是都是O(1)的时间复杂度。

list节点

list迭代器

注意:在list中使用erase只会使得当前迭代器失效,其他位置的元素在在迭代器访问时不会失效

原因是:vector是连续的线性存储空间,当删除元素时,从当前位置后的所有元素都需要向前移动一位,这就导致后面元素的迭代器完全失效,但是对于list来说,其存储元素时不连续的存储空间,所以删除当前元素不会对其他位置的元素产生影响,也不会导致其他位置的迭代器失效。

list数据结构(环状双向链表)

list使用方法

//创建ilist
list<int> ilist;

//获取ilist对象大小
cout << "size = " << ilist.size() << endl; //size = 0;


//添加元素
ilist.push_back(0);
ilist.push_back(1);
ilist.push_back(2);
ilist.push_back(3);

//遍历数据,迭代器it的原本类型是 it = list<int>::iterator;
for(auto it = ilist.begin(); it != ilist.end(); ++it){
   cout << *it << " ";
}
cout << endl;


//查找元素
list<int>::iterator itf = find(ilist.begin(), ilist.end(), 3);

//插入元素
ilist.insert(ilist.begin(), 99);

//删除元素
ilist.erase(ilist.begin());

list和vector的区别?

1、list不能够像vector一样以普通指针作为迭代器,因为节点不保证连续的存储空间; 但是vector是连续的线性存储空间,当容量不足时会进行2/1.5倍扩容操作;

2、list插入和删除操作不会引起其他元素的迭代器失效,但是vector会;

3、list不仅是双向链表,而且是环状双向链表,所以它的迭代器是双向迭代器,只需要一个指针 ;

4、list不像vector那样可以在空间不足的时候重新配置、数据移动的操作,所以插入前的所有迭代器都是有效的。

5、相较于vector直接分配连续的空间来说。list节点每次插入和删除都需要分配和释放空间;

6、vector的查找时间复杂度为O(1),但是插入和删除为O(n);list的插入和删除时间复杂度为O(1),但是查找为O(n);

7、可以从缺页中断谈起,因为对于vector是连续的线性存储空间,所以对于数据访问时产生的缺页中断次数更少,最差情况下也仅需要少量的页面换入换出即可,但是list是不连续的存储空间,所以导致缺页中断的几率更高。


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐