竞赛：STL之vector用法详解
关于vector，迭代器的入门详解，相关函数，以及一些典型习题
目录
4.begin函数和front函数&&end函数和back函数
5.resize()，swap()，sort()，reverse()函数
前言
本文所有编写代码已全部上传到gitee
一：什么是vector
向量（vector）是一个顺序容器，它能存放各种类型的对象。可以简单认为，向量是一个能够存放任意类型的动态数组（也就是说元素的个数可变）。
二：vector常见的函数
1.函数说明表
| 函数名 | 函数说明 |
| push_back(元素) | 增加一个元素到向量后面 |
| insert(位置，元素) | 插入元素到向量的指定位置 |
| insert(位置，个数n，元素) | 插入n个相同的元素到指定位置 |
| insert(位置，头指针，尾指针) | 将另一个向量从头指针的位置开始到尾指针的位置结束(不包括end)之间的内容插入该向量的指定位置 |
| erase(位置) | 删除指定位置的元素 |
| erase(位置1，位置2) | 删除向量[位置1，位置2)中的元素 |
| pop_back() | 弹出(删除)向量的最后一个元素 |
| clear() | 清除向量所有元素，size()变为0 |
| 运算符[i] | 取向量下标为i的元素 |
| front() | 取向量第一个元素 |
| back() | 取向量最后一个元素 |
| begin() | 返回向量头指针 (迭代器)，指向第一个元素 |
| end() | 返回向量尾指针，指向向量最后一个元素的下一个位置 |
| rbegin() | 反向迭代器，指向最后一个元素 |
| rend() | 反向迭代器，指向第一个元素之前的位置 |
| size() | 返回向量中实际元素的个数 |
| resize() | 重新设定向量的大小，也就是可以保存元素的个数 |
| max_size() | 得到 vector 最大可以是多大。 |
| empty() | 判断向量是否为空，等价于 size()为0 |
| swap() | 交换两个同类型向量的数据 |
2.vector的存储和遍历
构造vector的四种方法
（1）vector():创建一个空的vector
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
//定义方法1：定义vector存储int类型的变量
vector<int> v;
cout << v.size() << endl;
v.push_back(10);
v.push_back(20);
v.push_back(30);
print(v);
return 0;
}
//输出为：
//0
//10 20 30（2）vector(n):创建一个元素个数为n的vector
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
//定义方法2：定义一个长度为5的vector，默认值为0
vector<int> v(5);
cout << v.size() << endl;
print(v);
v.push_back(10);
v.push_back(20);
v.push_back(30);
print(v);
return 0;
}
//输出为：
//5
//0 0 0 0 0
//0 0 0 0 0 10 20 30（3）vector(n,t):创建一个元素个数为n且值为t的vector
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
vector<int> v(5, 20);
print(v);
v.push_back(10);
print(v);
return 0;
}
//输出为：
//20 20 20 20 20
//20 20 20 20 20 10
（4）vector(begin,end):复制[begin,end)区间内的另一个数组的元素到vector中
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = { 0,1,2,3,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
vector<int> v(arr, arr + sz); //begin是数组名则从头开始
print(v);
return 0;
}
//输出为：
//0 1 2 3 4
需要注意的是，vector<int> v是创建了一个空的vector，不可以用下标去访问，里面有内容的时候可以访问。
vector：可以用下标访问，但不能越界。
3.vector的插入，删除
insert的几种形式
（1）insert(位置，元素)
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
print(v);
v.insert(v.begin(), 5);
print(v);
v.insert(v.begin() + 1, 3);
print(v);
return 0;
//输出为：
//10 20 30
//5 10 20 30
//5 3 10 20 30
}
（2）insert(位置，个数，元素)
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
//向下标为1的位置插入5个50
v.insert(v.begin() + 1, 5, 50);
print(v);
return 0;
//输出为
//10 50 50 50 50 50 20 30
}
（3）insert(位置，位置，位置)
例如v1.insert(v1.begin()+1,v2.begin()+2,v2.end());
可以理解为从v1起始+1的位置插入v2起始+2到v2结束的所有数字
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
vector<int> v2;
v2.push_back(100);
v2.push_back(200);
print(v1);
//向v1的开头+1的位置插入从v2的开头到结尾的所有元素
v1.insert(v1.begin() + 1, v2.begin(), v2.end());
print(v1);
return 0;
//输出为
//10 20 30
//10 100 200 20 30
}
erase的用法
erase(位置1，位置2)：删除从位置1到位置2的元素
erase(位置1)：删除位置1指向的元素
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
print(v);
//删除v开始的数字
v.erase(v.begin());
print(v);
//删除v开头+1到结尾的所有数字
v.erase(v.begin()+1, v.end());
print(v);
return 0;
//输出为
//10 20 30 40
//20 30 40
//20
}
4.begin函数和front函数&&end函数和back函数
| begin() | 返回向量头指针，指向第一个元素 |
| end() | 返回向量尾指针，指向向量最后一个元素的下一个位置 |
| front() | 取向量的第一个元素 |
| back() | 取向量的最后一个元素 |
可以看到，begin函数返回的是指针，如果要访问具体的元素可以使用front函数
也可以使用解引用操作符利用指针访问里面的值
需要注意的是，end函数是指向向量最后一个元素的下一个位置，无法利用解引用操作符进行访问
具体代码实现如下：
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
//如果选择begin，也可以使用解引用操作符进行访问
cout << v.front() << " " << *v.begin() << endl;
cout << v.back() << endl;
return 0;
//输出为：
//10 10
//40
}
5.resize()，swap()，sort()，reverse()函数
| resize() | 重新设置向量的大小，也就是保存元素的个数 |
| swap() | 实现变量的交换 |
| sort() | 对数组/向量排序 |
| reverse() | 反转数组/向量 |
需要注意的是，swap，sort，reverse这样的函数，并不是vector中特有的函数，它们对于数组变量等同样适用，因此不需要写v.sort这样的表达式，这是错误的
具体代码实现如下：
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = {1,6,5,2,3,7,8};
int sz = sizeof(arr) / sizeof(arr[0]);
vector<int> v(arr, arr + sz);//创建了vector，内置元素为数组arr
sort(v.begin(), v.end());//排序
print(v);
reverse(v.begin(), v.end());//反转
print(v);
v.resize(10); //改变了v的大小，于是剩下的部分用0补齐
print(v);
return 0;
//输出为：
//1 2 3 5 6 7 8
//8 7 6 5 3 2 1
//8 7 6 5 3 2 1 0 0 0
}
实现swap函数：
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main()
{
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
vector<int> v2;
v2.push_back(100);
v2.push_back(200);
cout << "v1:" << endl;
print(v1);
cout << "v2:" << endl;
print(v2);
swap(v1, v2);//交换两个向量
cout << "v1:" << endl;
print(v1);
cout << "v2:" << endl;
print(v2);
return 0;
//输出为：
//v1 :
//10 20 30
//v2 :
//100 200
//v1 :
//100 200
//v2 :
//10 20 30
}
6.二维vector
代码实现如下：
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<vector <int> > v(20);
//需要注意，这里尽量写vector<vector <int> > v，最外边的两个"<"空开一格
//如果连在一起在旧版的编译器可能无法通过，因为"<<",在c++中定义为右移操作符
//vector<vector <int>> v; 可能无法通过
//vector<vector <int> > v; 一定可以通过
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
v[i].push_back(i + j); //v[i]确定一行，循环的往每一行后加数字
}
}
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
cout << v[i][j]<<" ";
}
cout << endl;
}
return 0;
//输出为：
//0 1 2 3 4
//1 2 3 4 5
//2 3 4 5 6
//3 4 5 6 7
//4 5 6 7 8
}
三：vector迭代器遍历
什么是迭代器？
迭代器是用来指向，遍历，修改容器元素的变量，类似于指针。
A：可以遍历STL容器内全部或部分元素的对象
B：指出容器中的一个特定位置
| 操作 | 效果 |
| * | 返回当前位置上的元素值。如果该元素有成员，可以通过迭代器以 operator ->取用 |
| ++ | 将迭代器前进至下一个元素 |
| ==/!= | 判断两个迭代器是否指向同一位置 |
| = | 为迭代器赋值(将所指元素的位置赋值过去) |
迭代器函数
| 操作 | 效果 |
| begin() | 返回一个迭代器，指向第一个元素 |
| end() | 返回一个迭代器，指向最后一个元素之后 |
具体图示化可以理解为下图：
那么，既然迭代器的功能和指针类似，那么首先温习一下指针的功能：
利用指针遍历一个字符串方法如下：
#include <bits/stdc++.h>
using namespace std;
int main()
{
char str[] = "hello world";
char* p;
for (p = str; *p != '\0'; p++)
{
cout << *p;
}
return 0;
//输出为：
// hello world
}
那么我们利用迭代器来迭代vector中的元素：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 10,20,30,40,50 };
vector<int> v(arr, arr + 5); //定义了一个向量
//定义一个迭代器，命名为it
vector<int>::iterator it;
it = v.begin(); //迭代器指向开头元素
(*it)++; //迭代器指向的元素+1
cout << *it << " " << v[0] << endl;
for (it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
return 0;
//输出为
// 11 11 迭代器把begin的元素加一，所以v[0]跟着也变化，体现了迭代器和指针有类似之处
// 11 20 30 40 50 遍历了vector
}
值得注意的是，对(*it)++后导致数组v[0]也发生了变化，体现出了迭代器确实和指针一样可以改变值
vector也支持迭代器反向遍历，我们来温习一下rbegin()函数：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1,2,3,4,5,6 };
vector<int> v(arr, arr + 6);
vector<int>::reverse_iterator rit;
for (rit = v.rbegin(); rit != v.rend(); rit++) //这里用的是rbegin(),所以用的应该是rit++
{
cout << (*rit)<<" ";
}
return 0;
//输出为：
// 6 5 4 3 2 1
}
迭代器分类
常用的迭代器按功能强弱分为:输入、输出、正向、双向、随机访问五种，这里介绍常用的三种。
不同容器的迭代器，其功能强弱有所不同。例如，排序算法需要通过随机访问迭代器来访问容器中的元素，因此有的容器就不支持排序算法。
A、正向迭代器
假设 p 是一个正向迭代器，则 p 支持以下操作: ++p，p++，*p。
此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较
B、双向迭代器
双向迭代器具有正向迭代器的全部功能。
双向选代器p支持--p 和 p--，使得 p 朝和++p 相反的方向移动。
C、随机访问迭代器
随机访问迭代器具有双向迭代器的全部功能
随机访问迭代器 p 还支持以下操作:
p+=i:使得 p往后移动i个元素
p-=i:使得 p往前移动i个元素
p+i:返回 p后面第i个元素的迭代器
p-i:返回 p前面第i个元素的迭代器
p[i]:返回p后面第i个元素的引用
两个随机访问迭代器 p1、p2 还可以用< 、>、<=、>= 运算符进行比较p1<p2 的含义是: p1 经过若干次 (至少一次) ++操作后，就会等于 p2
表达式p2-p1 表示迭代器p2 所指元素和迭代器p1 所指向元素的序号差(p2 和 p1 之间的元素个数减一)
不同容器支持的迭代器
| 容器 | 迭代器 |
| vector | 随机 |
| deque | 随机 |
| list | 双向 |
| set/multiset | 双向 |
| map/multimap | 双向 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
| priority_queue | 不支持迭代器 |
四：vector的一些例题
数组存数问题
题目描述
今有N个数组，初始时，N个数组均为空。共有M次操作，每次在第X个数组中加入数字Y.问最终各数组中有多少数，并将它们排序输出。比如，输入如下数据
3 5
1 31 2
1 1
2 1
3 1
表示有3个数组，共有5次操作，分别向第1个数组存入3，第1个数组存入2，第1个数组存入1，第2个数组存入1，第3个数组存入1。
输出如下
3 1 2 3
1 1
1 1
第1行表示:第1个数组中有3个数，排序结果为123
第2行表示:第2个数组中有1个数，排序结果为1
第3行表示:第3个数组中有1个数，排序结果为1
解题代码
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100001]; //本质上是个数组，存储的是vector数据
int main()
{
int i, j, x, y, m, n;
cin >> n >> m;
for (i = 0; i < m; i++)
{
cin >> x >> y;
v[x-1].push_back(y);
}
for (j = 0; j < x; j++)
{
sort(v[j].begin(),v[j].end());
}
for (i = 0; i < n; i++)
{
cout << v[i].size();
for (j = 0; j < v[i].size(); j++)
{
cout << " " << v[i][j];
}
cout << endl;
}
return 0;
}
字典排序问题
题目描述
给定N个数组，要求先对这N个数组分别进行排序，然后再根据N的数组的字典序对这N个数组进行排序。输出排序的结果。
输入
第一行一个整数N，表示数组数接下来N行，每一行先包含一个整数C，表示数组的大小，接下来C个整数，表示数组中的一个元素。输出
共N行，每行表示一个数组
#include <bits/stdc++.h>
using namespace std;
vector<int> a[100];
int n, c,x;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> c;
//输入
for (int j = 0; j < c; j++)
{
cin >> x;
a[i].push_back(x);
}
//排序
sort(a[i].begin(), a[i].end());
}
//数组间字典序排序
sort(a, a + n);
//输出
for (int i = 0; i < n; i++)
{
for (int j = 0; j < a[i].size(); j++)
{
cout << a[i][j]<<" ";
}
cout << endl;
}
return 0;
}
约瑟夫问题
题目描述
约瑟夫问题来源于公元1世纪的犹太历史学家Josephus。问题描述，有n个人(分别以编号1，2，3...n表示)围成一个圆圈，从编号为1的人开始进行1~m正向报数，报到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;如此重复下去，直到所有的人全部出列，求最后一个出列人的编号
输入
输入文件仅有一行包含二个用空格隔开的整数N，M
输出
输出文件仅有一行包含一个整数表示一个整数，表示最后一个人在队列中的编号
本题实际上可以看成一个循环数组的问题，但我们使用vector实现，具体分析如下：
其实可以看出，解决问题的关键就是找到每次要删除的下标，这个下标有这些问题：
1.每次会遇见循环回来下标怎么处理？
2.每次下标怎么加，规律是什么？
我们找规律其实会发现，每次下标都差2，第三个就会删除，而循环回来的情况可以用到取余操作符，由于一开始下标从0开始，于是在设置寻找下标时，我们从-1开始即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n = 0;
int m = 0;
vector<int> v;
cin >> n >> m; //8 3
for (int i = 1; i <= n; i++)
{
v.push_back(i);
}
//v:1 2 3 4 5 6 7 8
int c = -1;
while (v.size() != 1)
{
c = (c + m) % v.size();
v.erase(v.begin() + c);
c -= 1;
}
cout << v[0];
return 0;
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
6
0- 0
已为社区贡献2条内容
所有评论(0)