C++STL之VECTOR用法及实战（pat测试）

序vector是什么？什么时候用？vector的定义vector内元素的访问vector常用函数pat测试例题vector邻接表存储图

序

最近作者在刷pat，俗话说，学到能教人的程度才算完全掌握，教人等于输出，教的不对肯定是自己掌握不牢固，也就是内在算法不对。写这篇博客的目的一方面在于复习自己所学过的知识，整理下方便以后再次学习，作者水平很菜，欢迎大佬们纠正。

vector是什么？什么时候用？

vector翻译为向量， 但是在编程中我觉得变长数组更加贴切，也就是长度根据需要自动变化的数组。在考试过程中，有时会碰到用普通数组超内存的情况，就需要vector用邻接表的形式存储图（未完待续）

vector的定义

1.单独定义一个vector 数据类型 typename， vector名称 name；

vector<typename> name; //长度可变的一维动态数组

当然作为一个容器（什么是容器，就像碗里面放水一样，vector是碗，typename是水，当然也可以放米饭什么的），数据类型就可以放int、double、char、结构体等等，甚至你可以放他本身——大碗里放了个小碗。。。

vector<vector<int> > name; //“>” “>”之间要加空格，为了和iostream中的>>流做区分

这就成了一个两个维度都没定义的二维动态数组。灵魂画图，不喜见谅==。

vector<int> name[100];

很多小伙伴看到过这种写法，这种写法意思是其中一维用定义好长度为100的vector数组，另一维为长度动态变化的vector数组，vector中存int类型的数据。

vector内元素的访问

下标访问 与一般数组访问一样，对一个定义为vector vi的vector容器来说，访问vi[index]即可，index为0 ~ vi.size() - 1。 二维访问，对于一个定义为vector name[100]的容器来说，访问vi[x][y]即可，x为长度确定的数组下标，y为长度可变的vector的下标。迭代器访问 迭代器可以理解为一种类似指针的东西，其定义： vector<typename>::iterator it; 其中it就是迭代器的变量名，我们可以通过*it来访问vector内的元素，e.g. #include <cstdio> #include <vector> using namespace std; int main() { vector<int> vi; for(int i = 1; i <= 5; i++) { vi.push_back(i); //数组里依次添加1~5。 } vector<int>::iterator it = vi.begin(); //指向数组开头，存放数组开头地址 for(int i = 0; i < 5; i++) { printf("%d", *(it + i));//输出vi[i] } return 0; }

vector常用函数

push_back(x) 在数组末尾加入一个元素x，时间复杂度为O(1)。pop_back() 从数组末尾弹出一个之前放入的元素，也就是删除数组中尾元素，时间复杂度为O(1)。size() 用来获取数组长度，也就是其中元素的个数，时间复杂度为O(1)。clear() 清空数组，时间复杂度为O(n)。insert(it， x) 在迭代器it所指之处插入元素x，时间复杂度为O(n)。erase() erase(it)，删除迭代器it所指之处的元素。 erase(first, last)， 删除[first，last）之间的元素。左闭右开！！

pat测试例题

A1039 Course List for Student (25 分)

Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.

Input Specification Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤40,000), the number of students who look for their course lists, and K (≤2,500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students N​i (≤200) are given in a line. Then in the next line, N​i student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.

Output Specification: For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student’s name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.

Sample Input: 11 5 4 7 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 1 4 ANN0 BOB5 JAY9 LOR6 2 7 ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6 3 1 BOB5 5 9 AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

Sample Output: ZOE1 2 4 5 ANN0 3 1 2 5 BOB5 5 1 2 3 4 5 JOE4 1 2 JAY9 4 1 2 4 5 FRA8 3 2 4 5 DON2 2 4 5 AMY7 1 5 KAT3 3 2 4 5 LOR6 4 1 2 4 5 NON9 0

示例代码：

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; int getID(char name[]) //字符串hash（另开章节，未完待续），目的在于将字符串转化为数字存储，英文字母为26进制，数字为10进制，统一转化为10进制存储 { int id = 0; for(int i =0; i< 3; i++) { id = id * 26 + (name[i] - 'A'); } id = id * 10 + (name[3] - '0'); return id; } const int N = 40010; //总人数 const int M = 26*26*26*10 + 1; //三位英文字母加一位数字加一 vector<int> selectCource[M]; int main() { char name[5]; int n, k; // 人数及课程数 scanf("%d %d", &n, &k); for(int i = 0; i < k; i++) //对每门课程 { int course, x; scanf("%d %d", &course, &x); for(int j = 0; j < x; j++) //对选这门课的每个人 { scanf("%s", name); int id = getID(name); selectCource[id].push_back(course); //将课程编码加入尾部 } } for(int i = 0; i < n; i++) //n个查询 { scanf("%s", name); int id = getID(name); sort(selectCource[id].begin(), selectCource[id].end());//将每个人课程编号按从小到大排序 printf("%s %d", name, selectCource[id].size()); // 姓名，选课数 for(int i = 0; i < selectCource[id].size(); i++) //依次输出所选课程 { printf(" %d", selectCource[id][i]); } printf("\n"); } return 0; }

vector邻接表存储图

未完待续，敬请期待。