算法竞赛入门到进阶(微课版清华科技大讲堂)

作者简介

内容简介

3.1.1vector 视频讲解 数组是基本的数据结构，有静态数组和动态数组两种类型。在算法竞赛中，编码的惯例是： 如果空间足够，能用静态数组就用静态数组，而不用指针管理动态数组，这样编程比较简单并且不会出错； 如果空间紧张，可以用STL的vector建立动态数组，不仅节约空间，而且也不易出错。 vector http://www.cplusplus.com/reference/vector/vector/。是STL的动态数组，在运行时能根据需要改变数组大小。由于它以数组形式存储，也就是说它的内存空间是连续的，所以索引可以在常数时间内完成，但是在中间进行插入和删除操作会造成内存块的复制。另外，如果数组后面的内存空间不够，需要重新申请一块足够大的内存。这些都会影响vector的效率。 vector容器是一个模板类，能存放任何类型的对象。 1. 定义 其示例如表3.1所示。 表3.1vector定义示例 功能例子说明 定义int型数组 vector a;默认初始化，a为空 vector b(a);用a定义b vector a(100);a有100个值为0的元素 vector a(100, 6);100个值为6的元素 定义string型数组 vector a(10,\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"null\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\");10个值为null的元素 vector vec(10,\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"hello\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\");10个值为hello的元素 vectorb(a.begin(), a.end());b是a的复制 定义结构型数组struct point { int x, y; }; vector a;a用来存坐标 用户还可以定义多维数组，例如定义一个二维数组： vector a［MAXN］; 它的**维大小是固定的MAXN，第二维是动态的。用这个方式可以实现图的邻接表存储，细节见本书10.2节。 2. 常用操作 vector的常用操作如表3.2所示。 表3.2vector的常用操作 功能例子说明 赋值a.push_back(100);在尾部添加元素 元素个数int size=a.size();元素个数 续表 功能例子说明 是否为空bool isEmpty=a.empty();判断是否为空 打印cout<