一、概念

1. 意义

vector 翻译为向量，一般说成动态数组。
在插入数据或者新增数据时，数组会动态的拓展长度，即“长度根据需要而自动改变的数组”，整个过程无需人工干预，也不需要实现固定长度。

2. 优点

• 动态
• 随机访问
• 插入删除方便

3. 一维动态数组

(1) 定义

格式：vector<数据类型>动态数组名;

#include <vector>
vector<int>vec;

(2) 功能函数

方法	功能	常用程度
.push_back(x)	在尾部增加一个元素 $x$	⭐⭐⭐
.pop_back()	删除最后一个元素	⭐
.front()	返回首元素	⭐
.back()	返回尾数组	⭐
.size()	返回元素个数	⭐⭐⭐
.empty()	判断是否为空	⭐⭐⭐
.resize(n)	改变实际大小变为 $n$	⭐⭐
.begin()	返回指向第一个元素的迭代器	⭐
.end()	返回指向最后一个元素的下一个位置的迭代器	⭐
.erase()	删除迭代器指向元素	⭐⭐
.clear()	清空所有元素	⭐⭐⭐
.at(pos)	返回 $pos$ 位置元素的值	⭐
.max_size()	返回最大可允许的元素数量值	⭐

(3) 注意事项

• .resize(n) 如果 $n$ 比原来的实际大小更小，那么只会留下前面的 $n$ 个元素。
• .at(pos) 如果越界会产生提示报错。

4. 二维动态数组

(1) 二维静态数组的局限

• 大小固定：在编译时就需要确定，并且无法在运行时改变。如果数组大小超出了预设的限制，就无法存储更多的数据。
• 内存浪费：在编译时就需要分配内存空间，使用的空间如果没有占满，内存就会造成极大浪费。

(2) 二维动态数组操作

a. 定义

// 方法一：vector的数组
vector<int> a[105];

// 方法二：vector的vector
vector <vector<int> > a;
a.resize(105);

b. 初始化

// 方法一：vector的vector
vector<vector<int> > vec={{1,2},{3,4},{5,6}};

// 方法二：vector的vector数组
vector<vector<int> > vec(4, vector<int>(5));

// 方法三：全部初始化为0
vector<vector<int> > vec(4, vector<int>(5,0));

5. 迭代器

(1) 概念

迭代器的作用和指针类似，可以通过引用（*）操作访问其指向的元素内容。
常用的容器（例如 map，set，vector 等）都可以使用一对迭代器来表示范围。

(2) 定义

#include <vector>
vector<int>::iterator it;

(3) 遍历

for (it = vec.begin(); it != vec.end(); it++)
{
	cout << *it << " ";
}

(4) 功能函数

方法	功能	常用程度
.insert(it, x)	迭代器 it 指向的元素前添加一个元素 $x$	⭐⭐⭐
.erase(it)	删除迭代器 it 指向的元素	⭐⭐⭐
.begin()	返回指向第一个元素的迭代器	⭐⭐⭐
.end()	返回指向最后一个元素的下一个位置的迭代器	⭐⭐⭐
reverse(l, r+1)	翻转 $l$ 到 $r$ 范围的元素	⭐⭐
.insert(it, n, x)	迭代器 it 指向元素前增加 $n$ 个相同的元素 $x$	⭐⭐
.insert(it, l, r+1)	迭代器 it 指向元素前插入另一个相同类型向量的 $l$ 到 $r$ 之间的数据	⭐⭐
.erase(l, r+1)	删除 $l$ 到 $r$ 范围的元素	⭐⭐
.rbegin()	反向迭代器，指向最后一个元素	⭐
.rend()	反向迭代器，指向第一个元素之前的位置	⭐

二、例题

1. 命令列表

(1) 审题

题目描述

逛公园的时候，你捡到一个神奇的对讲机，这个对讲机有一个命令列表，列表上的命令分别有三种操作：
a) increase，表示向列表的最后面添加一个数字（列表中的元素唯一）；
b) remove，表示删除列表的第一个元素；
c) least，表示删除列表中的数字中值最小的那一个。

输入描述

第一行会给出一个数字 N，表示你会执行的命令数量。接下来的 $N$ 行中，每行都开始于一个字符串 $S$，$S$ 有三种可能：increase、remove、least。

输出描述

对于每一个操作，请给出适当的答案。
对于 incerase 操作，输出列表此刻的元素个数；
对于 remove 操作，那么删除列表头的元素并输出它。如果列表为空，不输出内容；
对于 least 命令，删除列表中值最小的那一个并输出它。如果列表为空，不输出内容。

样例1

输入

6
increase 5
increase 3
increase 7
increase 2
remove
least

输出

1
2
3
4
5
2

提示

对于 $80\%$ 的数据，$0\le X\le 10^9$，$0\le N\le 100$；
对于 $100\%$ 的数据，$0\le X\le 10^9$，$0\le N\le 5\times 10^4$，保证不会都是添加操作。

(2) 参考答案

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

int n;
int x;
vector<int> vec;

