ACM/ICPC竞赛中动态数组vector容器的教学探讨
2018-10-17赵磊魏书堤陈坚祯陈琼姚丽君
赵磊 魏书堤 陈坚祯 陈琼 姚丽君
摘 要： 动态数组vector容器在日常程序设计课程中没有涉及，而在ACM/ICPC竞赛中却经常被用到，因此有必要予以介绍。文章从创建一个vector对象，在vector对象中插入元素，在vector对象中删除元素，修改vector对象中元素的值，vector容器的常用成员函数和算法等方面详细地介绍了vector容器的使用。学生通过学习，能对vector容器有一个全面的认识，为其参加ACM/ICPC竞赛提供帮助。
关键词： 动态数组； vector容器； 程序设计； ACM/ICPC
中图分类号：TP312 文献标志码：A 文章编号：1006-8228（2018）08-64-03
Discussion on the teaching of dynamic array vector container in ACM/ICPC competition
Zhao Lei， Wei Shudi， Chen Jianzhen， Chen Qiong， Yao Lijun
（Computer department of Hengyang Normal University， Hengyang， Hunan 421001， China）
Abstract： The dynamic array vector container is not involved in the daily programming course， but is often used in the ACM/ICPC competitions， so it is necessary to be introduced. In this paper， the use of the vector container is introduced in detail， such as creating a vector object， inserting elements in the vector object， deleting elements in the vector object， modifying the value of the elements in the vector object， the common member functions and algorithms of the vector container. Through learning， students can have a comprehensive understanding of the vector container， it's helpful for them to participate in the ACM/ICPC competition.
Key words： dynamic array； vector container； program design； ACM/ICPC
0 引言
ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM/ICPC），是全球规模最大，最有影响力的大学生程序设计竞赛。竞赛的目的是让大学生运用计算机来充分展示自己分析问题和解决问题的能力。ACM/ICPC要求以团队的形式参赛，每个队伍由3名队员组成。每队使用一台计算机，选手在全封闭的环境内（不能有任何通讯设备，可以携带任何纸质资料）连续5个小时对8-11个问题进行解答。竞赛采用英文命题，题目涉及面非常广。需要参赛学生具有扎实的基本功、良好的分析问题的能力、较好的团队协作能力和压力下编写程序的能力。该竞赛为学生提供了一个学习和使用程序设计语言/算法的完整实践模式，使学生以精通编程为荣，形成一个积极向上的学习氛围[1]。
ACM竞赛中很多时候会用到STL。STL（标准模板库）是C++标准程序库的核心[2]，定义了一系列用途广泛的模板类和模板函数，它们可以用来实现许多通用的算法和数据结构。标准模板库STL的核心内容是3个基本组件：容器、算法和迭代器。STL将这些组件结合在一起为许多程序设计难题提供实际可行的解决办法。本文和大家一起探讨STL容器中的动态数组vector容器。
1 vector容器的基本运算
动态数组vector容器是可以根据需要改变大小的数组。因为在C++中数组的大小在编译时是固定的，所以程序在运行时不能改变数组的大小来适应程序需求。但是vector容器可以根据需要来分配内存，从而解决这个问题[2]。在创建vector容器前，先要在程序开头处加上#include
1.1 创建一个vector对象
创建vector对象就像申明一个变量一样，例如有如下代码：
vector
此代码申明了一个整型的vector对象，对象的名称为v1。又例如代码：
vector
此代码申明了一个字符型的vector对象，对象的名称为v2。vector是一个模板类，vector
1.2 在vector对象中插入元素
vector容器带有一个push_back（）函数，该函数可以向vector对象的末尾添加数值。例如代码：
v1.push_back（0）；
v1.push_back（1）；
for （int i=2； i<=10； i++） v1.push_back（i）；
上面第一行代码在vector对象v1的末尾添加了一个数值0，第二行代码在vector对象v1的末尾添加了一个数值1，后面的循环连续在vector对象v1的末尾添加数值2到10。
在vector容器中插入元素除了push_back（）方法提供了一个函数insert（），这个函数有以下三种用法。
⑴ 在指定位置loc前插入值为val的元素，返回指向这个元素的迭代器：
iterator insert（iterator loc， type val）；
⑵ 在指定位置loc前插入num个值为val的元素：
void insert（iterator loc， size_type num， type val）；
⑶ 在指定位置loc前插入区间[start， end）的所有元素：
void insert（iterator loc， iterator start， iterator end）；
这里先简单介绍下STL中另一个基本组件迭代器，迭代器是一种允许程序员检查容器内元素，并实现元素遍历的数据类型。标准库为每一种标准容器（包括vector）定义了一种迭代器类型。迭代器类型提供了比下标操作更一般化的方法。所有的标准库容器都定义了相应的迭代器类型，而只有少数容器支持下标操作。因为迭代器对所有的容器都适用，现代C++程序更倾向于使用迭代器而不是下标操作访问容器元素，即使对支持下标操作的vector类型也这样。
例如语句：vector
这条语句定义了一个名为iter的变量，它的数据类型是由vector
在下面的例子中我们定义一个迭代器p，p指向vector容器的开始位置，然后将p后移两个位置，使用insert（）函数的第二种用法在p位置前插入两个100，代码如下：
vector
p=p+2；
v1.insert（p， 2 ， 100）；
1.3 在vector对象中删除元素
在vector对象中删除元素的方法与插入元素比较类似，这里介绍三种方法。
⑴ 使用pop_back（）方法移除最后一个元素，与push_back（）相对应。
⑵ 删除迭代器所指元素。
iterator erase（iterator loc）；
⑶ 删除区间[start， end]的所有元素。
iterator erase（iterator start， iterator end）；
例如在v1中删除迭代器p和p后三个位置之间的元素，可以使用如下代码。
v1.erase（p， p+3）；
1.4 修改vector对象中元素的值
虽然vector是动态的，但仍然可以使用标准的数组下标运算来访问数组中的元素。例如下面代码：
v1[1]=v1[1]*v1[1]；
v1[2]=v1[2]+100；
上面第一行代码将vector对象v1的第一个元素平方，第二行代码将vector对象v1的第二元素的值加100。
当然也可以使用迭代器来访问或修改数组中的元素，下面代码完成上面代码一样的功能。
vector
*p=*p**p；
p++；
*p=*p+100；
需要注意的是，vector的下标运算只能改变或者获取已有的元素的值，不能往vector里添加元素。
2 vector容器的常用成员函数和算法
2.1 获得vector對象的大小函数size（）函数
下面代码输出v1容器中的每个元素。
for （i=0；i cout << v1[i] << " "； 2.2 获得vector对象中第一个元素begin（）函数和最后一个元素end（）函数 下面代码定义迭代器p1指向v1容器的开始，定义迭代器p2指向v1容器的结束。 vector vector 2.3 判断vector对象是否为空empty（）函数，为空返回true，否则返回false 下面代码判断容器v1是否为空，如果容器为空则输出“vector is empty！”。 if（v1.empty（）） cout<<"vector is empty！"； 2.4 清空vector容器中的所有元素clear（）函数 下面代码清空容器v1中的所有元素。 v1.clear（）； 2.5 交换两个相同类型vector容器中内容的swap（）函数 下面代码将v1容器和v2容器的内容进行交换。 vector vector v1.swap（v2）； 2.6 对vector容器中元素进行排序的sort（）算法 下面代码对容器v1中的所有元素从小到大进行排序。 sort（v1.begin（），v1.end（））； 如果需要从大到小排序的话，要自定义比较函数。 2.7 将vector容器中元素进行的reverse（）算法 下面代码对容器v1中的所有元素反向排列 reverse（v1.begin（），v1.end（））； 3 结束语 vector容器在日常的程序设计教学中并没有涉及到，但在ACM/ICPC竞赛中经常用到。本文详细地介绍了vector容器的基本运算、常用相关函数和算法，学生通过本文方法的学习，能对vector容器有一个全面的认识，再加以练习就能熟练掌握vector容器的使用，掌握好vector容器对学习其他容器和算法能有较大帮助，并能提高学生ACM/ICPC竞赛的程序设计能力。 参考文献（References）： [1] 赵磊，魏书堤，陈坚祯，陈琼，姚丽君.普通本科院校ACM/ ICPC竞赛教学的探讨[J].电脑知识与技术，2015.2：129-130，136 [2] Nicolai M.Josuttis.C++标准程序库[M].华中科技大学出版 社，2002.9：73 [3] 刘汝佳.算法竞赛入门经典（第二版）[M].清华大学出版社， 2014.
