ACM/ICPC競(jìng)賽中動(dòng)態(tài)數(shù)組vector容器的教學(xué)探討

趙磊　魏書堤　陳堅(jiān)禎　陳瓊　姚麗君

摘 要： 動(dòng)態(tài)數(shù)組vector容器在日常程序設(shè)計(jì)課程中沒有涉及，而在ACM/ICPC競(jìng)賽中卻經(jīng)常被用到，因此有必要予以介紹。文章從創(chuàng)建一個(gè)vector對(duì)象，在vector對(duì)象中插入元素，在vector對(duì)象中刪除元素，修改vector對(duì)象中元素的值，vector容器的常用成員函數(shù)和算法等方面詳細(xì)地介紹了vector容器的使用。學(xué)生通過(guò)學(xué)習(xí)，能對(duì)vector容器有一個(gè)全面的認(rèn)識(shí)，為其參加ACM/ICPC競(jìng)賽提供幫助。

關(guān)鍵詞： 動(dòng)態(tài)數(shù)組； vector容器； 程序設(shè)計(jì)； ACM/ICPC

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM International Collegiate Programming Contest，簡(jiǎn)稱ACM/ICPC），是全球規(guī)模最大，最有影響力的大學(xué)生程序設(shè)計(jì)競(jìng)賽。競(jìng)賽的目的是讓大學(xué)生運(yùn)用計(jì)算機(jī)來(lái)充分展示自己分析問題和解決問題的能力。ACM/ICPC要求以團(tuán)隊(duì)的形式參賽，每個(gè)隊(duì)伍由3名隊(duì)員組成。每隊(duì)使用一臺(tái)計(jì)算機(jī)，選手在全封閉的環(huán)境內(nèi)（不能有任何通訊設(shè)備，可以攜帶任何紙質(zhì)資料）連續(xù)5個(gè)小時(shí)對(duì)8-11個(gè)問題進(jìn)行解答。競(jìng)賽采用英文命題，題目涉及面非常廣。需要參賽學(xué)生具有扎實(shí)的基本功、良好的分析問題的能力、較好的團(tuán)隊(duì)協(xié)作能力和壓力下編寫程序的能力。該競(jìng)賽為學(xué)生提供了一個(gè)學(xué)習(xí)和使用程序設(shè)計(jì)語(yǔ)言/算法的完整實(shí)踐模式，使學(xué)生以精通編程為榮，形成一個(gè)積極向上的學(xué)習(xí)氛圍[1]。

ACM競(jìng)賽中很多時(shí)候會(huì)用到STL。STL（標(biāo)準(zhǔn)模板庫(kù)）是C++標(biāo)準(zhǔn)程序庫(kù)的核心[2]，定義了一系列用途廣泛的模板類和模板函數(shù)，它們可以用來(lái)實(shí)現(xiàn)許多通用的算法和數(shù)據(jù)結(jié)構(gòu)。標(biāo)準(zhǔn)模板庫(kù)STL的核心內(nèi)容是3個(gè)基本組件：容器、算法和迭代器。STL將這些組件結(jié)合在一起為許多程序設(shè)計(jì)難題提供實(shí)際可行的解決辦法。本文和大家一起探討STL容器中的動(dòng)態(tài)數(shù)組vector容器。

1 vector容器的基本運(yùn)算

動(dòng)態(tài)數(shù)組vector容器是可以根據(jù)需要改變大小的數(shù)組。因?yàn)樵贑++中數(shù)組的大小在編譯時(shí)是固定的，所以程序在運(yùn)行時(shí)不能改變數(shù)組的大小來(lái)適應(yīng)程序需求。但是vector容器可以根據(jù)需要來(lái)分配內(nèi)存，從而解決這個(gè)問題[2]。在創(chuàng)建vector容器前，先要在程序開頭處加上#include頭文件以包含所需要的文件，同時(shí)還需要使用std名字空間using namespace std。下面介紹vector容器的幾個(gè)基本運(yùn)算。

1.1 創(chuàng)建一個(gè)vector對(duì)象

