C++ Primer 标准库vector

专栏简介：本专栏主要面向C++初学者，解释C++的一些基本概念和基础语言特性，涉及C++标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级程序设计技术。希望对读者有帮助！

3.3标准库Vector

标准库类型vector表示对象的集合,其中所有对象的类型都相同。集合中的每个对象都有一个与之对应的索引,索引用于访问对象。因为vector“容纳着“其他对象,所以它也常被称作容器(container)。

要想使用vector,必须包含适当的头文件。在后续的例子中,都将假定做了如下using声明;

#include<vector>
usingstd::vector;

C++语言既有类模板(classtemplate),也有函数模板,其中vector是一个类模板。只有对C++有了相当深入的理解才能写出模板,事实上,我们直到第16章才会学习如何自定义模板。幸运的是,即使还不会创建模板,我们也可以先试着用用它。

模板本身不是类或函数,相反可以将模板看作为编译器生成类或函数编写的一份说明。编译器根据模板创建类或函数的过程称为实例化(instantiation),当使用模板时,需要指出编译器应把类或函数实例化成何种类型。

对于类模板来说,我们通过提供一些额外信息来指定模板到底实例化成什么样的类,需要提供哪些信息由模板决定。提供信息的方式总是这样:即在模板名字后面跟一对尖括号,在括号内放上信息。
以vector为例,提供的额外信息是vector内所存放对象的类型:

    vector<int> ivec;//ivec保存int类型的对象
    vector<Sales_item> Sales_vec//保孙Salesitem类型的对象
    vector<vector<string>> file;//该向量的元素是vectoz对象

在上面的例子中,编详器根据模板vector生成了三种不同的类型,vector、vector<Sales_item>和 vector<vector>。vector是模板而非类型,由vector生成的类型必须包含vector中元素的类型,例如yector。

vector能容纳绝大多数类型的对象作为其元素,但是因为引用不是对象,所以不存在包含引用的vector。除此之外,其他大多数(非引用内置类型和类类型都可以构成vector对象,甚至组成vector的元素也可以是vector。

需要指出的是,在早期版本的C++标准中如果vector的元素还是vector(或者其他模板类型),则其定义的形式与现在的C++11新标准略有不同。过去,必须在外层vector对象的右尖括号和其元素类型之间添加一个空格,如应该写成vector<vector >而非vector<vector>

WARNNING ：某些编译器可能仍需以老式的声明语句来处理元素为vector的vector对象，如vector<vector > 。

定义和初始化vector对象通

和任何一种类类型一样,vector模板控制着定义和初始化向量的方法。表3.4列出了定义vector对象的常用方法。

表3.4:初始化vector对象的方法

可以默认初始化vector对象,从而创建一个指定类型的空 vector:

vector<string>syec; //默认初始化,svec不含任何元素

看起来空vector好像没什么用,但是很快我们就会知道程序在运行时可以很高效地往vector对象中添加元素。事实上,最常见的方式就是先定义一个空vector,然后当运行时获取到元素的值后再逐一添加。

当然也可以在定义vector对象时指定元素的初始值。例如,允许把一个vector对象的元素拷贝给另外一个vector对象。此时,新vector对象的元素就是原vector对象对应元素的副本。注意两个vector对象的类型必须相同:

vector<int> ivec;//初始状态为空
//在此处给ivec添加一些值
vector<int> ivec2(ivec);//把tvec的元素拷贝给ivec2
vector<int> tvec3=ivecy;//把ivec的元素拷贝给ivec3
vector<string> svec(tvec2);//错误:svec的元素是string对象,不是tnt

列表初始化vector对象

C++11新标准还提供了另外一种为vector对象的元素赋初值的方法,即列表初始化。此时,用花括号担起来的0个或多个初始元素值被赋给vector对象:

vector<string> articles = {“a“,“an“,“the“};

上述vector对象包含三个元素:第一个是字符串“a“,第二个是字符串“an“,最后一个是字符串“the“。

之前已经讲过,C++语言提供了几种不同的初始化方式。在大多数情况下这些初始化方式可以相互等价地使用,不过也并非一直如此。目前已经介绍过的两种例外情况是:其一,使用拷贝初始化时(即使用=时),只能提供一个初始值;其二,如果提供的是一个类内初始值,则只能使用拷贝初始化或使用花括号的形式初始化。第三种特殊的要求是,如果提供的是初始元素值的列表,则只能把初始值都放在花括号里进行列表初始化,而不能放在圆括号里:

vector<string>V1{“a“,“anm,“the“};//列表初始化
vector<string>v2(“a“,“an“,“the“);//错误

创建指定数量的元素

还可以用vector对象容纳的元素数量和所有元素的统一初始值来初始化vector对象:

vector<int>ivec(10,-1)}//10个int类型的元素,每个都被初始化为-1
vector<string>svec(10,“hi!“);//10个string类型的元素,
                            //每个都被初始化为“hi1

