list 即双向链表,和数组一样是用来存储数据的容器,与数组比起来其有如下优缺点:
优点:
- 因为是链表,存储的数据都是在“一条链子上的”,增删数据的时候是不需要挪动没有改变的数据的位置的,所以增删数据效率高
- 不需要划分一整片的空间来存储数据,通过首尾的指针变量即可存储前一个和后一个节点的位置
缺点:
- 因为是链表,所以不能像数组一样直接访问链表上的节点,只能通过类似于“顺藤摸瓜”的方式查找数组上的值
- 写起来困难……至少对我而言困难……
但是万幸的是,神奇的cpp居然内置了双向列表!那我们来看看怎么使用吧
引入
和其他的STL容器一样,可以使用万能头文件,或者:
#include<list>
using namespace std;
如果要申明一个list,申明方法可以参照其他的STL容器:
list<type_name>list_name;
//example:
list<int>stand;
常用函数
函数名 | 描述 |
---|---|
1. push_back(object) | 将object插入到链表尾 |
2. push_front(object) | 将object插入到链表尾 |
3. empty() | 链表是否为空 |
4. clear() | 清空链表 |
5. pop_back() | 弹出末尾节点 |
6. pop_front() | 弹出开头节点 |
7. insert(iterator,object) | 在iterator前插入object |
8. erase(iterator) | 清除iterator处的节点 |
9. remove(object) | 清除值为object的节点 |
10. front() | 获取list中的头部元素 |
11. back() | 获取list中的尾部元素 |
注: 使用 erase(iterator) 清除节点后,如果不重新为该的迭代器赋值,将会出错哦~
其余非常用函数请参阅:c++ STL的list用法总结
迭代器
在链表中,最常用的怕不是就是迭代器了,毕竟你要查看链表中的内容啊~
迭代器的定义
与map的迭代器定义相似:
list<int>::iterator it = stand.begin();
//定义了一个从头开始的迭代器
这里值得注意的是,begin()
和end()
分别可以返回开头和结尾的迭代器
通过迭代器访问每个节点
list<int>::iterator it =stand.begin();
for (;it!=stand.end();it++)
{
it!=stand.begin()?printf(" %d",*it):printf("%d",*it);
//输出链表 stand 里的每一个节点的值
}
或者可以这样写:
bool first = true;
for (int x: stand)
{
if (!first)
putchar(' ');
first = false;
printf("%d", x);
}
两种写法输出的结果是一样的
例题:
https://www.luogu.com.cn/problem/P1160
顺手交一手AC代码:
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-03 21:46:15
* @Website1: 449293786.site
* @Website2: sluowanx.cn
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
using _iter=list<int>::iterator;
_iter pos[N];
list<int>stand;
bool vis[N];
void build_queue()
{
int number;
cin>>number;
stand.push_front(1);
//insert first number
pos[1]=stand.begin();
for (int i=2;i<number+1;i++)
{
int id,type;
scanf("%d%d",&id,&type);
if (type)
{
//insert right
auto nest_iter=next(pos[id]);
pos[i]=stand.insert(nest_iter,i);
}
else
{
//insert left
pos[i]=stand.insert(pos[id],i);
}
}
}
void del_queue()
{
int number,member;
cin>>number;
for (int i=0;i<number;i++)
{
scanf("%d",&member);
if (vis[member])
{
//todo
//remove member
stand.erase(pos[member]);
}
vis[member]=0;
}
}
int main()
{
memset(vis,true,sizeof(vis));
build_queue();
del_queue();
//todo
list<int>::iterator it =stand.begin();
for (;it!=stand.end();it++)
{
it!=stand.begin()?printf(" %d",*it):printf("%d",*it);
}
return 0;
}
后话
文章参考:
https://www.yilantingfeng.site/algorithm/856/
https://blog.csdn.net/xiaoquantouer/article/details/70339869
作者:NorthCity1984
出处:https://grimoire.cn/algorithm/stl-list.html
版权:本文《STL的神奇容器之list》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
出处:https://grimoire.cn/algorithm/stl-list.html
版权:本文《STL的神奇容器之list》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任