C++序列容器零基础教程（GESP5）

本教程基于PPT《序列容器类》编写，面向零基础，大量注释，通俗讲解，包含vector、list、迭代器、STL算法、真题实战。 头文件总览：

• #include <vector> 动态数组容器
• #include <list> 双向链表容器
• #include <algorithm> STL算法库 sort、reverse、transform、next_permutation
• #include <iostream> 输入输出

一、什么是容器？

容器就是C++标准库帮我们写好的“装数据的盒子”。 普通数组缺点：大小固定，不能动态增加元素。 容器可以自动扩容，自带增删改查一堆现成函数。 两类重点序列容器：

1. vector：动态数组，内存连续，随机访问快，中间插入删除慢
2. list：双向链表，内存不连续，任意位置插入删除快，随机访问慢

特性	vector	list
底层	动态数组	双向链表
随机访问vec[0]	✅ O(1)	❌ 只能迭代器 O(n)
尾部增删	很快 O(1)	很快 O(1)
头部/中间插入删除	慢 O(n)
排序	用sort()算法	成员函数.sort()，不能用algorithm的sort

---

二、vector 动态数组（最常用）

头文件：#include <vector>

2.1 vector创建的4种写法

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //写法1：空vector，size=0，后面可以push_back加元素
    vector<int> v1;

    //写法2：创建5个int，全部初始化为0
    vector<int> v2(5);

    //写法3：创建5个int，全部初始化为42
    vector<int> v3(5, 42);

    //写法4：C++11直接初始化列表
    vector<int> v4 = {10,20,30,40};

    return 0;
}

2.2 vector常用成员方法

函数	作用
.size()	返回元素个数 O(1)
.empty()	判断是否为空 true空 false不为空
.push_back(x)	尾部追加元素x
.pop_back()	删除尾部元素
.clear()	清空全部元素
.front()	取第一个元素
.back()	取最后一个元素
.resize(n)	修改容器大小
.begin()	迭代器：指向第一个元素
.end()	迭代器：指向最后元素的下一个位置

2.3 vector访问元素三种方式

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v = {10,20,30,40};

    //方式1：下标 [] 和普通数组一样，下标从0开始
    cout << v[0] << endl;

    //方式2：at()，越界会报错，[]越界不会报错，建议调试用at
    cout << v.at(1) << endl;

    //方式3：迭代器，类似指针
    vector<int>::iterator it = v.begin();
    cout << *it << endl; //*解引用，拿到迭代器指向的值

    return 0;
}

2.4 vector遍历三种写法

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v = {1,2,3,4,5};

    //方式1：范围for循环（最简单，C++11）
    cout << "范围for：";
    for(auto num : v){
        cout << num << " ";
    }
    cout << endl;

    //方式2：下标for循环，和数组一样
    cout << "下标循环：";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << " ";
    }
    cout << endl;

    //方式3：迭代器循环，记住条件 it != v.end()，不要用 <
    cout << "迭代器循环：";
    for(vector<int>::iterator it = v.begin(); it != v.end(); it++){
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

2.5 vector插入删除

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v = {10,30,40};

    //insert(迭代器位置，值)：在迭代器前面插入元素
    v.insert(v.begin()+1, 20); //在10和30中间插入20 → {10,20,30,40}

    //erase(迭代器位置) 删除该位置元素
    v.erase(v.begin()+2); //删掉30

    for(auto x:v) cout << x << " ";

    return 0;
}

---

三、list双向链表容器

头文件：#include <list>

list不支持下标 lst[0]！不能随机访问！只能迭代器遍历。

3.1 list常用方法

函数	作用
.push_back(x)	尾部加
.push_front(x)	头部插入，vector没有这个函数
.pop_back()	尾部删
.pop_front()	头部删
.empty()	判空
.size()	返回元素数量，O(n)
.front()	头元素
.back()	尾元素
.clear()	清空
.insert(pos,val)	pos迭代器前插入val
.erase(pos)	删除pos迭代器元素
.sort()	list自己的排序成员函数，不要用algorithm::sort

3.2 list遍历示例