值初始化

通常情况下,可以只提供vector对象容纳的元素数量而不用略去初始值。此时库会创建一个值初始化的(value-initialized)元素初值,并把它赋给容器中的所有元素。这个初值由vector对象中元素的类型决定。

如果vector对象的元素是内置类型,比如int,则元素初始值自动设为0。如果元素是桅种类类型,比如string,则元素由类默认初始化:

vector<int>ivec(10);     //10个元素,每个都初始化为0
vector<string>svec(10);  //10个元素,参个都是空string对象

对这种初始化的方式有两个特殊限制:其一,有些类要求必须明确地提供初始值,如果vector对象中元素的类型不支持默认初始化,我们就必须提供初始的元素值.对这种类型的对象来说,只提供元素的数量而不设定初始值无法完成初始化工作。

其二,如果只提供了元素的数量而没有设定初始值,只能使用直接初始化:

vector<int>vi=10;//错误:必须使用直接初始化的形式指定向量大小

这里的10是用来说明如何初始化vector对象的,我们用它的本意是想创建含有10个值初始化了的元素的vector对象,而非把数字10“拷贝“到vector中。因此,此时不定使用拷贝初始化。

列表初始值还是元素数量?

在某些情况下,初始化的真实含义依赖于传递初始值时用的是花括号还是圆括号。例如,用一个整数来初始化vector时,整数的含义可能是vector对象的容量也可能是元素的值。类似的,用两个整数来初始化vector时,这两个整数可能一个是vector对象的容量,另一个是元素的初值,也可能它们是容量为2的vector对象中两个元素的初值。通过使用花括号或圆括号可以区分上述这些含义:

vector<int>v1(10);//vl有10个元素,每个的值都是0
vector<int>v2{10};//v2有1个元素,该元素的值是10
vector<int>v3(10,1);//v3有10个元素,每个的值都是1
vector<int>v4{10,1};//v4有2个元素,值分别是10和1

如果用的是圆括号,可以说提供的值是用籼构造Cconstruct)vectoz对象的。例如,v1的初始值说明了vector对象的容量;v3的两个初始值则分别说明了vector对象的容量和元素的初值。

如果用的是花括号,可以表述成我们想列表初始化(listinitialize)该vector对象。也就是说,初始化过程会尽可能地把花括号内的值当成是元素初始值的列表来处理,只有在无法执行列表初始化时才会考虑其他初始化方式。在上例中,给v2和v4提供的初始
值都能作为元素的值,所以它们都会执行列表初始化,vector对象v2包含一个元素而vector对象v4包含两个元素。

另一方面,如果初始化时使用了花括号的形式但是提供的值又不能用来列表初始化,就要考虑用这样的值来构造vector对象了。例如,要想列表初始化一个含有string对象的vector对象,应该提供能赋给string对象的初值。此时不难区分到底是要列表初始化vector对象的元素还是用给定的容量值来构造vector对象:

vector<string>v5{“hi“};      //列表初始化:v5有一个元素
vector<string>v6(“hi“);      //错误:不能使用字符串字面值构建vector对象
vector<string>v7{10};        //v7有10个默认初始化的元素
vector<string>V8{10,"hin1"}; //v8有10个值为vhi“的元素

尽管在上面的例子中除了第二条语句之外都用了花括号,但其实只有v5是列表初始化。要想列表初始化vector对象,花括号里的值必须与元素类型相同。显然不能用int初始化string对象,所以v7和v8提供的值不能作为元素的初始值。确认无法执行列表初始化后,编译器会尝试用默认值初始化vector对象。

向vector对象中添加元素

对vector对象来说,直接初始化的方式适用于三种情况:初始值已知且数量较少、初始值是另一个vector对象的副本、所有元素的初始值都一样。然而更常见的情况是:创建一个vectozr对象时并不清楚实际所需的元素个数,元素的值也经常无法确定。还有些时候即使元素的初值已知,但如果这些值总量较大而各不相同,那么在创建vector对象的时候执行初始化操作也会显得过于烦琐。

