ACM/ICPC競賽中動態數組vector容器的教學探討

趙磊　魏書堤　陳堅禎　陳瓊　姚麗君

摘 要： 動態數組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頭文件以包含所需要的文件，同時還需要使用std名字空間using namespace std。下面介紹vector容器的幾個基本運算。

1.1 創建一個vector對象

創建vector對象就像申明一個變量一樣，例如有如下代碼：

vector v1；

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

vector v2；

此代碼申明了一個字符型的vector對象，對象的名稱為v2。vector是一個模板類，vector是一個類似int a[]的整數數組，而vector就是類似char a[]的字符串數組[3]。vector容器可以使用自定義數據類型，例如在vector<自定義的結構>v3的代碼中，尖括號<>中的數據類型可以使用自定義的數據類型。創建了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：：iterator iter；

這條語句定義了一個名為iter的變量，它的數據類型是由vector定義的iterator類型。每個標準庫容器類型都定義了一個名為iterator的成員，這里的iterator與迭代器實際類型的含義相同。

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

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

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：：iterator p=v1.begin（）；

*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：：iterator p1=v1.begin（）；

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

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 v1（10）；

vector v2（20）；

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.