int main()
{
    cin >> n;
    
    while (n--)
    {
        string comm;
        cin >> comm;
        
        if (comm == "increase")
        {
            cin >> x;
            vec.push_back(x);
            cout << vec.size() << endl;
        }
        else if (comm == "remove")
        {
            cout << vec[0] << endl;
            if (!vec.empty())
            {
                vec.erase(vec.begin());
            }
        }
        else if (comm == "least")
        {
            if (!vec.empty())
            {
                int pos;
                int minn = 1e9;
                int len = vec.size();
                for (int i = 0; i < len; i++)
                {
                    if (vec[i] < minn)
                    {
                        minn = vec[i];
                        pos = i;
                    }
                }
                cout << minn << endl;
                vec.erase(vec.begin() + pos);
            }
        }
    }
    
    return 0;
}

如果学过 min_element 的同学也可以这么写：

#include <algorithm>
else if (comm == "least")
{
    if (!vec.empty())
    {
        int minn = min_element(vec.begin(), vec.end());
        cout << *minn << endl;
        vec.erase(minn);
    }
}

2. 借阅表格

(1) 审题

题目描述

在一个图书馆系统中有 $N$ 条借阅书籍记录，每条记录包含读者名和书籍名。每个读者都有一个唯一的读者名，每个读者名是一个只含小写字母且长度小于 $1000$ 的字符串。每个读者每次借阅书籍的名称也是一个只含小写字母且长度小于 $1000$ 的字符串，每次借阅书籍的记录都会被记录下来，现在需要统计每个读者分别借阅了哪些书籍。

输入描述

第 $1$ 行包含一个正整数 $N$。
第 $2N+1$ 行，每行包含 $2$ 个用 $1$ 个空格隔开的字符串，分别表示读者名和借阅的书籍名称。

输出描述

多行，每行的第一个字符串是读者名，接下来的若干字符串是这个读者依次借阅的书籍名称（之间用一个空格隔开）。按照读者名出现的次序排序输出。

样例1

输入

7
joan pride
nikia ulysses
joan prejudice
nikib ulysses
nikic ulysses
nikia moby
betty dack

输出

joan pride prejudice
nikia ulysses moby
nikib ulysses
nikic ulysses
betty dack

提示

对 $80\%$ 的数据保证，$1\le N\le 500$；
对 $100\%$ 的数据保证，$1\le N\le 50000$，且不会都是同一个人的阅读记录。

(2) 参考答案

a. 普通写法

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

int n;
vector<string> names;
vector<vector<string>> books;

int main()
{
    cin >> n;
    
    while (n--)
    {
        string name, book;
        cin >> name >> book;
        
        // 判断名字是否第一次出现
        bool flag = false;
        for (int i = 0; i < names.size(); i++)
        {
            if (names[i] == name) // 出现过
            {
                books[i].push_back(book);
                flag = true;
                break;
            }
        }

        if (!flag) // 没出现过
        {
            // 记录人名
            names.push_back(name);
            
            // 记录书名
            books.push_back({});
            int pos = names.size()-1;
            books[pos].push_back(book);
        }
    }
    
    // 输出表格
    for (int i = 0; i < names.size(); i++)
    {
        cout << names[i] << " ";
        for (int j = 0; j < books[i].size(); j++)
        {
            cout << books[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

b. 结构体

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

struct Node
{
	string reader;
	vector <string> books;
};

int n;
vector <Node> names;

int main()
{
	cin >> n;
	
	while (n--)
	{
		string name, book;
		cin >> name >> book;
		
		bool flag = false;
		for (int i = 0; i < names.size(); i++)
		{
			if (names[i].reader == name)
			{
				names[i].books.push_back(book);
				flag = true;
				break;
			}
		}
		
		if (!flag)
		{
			Node x;
			x.reader = name;
			x.books.push_back(book);
			names.push_back(x);
		}
	}
	
	for (int i = 0; i < names.size(); i++)
	{
		cout << names[i].reader << " ";
		for (int j = 0; j < names[i].books.size(); j++)
		{
			cout << names[i].books[j] << " ";
		}
		cout << endl;
	}
	
	return 0;
}

3. 物品档案柜

(1) 审题

题目描述

学校里有 $n$ 个学生物品档案柜。每个档案柜的格子数量不一，第 $i$ 个档案柜有 $a_i$ 个格子。每个格子编号从 $1$ 开始到 $a_i$。现在有 $q$ 次操作。
1 i j k：在第 $i$ 个柜子的第 $j$ 个格子中存入物品 $k$。当 $k=0$ 时说明清空该格子。
2 i j：查询第i个柜子的第 $j$ 个格子中物品是什么，保证查询的格子中有存过东西。假设学校里共计不会超过 $10^7$ 个档案柜格子，$a_i$ 是确定而未知的，但是保证一定不小于该档案柜存物品请求的格子编号的最大值。有些档案柜中可能一个格子都没有。

输入描述

第一行 $2$ 个整数 $n$ 和 $q$，档案柜个数和操作次数。
接下来 $q$ 行，每行代表一次操作。

输出描述

对于查询操作时，输出答案，两个答案之间以换行隔开。

样例1

输入

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

输出

118014
1

提示

$1\le n,a_i,q\le 10^5$

(2) 参考答案

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

vector<int> a[100005];
int n, q;

int main()
{
    cin >> n >> q;
    while (q--)
    {
        int comm, i, j, k;
        cin >> comm;
        if (comm == 1) // 存入
        {
            cin >> i >> j >> k;
            if (j >= a[i].size())
            {
                a[i].resize(j+1);
            }
            a[i][j] = k;
        }
        else if (comm == 2) // 查询
        {
            cin >> i >> j;
            cout << a[i][j] << endl;
        }
    }
	return 0;
}