#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> lst;
    lst.push_back(10);
    lst.push_back(20);
    lst.push_front(5); //头部插入5 → {5,10,20}

    //1.范围for
    for(auto e : lst){
        cout << e << " ";
    }
    cout << endl;

    //2.正向迭代器
    for(auto it = lst.begin(); it != lst.end(); it++){
        cout << *it << " ";
    }
    cout << endl;

    //3.反向迭代器 rbegin rend，倒序遍历
    for(auto it = lst.rbegin(); it != lst.rend(); it++){
        cout << *it << " ";
    }
    cout << endl;

    //list专属排序，不能写 sort(lst.begin(),lst.end())！
    lst.sort();

    return 0;
}

⚠️重点坑： sort( begin,end ) 是algorithm库函数，不能给list用。list只能调用自己成员函数 lst.sort()

---

四、STL通用算法（algorithm头文件）

4.1 sort、reverse

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v = {3,1,4,2};

    //sort(起始迭代器，结束迭代器) 默认升序
    sort(v.begin(), v.end()); //1 2 3 4

    //reverse反转区间
    reverse(v.begin(), v.end()); //4 3 2 1

    for(auto x:v) cout << x << " ";
    return 0;
}

4.2 next_permutation 生成全排列⭐GESP高频

字典序排列，next_permutation(begin,end) 功能：生成下一个字典序更大排列 返回true：成功得到下一个排列；返回false：已经最大排列，重置为最小升序。 ✅使用前提：初始数组必须是升序！ 才能遍历全部排列。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> pm = {1,2,3};
    //初始必须升序！do while循环遍历全部排列
    do{
        for(auto x:pm){
            cout << x << " ";
        }
        cout << endl;
    }while(next_permutation(pm.begin(), pm.end()));
    return 0;
}

输出所有6种排列。

N<=9的时候 9! =362880，计算机可以轻松跑完。PPT中“好斗的牛”就是依靠这个枚举全部排列求最优解。

4.3 transform 转换容器元素

transform：批量处理容器数据，可以单参数、双参数。需要预先开辟输出空间。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> nums = {1,2,3,4};
    vector<int> square(nums.size()); //提前准备空间

    //单参数transform：每个元素求平方
    transform(
        nums.begin(), nums.end(), //输入范围
        square.begin(),           //输出起始位置
        [](int x){return x*x;}    //lambda匿名函数，输入x返回x*x
    );
    for(auto x : square) cout << x << " ";
    cout << endl;

    //双参数transform：两个vector对应相加
    vector<int> a={1,2,3}, b={10,20,30};
    vector<int> sum(3);
    transform(
        a.begin(),a.end(),
        b.begin(),
        sum.begin(),
        [](int x,int y){return x+y;}
    );
    for(auto x:sum) cout << x << " ";

    return 0;
}

[](int x){return x*x;}叫做lambda匿名函数，临时写一个小函数给算法使用。

---

五、真题实战1：好斗的牛（next_permutation全排列）

题目简述：N头牛，每头牛左边a[i]不能有牛，右边b[i]不能有牛。求安排顺序后最少牛棚数量。 规则：相邻两头牛X、Y，中间间隔 = max(X.b , Y.a)；总长度 = N头牛本身占N格 + 所有间隔。

N≤9，枚举全部排列求最小值。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    //读入a数组：每头牛左边警戒数量
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    //读入b数组：每头牛右边警戒数量
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }

    vector<int> pm(n);
    for(int i = 0; i < n; i++){
        pm[i] = i; //初始排列0,1,2...n-1，代表牛编号
    }

    int ans = 1e9; //答案初始无穷大

    do{
        int cur_len = n; //n头牛，自身占n个牛棚
        for(int i = 1; i < n; i++){
            int prev_cow = pm[i-1]; //前一头牛
            int now_cow = pm[i];    //当前牛
            //中间间隔 = max(前一头牛的b，当前牛的a)
            cur_len += max(b[prev_cow], a[now_cow]);
        }
        if(cur_len < ans){
            ans = cur_len;
        }
    }while(next_permutation(pm.begin(), pm.end()));

    cout << ans << endl;
    return 0;
}

输入样例

2
1 2
1 2

输出 4，与PPT样例一致。

---

六、真题实战2：强化武器（选票模型）

题意：m张选票，希望1号武器票数严格大于所有其他武器，求最小花费。 思路：枚举目标票数aim（1号武器想要拿到aim张）；

1. 其他人票数最多只能 aim‑1；超过的选票要买走，优先买便宜；
2. 买完强制削减的选票后，如果1号票数还不足aim，再从剩下选票挑最便宜补齐。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1005;