举个例子,如果想创建一个vector对象令其包含从0到9共10个元素,使用列表初始化的方法很容易做到这一点;但如果vector对象包含的元素是从0到99或者从0到999呢?这时通过列表初始化把所有元素都一一罗列出来就不太合适了。对于此例来说,更好的处理方法是先创建一个空vector,然后在运行时再利用vector的成员函数push_back向其中添加元素。push_back负责把一个值当vector对象的尾元素“压到(push)“vector对象的“尾端(back)“。例如:

vector<int>v2;//空vector对象
for(int i=0;i!=100;++i)
    v2.Push_back();//依次把整数值放到v2尾端
    //循环结束后v2有100个元素,值从0到99

在上例中,尽管知道vector对象最后会包含100个元素,但在一开始还是把它声明成空vector,在每次迭代时才顺序地把下一个整数作为v2的新元素添加给它。

同样的,如果直到运行时才能知道vector对象中元素的确切个数,也应该使用刚刚这种方法创建vector对象并为其赋值。例如,有时需要实时读入数据然后将其赋了vector对象:

//从标准输入中读取单词,将其作为vector对象的元素存傅
string word;
vector<string> text;//空vector对象
while(cin>>word) {
    text.push_back(word);//把word添加到text后面
}

和之前的例子一样,本例也是先创建一个宇vector,之后依次读入未知数量的值并保存到text中。

关键概念:vector对象能高效增长

C++标准要求vector应该能在运行时高效快速地添加元素。因此既然vector对象能高效地增长,那么在定义vector对象的时候设定其大小也就没什么必要了,事实上如果这么做性能可能更差。只有一种例外情况,就是所有(all)元素的值都一样。一旦元素的值有所不同,更有效的办法是先定义一个空的vector对象,再在运行时闭其中添加具体值。此外,vector还提供了方法,允许我们进一步提升动态添加元素的性能。

开始的时候创建空的vector对象,在运行时再动态添加元素,这一做法与C语言及其他大多数语言中内置数组类型的用法不同。特别是如果用惯了C或者Java,可以预计在创建vector对象时顺便指定其容量是最好的。然而事实上,通常的情况是恰

向vector对象添加元素蕴含的编程假定

由于能高效便捷地向vector对象中添加元素,很多编程工作被极大简化了。然而,这种简便性也伴随着一些对编写程序更高的要求:其中一条就是必须要确保所写的循环正确无误,特别是在循环有可能改变vector对象容量的时候。

随着对vector的更多使用,我们还会逐渐了解到其他一些隐含的要求,其中一条是现在就要指出的:如果循环体内部包含有向vector对象添加元素的语句,则不能使用范围for循环。

WARNING:范围for语句体内不应改变其所造历序列的大小。

其他vector操作

除了push_back之外，vector还提供了几种其他操作，大多数都和string的相关操作类似，表3.5列出了其中比较重要的一些。

表3.5:vector支持的操作

访问vector对象中元素的方法和访问string对象中字符的方法差不多,也是通过元素在vector对象中的位置。例如,可以使用范围for语句处理vector对象中的所有元素:

vector<int>V{112,3,4,5,6,718,917}
for(auto&:v)//对于中的每个元素(注意:i是一个引用)
    i*=i;//求元素值的平方
for(auto i:v)//对于中的每个元素
cout<<i<<" ";//输出该元素
cout<<endl;

第一个循环把控制变量i定义成引用类型,这样就能通过i给v的元素赋值,其中i的类型由auto关键字指定。这里用到了一种新的复合赋值运算符。如我们所知,+=把左侧运算对象和右侧运算对象相加,结果存入左侧运算对象;类似的,*=把左侧运算对象和右侧运算对象相乘,结果存入左侧运算对象。最后,第二个循环输出所有元素。

vector的empty和size两个成员与string的同名成功能完全一致:empty检查vector对象是否包含元素然后返回一个布尔值;size则返回vector对象中元素的个数,返回值的类型是由vector定义的size_type类型。

各个相等性运算符和关系运算符也与string的相应运算符功能一致。两个vector对象相等当且仅当它们所含的元素个数相同,而且对应位置的元素值也相同。关系运算符依照字典顺序进行比较:如果两个vector对象的容量不同,但是在相同位置上的元素值都一样,则元素较少的vector对象小于元素较多的vector对象;若元素的值有区别,则vector对象的大小关系由第一对相异的元素值的大小关系决定。

只有当元素的值可比较时,vector对象才能被比较。一些类,如string等,确实定义了自己的相等性运算符和关系运算符。

计算vector内对象的索引

使用下标运算符能获取到指定的元素。和string一样,vector对象的下标也是从0开始计起,下标的类型是相应的size_type类型。只要vector对象不是一个常量,就能向下标运算符返回的元素赋值。此外,也能通过计算得到vector内对象的索引,然后直接获取索引位置上的元素。