創(chuàng)建vector對(duì)象就像申明一個(gè)變量一樣，例如有如下代碼：

vector v1；

此代碼申明了一個(gè)整型的vector對(duì)象，對(duì)象的名稱為v1。又例如代碼：

vector v2；

此代碼申明了一個(gè)字符型的vector對(duì)象，對(duì)象的名稱為v2。vector是一個(gè)模板類，vector是一個(gè)類似int a[]的整數(shù)數(shù)組，而vector就是類似char a[]的字符串?dāng)?shù)組[3]。vector容器可以使用自定義數(shù)據(jù)類型，例如在vector<自定義的結(jié)構(gòu)>v3的代碼中，尖括號(hào)<>中的數(shù)據(jù)類型可以使用自定義的數(shù)據(jù)類型。創(chuàng)建了vector對(duì)象后，就可以向它添加數(shù)值了。

1.2 在vector對(duì)象中插入元素

vector容器帶有一個(gè)push_back（）函數(shù)，該函數(shù)可以向vector對(duì)象的末尾添加數(shù)值。例如代碼：

v1.push_back（0）；

v1.push_back（1）；

for （int i=2； i<=10； i++） v1.push_back（i）；

上面第一行代碼在vector對(duì)象v1的末尾添加了一個(gè)數(shù)值0，第二行代碼在vector對(duì)象v1的末尾添加了一個(gè)數(shù)值1，后面的循環(huán)連續(xù)在vector對(duì)象v1的末尾添加數(shù)值2到10。

在vector容器中插入元素除了push_back（）方法提供了一個(gè)函數(shù)insert（），這個(gè)函數(shù)有以下三種用法。

⑴ 在指定位置loc前插入值為val的元素，返回指向這個(gè)元素的迭代器：

iterator insert（iterator loc， type val）；

⑵ 在指定位置loc前插入num個(gè)值為val的元素：

void insert（iterator loc， size_type num， type val）；

⑶ 在指定位置loc前插入?yún)^(qū)間[start， end）的所有元素：

void insert（iterator loc， iterator start， iterator end）；

這里先簡(jiǎn)單介紹下STL中另一個(gè)基本組件迭代器，迭代器是一種允許程序員檢查容器內(nèi)元素，并實(shí)現(xiàn)元素遍歷的數(shù)據(jù)類型。標(biāo)準(zhǔn)庫(kù)為每一種標(biāo)準(zhǔn)容器（包括vector）定義了一種迭代器類型。迭代器類型提供了比下標(biāo)操作更一般化的方法。所有的標(biāo)準(zhǔn)庫(kù)容器都定義了相應(yīng)的迭代器類型，而只有少數(shù)容器支持下標(biāo)操作。因?yàn)榈鲗?duì)所有的容器都適用，現(xiàn)代C++程序更傾向于使用迭代器而不是下標(biāo)操作訪問容器元素，即使對(duì)支持下標(biāo)操作的vector類型也這樣。

例如語(yǔ)句：vector：：iterator iter；

這條語(yǔ)句定義了一個(gè)名為iter的變量，它的數(shù)據(jù)類型是由vector定義的iterator類型。每個(gè)標(biāo)準(zhǔn)庫(kù)容器類型都定義了一個(gè)名為iterator的成員，這里的iterator與迭代器實(shí)際類型的含義相同。

在下面的例子中我們定義一個(gè)迭代器p，p指向vector容器的開始位置，然后將p后移兩個(gè)位置，使用insert（）函數(shù)的第二種用法在p位置前插入兩個(gè)100，代碼如下：

vector：：iterator p=v1.begin（）；

p=p+2；

v1.insert（p， 2 ， 100）；

1.3 在vector對(duì)象中刪除元素

在vector對(duì)象中刪除元素的方法與插入元素比較類似，這里介紹三種方法。

⑴ 使用pop_back（）方法移除最后一個(gè)元素，與push_back（）相對(duì)應(yīng)。

⑵ 刪除迭代器所指元素。

iterator erase（iterator loc）；

⑶ 刪除區(qū)間[start， end]的所有元素。

iterator erase（iterator start， iterator end）；