int n,m;
int cnt[MAXN]; //cnt[i]：武器i原始选票数量
vector<int> cost[MAXN]; //cost[i]保存武器i所有选票花费

//calc函数：计算当1号目标aim张选票，需要多少金币
ll calc(int aim)
{
    int cur = cnt[1]; //一号武器现在手里票数
    ll res = 0; //总花费
    vector<int> rest; //存放所有剩下可以买的选票花费

    for(int i = 2; i <= n; i++)
    {
        //这个候选人需要强制买走多少张，保证不超过aim‑1
        int need_buy = max((int)cost[i].size() - (aim-1), 0);
        for(int j = 0; j < need_buy; j++)
        {
            res += cost[i][j]; //买最便宜need_buy张
            cur++; //一号武器票数增加
        }
        //剩下选票放进候选池子，以后缺票可以从这里买
        for(int j = need_buy; j < cost[i].size(); j++)
        {
            rest.push_back(cost[i][j]);
        }
    }
    sort(rest.begin(), rest.end()); //池子从小到大排序
    //还缺多少票
    for(int i = 0; i < aim - cur; i++)
    {
        res += rest[i];
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int p,c;
        cin >> p >> c;
        cnt[p]++;
        cost[p].push_back(c);
    }
    //每个武器内部选票花费从小到大排序
    for(int i = 1; i <= n; i++)
    {
        sort(cost[i].begin(), cost[i].end());
    }

    ll ans = 1e18;
    //枚举所有可能aim：最少是原本一号票数，最多m张
    for(int aim = cnt[1]; aim <= m; aim++)
    {
        ans = min(ans, calc(aim));
    }
    cout << ans << endl;
    return 0;
}

样例输入

4 4
1 1
2 1
3 1
3 2

输出 1。

---

七、课后作业：健身房器械安排（作业题）

N≤9，用next_permutation枚举全部排列。 每台器械宽度a[i]；左右最小间隔b[i]；两台器械中间间隔 = max(左边器械b[i],右边器械b[j],1)，最小间隔强制为1。总长度=所有器械宽度之和 + 所有相邻间隔。求全局最小总长度。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];

    vector<int> pm(n);
    for(int i=0;i<n;i++) pm[i]=i;

    int ans = 1e9;
    do{
        int total_width = 0;
        //累加所有器械自身宽度
        for(int i=0;i<n;i++) total_width += a[pm[i]];
        //计算相邻间隔
        for(int i=1;i<n;i++){
            int left = pm[i-1];
            int right = pm[i];
            //间隔取 max(左边b，右边b，1)
            int gap = max(max(b[left], b[right]), 1);
            total_width += gap;
        }
        ans = min(ans, total_width);
    }while(next_permutation(pm.begin(), pm.end()));
    cout << ans << endl;
    return 0;
}

样例输入1

2
2 3
0 0

输出：6

---

八、重点易错总结（考试必背）

1. vector内存连续，支持下标；list链表，不支持下标访问。
2. list排序必须写.sort()成员函数，不能sort(lst.begin(),lst.end())。
3. next_permutation做全排列，初始数组必须升序，搭配do while。
4. 迭代器循环判断条件：it != end()，不要写 it < end()（list迭代器不支持小于比较）。
5. front()、back()调用前容器不能为空，否则程序崩溃。
6. transform输出容器需要提前开辟足够size空间，不能直接空vector。
7. N<=9，9! =362880，暴力枚举全部排列时间完全可以接受。

C++ vector / list 容器函数对照表（0基础版）

头文件

• vector：#include <vector>
• list：#include <list>
• 通用算法(sort、reverse、next_permutation、transform)：#include <algorithm>

名词解释

• 迭代器 iterator：类似“指向容器元素的指针”，begin()开头，end()末尾下一位；*迭代器取出元素。
• ✅支持；❌不支持；⚠️注意坑点

一、成员函数对比表（容器自己自带的函数）