举个例子,假设有一组成绩的集合,其中成绩的取值是从0到100。以10分为一个分数段,要求统计各个分数段各有多少个成绩。显然,从0到100总共有101种可能的成绩取值,这些成绩分布在11个分数段上:每10个分数构成一个分数段,这样的分数段有10个,额外还有一个分数段表示满分100分。这样第一个分数段将统计成绩在0到9之间的数量;第二个分数段将统计成绩在10到19之间的数量,以此类推。最后一个分数段统计满分100分的数量。

按照上面的描述,如果输入的成绩如下:

42 65 95 100 39 67 95 76 88 76 83 92 76 93

则输出的结果应该是:

0 0 0 1 1 0 2 3 2 4 1

结果显示:成绩在30分以下的没有、30分至39分有1个、40分至49分有1个、50分全59分没有、60分至69分有2个、70分至79分有3个、80分至89分有2个、90分至99分有4个,还有1个是满分。

在具体实现时使用一个含有11个元素的vector对象,每个元素分别用于统计各个分数段上出现的成绩个数。对于某个成绩来说,将其除以10就能得到对应的分数段索引。注意:两个整数相除,结果还是整数,余数部分被自动忽略掉了。例如,42/10=4、65/10-6、100/10=10等。一旦计算得到了分数段索引,就能用它作为vector对象的下标,进而获取该分数段的计数值并加1:

//以10分为一个分数段统计成绩的数量:0~9,10~19,..,90~99,100
vector<unsigned> scores(11,0); //11个分数段,全都初始化为0
unsigned grade;
while(cin>>grade)《//读取成绩
    if(grzade<=100)//只处理有效的成绩
        ++scores[grade/10];//将对应分数段的计数值加1

在上面的程序中,首先定义了一个vector对象存放各个分数段上成绩的数量。此例中,由于初始状态下每个元素的值都相同,所以我们为vector对象申请了11个元素,并把所有元素的初始值都设为0。while语句的条件部分负责读入成绩,在循环体内部首先检查读入的成绩是否合法(即是否小于等于100分),如果合法,将成绩对应的分数段的计数值加1。

执行计数值累加的那条语句很好地体现了C++程序代码的简洁性。表达式

++scores[grade/10];//将当前分数段的计数值加1

等价于

auto ind = grade/10;//得到分数段索引
scores[tnd]=scores[ind]+1;//将计数值加1

上述语句的含义是:用grade除以10来计算成绩所在的分数段,然后将所得的结果作为变量scores的下标。通过运行下标运算获取该分数段对应的计数值,因为新出现了一个属于该分数段的成绩,所以将计数值加1。

如前所述,使用下标的时候必须清楚地知道它是否在合理范围之内。在这个程序里,我们事先确认了输入的成绩确实在0到100之间,这样计算所得的下标就一定在0到10之间,属于0到scores.size()-1规定的有效范围,一定是合法的。

不能用下标形式添加元素

刚接触C++语言的程序员也许会认为可以通过vector对象的下标形式来添加元素,事实并非如此。下面的代码试图为vector对象ivec添加10个元素:

vector<int>tvec;//空vector对象
for(decltype(ivec.size())ix = 0;ix!=10;++ix)
    ivec[ix]=ix;//严重错误:tvec不包吴任何元素

然而,这段代码是错误的:ivec是一个空vector,根本不包含任何元素,当然也就不能通过下标去访问任何元素!如前所述,正确的方法是使用push_bacK:

for(decltype(tvec.size())ix=0;ix!=10;++ix)
    ivec.push_back(ix); //正确:添加一个新元素,该元素的值是ix

vestor兑现(以及string对象)的下标运算答可用于访问已存在的元素。而不能用于添加元素。

提示:只能对确知已存在的元素执行下标操作!

关于下标史须明确的一点是;只能对确知已存在的元素执行下标操作。例如,

vector<int>ivec;//空vector对象
cout<<ivec[013//错误:ivec不艮含任何元素

vector<int>ivec2(10j);//含有10个元素的yector财象
cout<<ivec2[10];//错误:ivec2元素的合法索引是从0到9

试图用下标的形式去访问一个不存在的元素将引发锦误,不过这种错误不会被编译器发现,而是在运行时产生一个不可预知的值。

不幸的是,这种通过下标访问不存在的元素的行为非常常见,而且会产生很严重的后果。所谓的缓冲区溢出(buffer overflow)指的就是这类错误,这也是导致PC及其他
设备上应用程序出现安全问题的一个重要原因。