STL-vector deepseek学案（1）

wflengxuenong · 2025-05-08 20:20:53 · 个人记录

STL-vector

一、vector基础知识

1. vector特性

动态数组容器，可自动管理内存
支持O(1)时间的随机访问
尾部插入/删除效率高（O(1)），中间操作效率低（O(n)）
支持动态扩容（容量不足时自动翻倍）

2. 基本操作

#include <vector>
using namespace std;

// 声明与初始化
vector<int> v1;                 // 空vector
vector<int> v2(5);              // 5个0
vector<int> v3(5, 10);          // 5个10
vector<int> v4 = {1,3,5,7,9};   // 初始化列表

// 常用操作
v.push_back(x);       // 尾部插入元素
v.pop_back();         // 删除尾部元素
v.size();             // 获取元素个数
v.empty();            // 判断是否为空
v.clear();            // 清空元素
v.front();            // 第一个元素
v.back();             // 最后一个元素
v.begin(); v.end();   // 迭代器

二、一维vector应用

例题1：洛谷P3156 【深基15.例1】询问学号

题目描述：给定n个学生的学号，进行m次查询，每次给出位置k，输出对应学号

代码实现：

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

int main() {
    int n, m, tmp;
    cin >> n >> m;
    vector<int> stu(n+1);  // 学号从1开始存

    for(int i=1; i<=n; ++i)
        cin >> stu[i];

    while(m--){
        int k;
        cin >> k;
        cout << stu[k] << endl;
    }
    return 0;
}

例题2：AtCoder ABC323 B - Round-Robin Tournament

题目描述：根据比赛结果统计每个选手的胜利次数并排序

核心代码：

struct Player {
    int id, wins;
};

vector<Player> players(n);
// ...输入处理...
sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
    return a.wins != b.wins ? a.wins > b.wins : a.id < b.id;
});

三、二维vector应用

1. 二维声明方式

vector<vector<int>> matrix;          // 空二维数组
vector<vector<int>> mat(5, vector<int>(3));  // 5行3列
vector<vector<int>> tri(5);          // 每行长度不同

例题3：洛谷P3613 【深基15.例2】寄包柜

题目描述：模拟超市寄包柜操作，支持：

在第i个柜子的第j个格子存入物品k
查询第i个柜子第j个格子的物品

代码实现：

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

vector<vector<int>> lockers;  // lockers[i]表示第i个柜子

int main() {
    int n, q;
    cin >> n >> q;
    lockers.resize(n+1);  // 柜子编号从1开始

    while(q--){
        int op, i, j;
        cin >> op >> i >> j;
        if(op == 1){
            int k;
            cin >> k;
            if(lockers[i].size() <= j)  // 需要扩容
                lockers[i].resize(j+1);
            lockers[i][j] = k;
        } else {
            cout << lockers[i][j] << endl;
        }
    }
    return 0;
}

例题4：图的邻接表存储（Codeforces 231D）

题目描述：实现图的邻接表存储，处理多次查询

邻接表实现：

int n = 1e5;
vector<vector<int>> adj(n+1);  // adj[u]存储u的邻接点

// 添加边u-v
adj[u].push_back(v);
adj[v].push_back(u);  // 无向图

// 遍历u的邻接点
for(int v : adj[u]){
    // 处理邻接点v
}

四、练习题推荐

洛谷P1177 【模板】排序（vector排序应用）
Codeforces 474B - Worms（前缀和+二分查找）
AtCoder ABC142D - Disjoint Set of Common Divisors（因数分解）
at_abc404_c （图的存储与遍历）
洛谷P3383 【模板】线性筛素数（vector维护质数表）
Codeforces 510B - Fox And Two Dots（二维矩阵DFS）

五、使用技巧

预分配空间：v.reserve(n)减少扩容次数
避免越界访问：使用v.at(i)进行边界检查
高效清空：vector<int>().swap(v)释放内存
二维数组初始化：vector<vector<int>>(n, vector<int>(m, -1))
搭配算法库：sort, lower_bound, unique等STL算法

六、常见错误

未初始化直接访问元素
在循环中使用size()但修改容器
二维数组行列顺序混淆
未处理扩容导致越界
错误估计时间复杂度（特别是中间插入操作）