例如在v1中刪除迭代器p和p后三個(gè)位置之間的元素，可以使用如下代碼。

v1.erase（p， p+3）；

1.4 修改vector對(duì)象中元素的值

雖然vector是動(dòng)態(tài)的，但仍然可以使用標(biāo)準(zhǔn)的數(shù)組下標(biāo)運(yùn)算來(lái)訪問數(shù)組中的元素。例如下面代碼：

v1[1]=v1[1]*v1[1]；

v1[2]=v1[2]+100；

上面第一行代碼將vector對(duì)象v1的第一個(gè)元素平方，第二行代碼將vector對(duì)象v1的第二元素的值加100。

當(dāng)然也可以使用迭代器來(lái)訪問或修改數(shù)組中的元素，下面代碼完成上面代碼一樣的功能。

vector：：iterator p=v1.begin（）；

*p=*p**p；

p++；

*p=*p+100；

需要注意的是，vector的下標(biāo)運(yùn)算只能改變或者獲取已有的元素的值，不能往vector里添加元素。

2 vector容器的常用成員函數(shù)和算法

2.1 獲得vector對(duì)象的大小函數(shù)size（）函數(shù)

下面代碼輸出v1容器中的每個(gè)元素。

for （i=0；i

cout << v1[i] << " "；

2.2 獲得vector對(duì)象中第一個(gè)元素begin（）函數(shù)和最后一個(gè)元素end（）函數(shù)

下面代碼定義迭代器p1指向v1容器的開始，定義迭代器p2指向v1容器的結(jié)束。

vector：：iterator p1=v1.begin（）；

vector：：iterator p2=v1.end（）；

2.3 判斷vector對(duì)象是否為空empty（）函數(shù)，為空返回true，否則返回false

下面代碼判斷容器v1是否為空，如果容器為空則輸出“vector is empty！”。

if（v1.empty（））

cout<<"vector is empty！"；

2.4 清空vector容器中的所有元素clear（）函數(shù)

下面代碼清空容器v1中的所有元素。

v1.clear（）；

2.5 交換兩個(gè)相同類型vector容器中內(nèi)容的swap（）函數(shù)

下面代碼將v1容器和v2容器的內(nèi)容進(jìn)行交換。

vector v1（10）；

vector v2（20）；

v1.swap（v2）；

2.6 對(duì)vector容器中元素進(jìn)行排序的sort（）算法

下面代碼對(duì)容器v1中的所有元素從小到大進(jìn)行排序。

sort（v1.begin（），v1.end（））；

如果需要從大到小排序的話，要自定義比較函數(shù)。

2.7 將vector容器中元素進(jìn)行的reverse（）算法

下面代碼對(duì)容器v1中的所有元素反向排列

reverse（v1.begin（），v1.end（））；

3 結(jié)束語(yǔ)

vector容器在日常的程序設(shè)計(jì)教學(xué)中并沒有涉及到，但在ACM/ICPC競(jìng)賽中經(jīng)常用到。本文詳細(xì)地介紹了vector容器的基本運(yùn)算、常用相關(guān)函數(shù)和算法，學(xué)生通過(guò)本文方法的學(xué)習(xí)，能對(duì)vector容器有一個(gè)全面的認(rèn)識(shí)，再加以練習(xí)就能熟練掌握vector容器的使用，掌握好vector容器對(duì)學(xué)習(xí)其他容器和算法能有較大幫助，并能提高學(xué)生ACM/ICPC競(jìng)賽的程序設(shè)計(jì)能力。

參考文獻(xiàn)（References）：

[1] 趙磊，魏書堤，陳堅(jiān)禎，陳瓊，姚麗君.普通本科院校ACM/

ICPC競(jìng)賽教學(xué)的探討[J].電腦知識(shí)與技術(shù)，2015.2：129-130，136

[2] Nicolai M.Josuttis.C++標(biāo)準(zhǔn)程序庫(kù)[M].華中科技大學(xué)出版

社，2002.9：73

[3] 劉汝佳.算法競(jìng)賽入門經(jīng)典（第二版）[M].清華大學(xué)出版社，

2014.