STL的神奇容器之list

list 即双向链表，和数组一样是用来存储数据的容器，与数组比起来其有如下优缺点：

优点：

1. 因为是链表，存储的数据都是在“一条链子上的”，增删数据的时候是不需要挪动没有改变的数据的位置的，所以增删数据效率高
2. 不需要划分一整片的空间来存储数据，通过首尾的指针变量即可存储前一个和后一个节点的位置

缺点：

1. 因为是链表，所以不能像数组一样直接访问链表上的节点，只能通过类似于“顺藤摸瓜”的方式查找数组上的值
2. 写起来困难……至少对我而言困难……

但是万幸的是，神奇的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