MENU

STL的神奇容器之list

April 4, 2020 • Read: 459 • 算法

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

Archives Tip
QR Code for this page
Tipping QR Code