函数/方法	功能说明	vector（动态数组）	list（双向链表）
.size()	返回容器内元素个数	✅ O(1)	✅ ⚠️PPT写O(n)（老标准）
.empty()	判断容器是否为空，空返回true	✅	✅
.clear()	清空容器全部元素，size变成0
.front()	获取第一个元素的引用（容器不能为空！）
.back()	获取最后一个元素的引用（容器不能为空！）
.push_back(val)	尾部添加元素val
.pop_back()	删除尾部元素
.push_front(val)	头部添加元素val	❌没有这个函数
.pop_front()	删除头部元素
.begin()	返回指向第一个元素的迭代器	✅
.end()	返回最后元素下一个位置迭代器
.rbegin()	反向迭代器：指向最后一个元素
.rend()	反向迭代器：指向第一个元素前面
.insert(pos, val)	在迭代器pos前面插入val，返回新元素迭代器	✅ O(n) 中间插入慢	✅ O(1) 任意位置插入快
.erase(pos)	删除迭代器pos指向的元素，返回后一个元素迭代器	✅ O(n)	✅ O(1)
.sort()	容器自带排序成员函数	❌没有！	✅ lst.sort() 默认升序
[下标]	数组下标访问，例如 v[2]	✅ O(1)随机访问	❌完全不支持下标！不能写lst[0]
.at(下标)	下标访问，越界会报错	✅	❌不支持

⚠️超级重要坑：

1. list 不能用下标 lst[i]！访问元素只能靠迭代器 / 范围for循环。
2. vector没有push_front，想在头部加元素只能用insert(vec.begin(), val)，速度很慢O(n)。
3. list不要用全局sort()算法！要用自己的成员函数.sort()。

---

二、<algorithm>通用算法函数（不属于容器，全局函数）

这些函数不是vector/list自带，要传入**迭代器区间 begin, end**使用

函数	作用	可以用于vector	可以用于list
sort(begin, end)	对区间升序排序	✅	❌ list不能用！用.sort()
reverse(begin, end)	反转区间元素顺序		✅
next_permutation(begin,end)	生成字典序下一个排列		❌不支持
transform(in_begin,in_end,out_begin, op)	批量处理每个元素		✅

简单示例

vector<int> v={3,1,2};
sort(v.begin(),v.end()); //正确

list<int> lst={3,1,2};
// sort(lst.begin(),lst.end()); //错误！
lst.sort(); //正确，调用list自己的排序

---

三、遍历写法对比（0基础必背）

1）vector三种遍历

vector<int> v={1,2,3,4};

//①下标遍历（只有vector能用！list不行）
for(int i=0;i<v.size();i++){
    cout << v[i];
}

//②范围for循环，vector、list通用
for(auto x : v){
    cout << x;
}

//③迭代器遍历，vector、list通用
for(auto it = v.begin(); it != v.end(); it++){
    cout << *it; //*it取出迭代器对应元素
}

2）list两种遍历（❌不能下标）

list<int> lst={1,2,3,4};

//①范围for循环
for(auto x : lst){
    cout << x;
}

//②迭代器遍历
for(auto it = lst.begin(); it != lst.end(); it++){
    cout << *it;
}

//倒序遍历，反向迭代器
for(auto it = lst.rbegin(); it != lst.rend(); it++){
    cout << *it;
}

---

四、时间复杂度速查表（GESP选择题高频）

操作	vector	list
随机访问（取第k个元素）	$O(1)$	$O(n)$，必须一步步移动迭代器
尾部增加/删除 push_back / pop_back	分摊$O(1)$	$O(1)$
头部增加/删除	$O(n)$，大量元素移动
中间位置插入/删除	$O(n)$	$O(1)$（前提已经拿到迭代器）

什么时候选vector？ 大部分场景，需要随机下标访问、主要只在尾部增删。

什么时候选list？ 需要频繁在头部、中间插入删除元素；不需要随机下标访问。

---

五、常见易错代码对比（考试坑）

错误代码	正确代码	原因
list<int> lst; cout << lst[0];	使用迭代器*lst.begin()	list不支持下标[]
sort(lst.begin(),lst.end());	lst.sort();	list不能用algorithm库sort
vector<int> v; v.push_front(5);	v.insert(v.begin(),5);	vector没有push_front
transform(a.begin(),a.end(),b.begin(),func);	预先保证b容器有足够size空间	transform不会自动扩容
next_permutation(v.begin(),v.end());前没有sort	先sort(v.begin(),v.end());再do‑while	next_permutation要从最小排列开始才能遍历全部排列

---

六、极简记忆口诀

1. vector是动态数组，内存连续，可以下标，头插慢；
2. list双向链表，不能下标，任意位置插入删除快；
3. vector用sort全局函数，list用自己的.sort()；
4. next_permutation只支持vector数组，搭配do‑while全排列。