csp信奥赛C++标准模板库STL（3）：list的使用详解

csp信奥赛C++标准模板库STL（3）：list的使用详解

1. list基本概念

list是C++标准模板库(STL)中的双向链表容器。与vector和deque不同，list不支持随机访问，但可以在任意位置快速插入和删除元素。

特点：

• 双向链表：每个元素包含指向前后元素的指针
• 非连续存储：元素在内存中不连续存放
• 动态大小：无需预先指定大小
• 插入删除高效：在任意位置插入删除时间复杂度为O(1)
• 不支持随机访问：不能像数组一样通过下标访问

2. 基本用法

头文件和声明

#include<iostream>#include<list>usingnamespacestd;// 声明listlist<int>lst1;// 空listlist<int>lst2(5,10);// 5个元素，每个初始化为10list<int>lst3={1,2,3,4,5};// 初始化列表(C++11)list<int>lst4(lst3.begin(),lst3.end());// 通过迭代器构造list<int>lst5(lst3);// 拷贝构造

3. 常用操作

3.1 插入元素

list<int>lst;// 末尾插入lst.push_back(10);// {10}lst.push_back(20);// {10, 20}// 开头插入lst.push_front(5);// {5, 10, 20}// 指定位置插入autoit=lst.begin();advance(it,2);// 移动到第3个位置lst.insert(it,15);// {5, 10, 15, 20}// 插入多个元素it=lst.begin();lst.insert(it,3,0);// {0, 0, 0, 5, 10, 15, 20}// 插入范围vector<int>vec={100,200};lst.insert(lst.end(),vec.begin(),vec.end());// 末尾插入vector内容

3.2 删除元素

list<int>lst={1,2,3,4,5,6};// 删除末尾lst.pop_back();// {1, 2, 3, 4, 5}// 删除开头lst.pop_front();// {2, 3, 4, 5}// 删除指定位置autoit=lst.begin();advance(it,2);it=lst.erase(it);// 删除第3个元素，返回下一个迭代器 {2, 3, 5}// 删除指定范围autofirst=lst.begin();autolast=lst.begin();advance(last,2);lst.erase(first,last);// 删除前2个元素 {5}// 删除特定值lst={1,2,3,2,4,2};lst.remove(2);// 删除所有值为2的元素 {1, 3, 4}// 删除满足条件的元素lst={1,2,3,4,5,6};lst.remove_if([](intx){returnx%2==0;});// 删除所有偶数 {1, 3, 5}// 清空listlst.clear();// {}

3.3 访问元素

list<int>lst={10,20,30,40};// 访问首尾元素cout<<"front: "<<lst.front()<<endl;// 10cout<<"back: "<<lst.back()<<endl;// 40// 注意：list不支持随机访问，不能使用lst[2]或lst.at(2)// 遍历访问for(autoit=lst.begin();it!=lst.end();++it){cout<<*it<<" ";}cout<<endl;// 使用范围for循环(C++11)for(intval:lst){cout<<val<<" ";}cout<<endl;

4. 容量操作

list<int>lst={1,2,3};// 大小相关cout<<"size: "<<lst.size()<<endl;// 3cout<<"empty: "<<lst.empty()<<endl;// 0(false)// 调整大小lst.resize(5);// {1, 2, 3, 0, 0}，多出的元素默认初始化为0lst.resize(2);// {1, 2}，截断多余元素lst.resize(4,100);// {1, 2, 100, 100}，多出的元素初始化为100

5. list特有操作

5.1 合并操作(merge)

list<int>lst1={1,3,5};list<int>lst2={2,4,6};// 合并两个已排序的listlst1.merge(lst2);// lst1: {1, 2, 3, 4, 5, 6}, lst2为空// 自定义比较函数的合并list<int>lst3={6,4,2};list<int>lst4={5,3,1};lst3.sort();// {2, 4, 6}lst4.sort();// {1, 3, 5}lst3.merge(lst4,greater<int>());// 降序合并

5.2 排序和去重

list<int>lst={5,3,1,4,2,3,1};// 排序lst.sort();// 升序排序 {1, 1, 2, 3, 3, 4, 5}lst.sort(greater<int>());// 降序排序 {5, 4, 3, 3, 2, 1, 1}// 去重（必须先排序）lst.sort();// 先排序lst.unique();// 去除相邻重复元素 {1, 2, 3, 4, 5}// 自定义去重条件list<int>lst2={1,2,3,4,5};lst2.unique([](inta,intb){returnb-a==1;// 如果相差1，则视为"重复"});// 可能保留 {1, 3, 5}，具体取决于实现

5.3 反转

list<int>lst={1,2,3,4,5};lst.reverse();// {5, 4, 3, 2, 1}

6. 迭代器

list<int>lst={10,20,30,40,50};// 双向迭代器list<int>::iterator it;// 正向迭代器list<int>::reverse_iterator rit;// 反向迭代器// 迭代器操作it=lst.begin();// 指向第一个元素advance(it,2);// 前进2个位置autoprev_it=prev(it,1);// 后退1个位置autonext_it=next(it,1);// 前进1个位置// 反向遍历for(rit=lst.rbegin();rit!=lst.rend();++rit){cout<<*rit<<" ";// 输出: 50 40 30 20 10}// 常量迭代器list<int>::const_iterator cit=lst.cbegin();// *cit = 100; // 错误：不能修改const迭代器指向的值

7. 在信奥赛中的应用示例

案例：约瑟夫环问题

// n个人围成一圈，从1开始报数，报到m的人出列，求最后剩下的人intjosephus(intn,intm){list<int>people;for(inti=1;i<=n;i++){people.push_back(i);}autoit=people.begin();while(people.size()>1){// 数m-1个人for(inti=1;i<m;i++){it++;if(it==people.end()){it=people.begin();}}// 删除第m个人it=people.erase(it);if(it==people.end()){it=people.begin();}}returnpeople.front();}

8. 性能分析

总结

在CSP信奥赛中，list适用于以下场景：

• 需要频繁在任意位置插入删除元素
• 不需要随机访问元素
• 需要高效的合并、拼接操作
• 实现LRU缓存等特定数据结构

掌握list的关键是理解链表特性和STL提供的丰富操作，这些在解决特定问题时非常高效。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

• 2025 csp-j 复赛真题及答案解析（最新更新）
• 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
• 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
• 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
• 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
• 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
• 2020 ~ 2024 csp 复赛真题题单及题解
• 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
• 2021 ~ 2024 csp-s 初赛高频考点解析
• 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
• 2024 csp-j 初赛真题及答案解析
• 2025 csp-j 初赛真题及答案解析（最新更新）
• 2025 csp-s 初赛真题及答案解析（最新更新）
• 2025 csp-x (山东)初赛真题及答案解析(最新更新)
• 2025 csp-x (江西)初赛真题及答案解析(最新更新)
• 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

• 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}