北京大学《C++程序设计》这门课将向你讲授C++程序设计有关的概念和语法，使你能够使用C++语言，以面向对象的方法编写可维护性、可扩充性好的，较大规模的程序。我们建议你在开始本课程之前已经熟悉了C语言和基本程设编写。这门课则将带你掌握C++语言中类、对象、运算符重载、继承、多态等面向对象的程序设计方法，以及模板、标准模板库STL等泛型程序设计的机制，体会和领悟面向对象程序设计方法和泛型程序设计方法的优势。
顺序容器Vector
Loading...
来自 Peking University 的课程
C++程序设计
655 个评分
从本节课中
标准模板库 STL-1
本模块将介绍C++的标准模板库（Standard Template Library，STL），这是泛型程序设计最成功的应用实例。STL是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。有了STL，你就不必编写大多的、常用的数据结构和算法。即便不想用面向对象的程序设计方法编程，学习STL也是大有裨益的。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，在这一小节中我们来看一下STL的第一个容器Vector。
可能有同学会注意到今天我们这个课程的背景呢有一点点不一样
这是因为学校呢新给我们大家添置了一个叫做，嗯，多重背景的这样一个背景幕
那么一共有蓝绿黑白四种颜色 那么我们这次课呢，就选择这种青葱模式。
其实很多同学在了解了Vector的使用之后呢 都会感慨说：哎呀，这才是我想要的那个数组
那么具体它是一个怎么样的数组呢？我们说Vector
它本身提供的是一种叫做可编程的动态数组。
什么叫做动态可编程的数组呢？ 这就是针对我们之前自己去写的一些静态的数组，比方说我们定义了一个int a 100
我们定义了一个数组a它包含了100个元素，你可以从a 0一直访问到a
99 但是有些时候，往往程序就偏偏需要呢第100个
101个，也就说额外超出我们自己定义的数组范围大小的那些元素
那么在这个时候，我们就不可以轻易对静态定义的这些数组呢
直接进行删改或者说直接来进行扩充
那么这时候我们就迫切地需要说:哎呀，最好能有一个
所谓可以自动来调节长短的动态数组，就可以解决大问题 那么Vector就是你所需要的那个数组。
当然呢，我们去使用Vector的时候，必须要去引入这样的一个头文件。
之前呢郭老师已经给大家介绍了关于迭代器的概念
那么作用在Vector这个容器上呢，这个迭代器呢，我们说它是一个叫做随机访问的迭代器
因为它是随机访问的，所以呢我们可以根据下标随机地访问某一个元素
那么由于是随机访问迭代器，所以这种按下标随机
访问某个元素的时间呢，通常都是为常数级别的。
而且呢我们在Vector这个容器的尾部
如果去添加一些额外的一些元素进来的话呢，那么它的速度也通常是比较快的
因为我们针对Vector这个容器呢，一般来说即便去存放一个元素
也会需要去开辟一个比方说32个元素大小这样的一块空间
因此呢，你如果需要在这个基础上来进行扩充的话，那么只需要直接去添加相应的元素就可以了
当然如果你增加的内容非常的多，超出了我预先预留的这样的一些额外的空间的话
那么通常我们需要去分配一个新的空间出来，然后把已有的数据呢直接拷贝到新的数据上
新的空间上来进行扩充，那么这样的过程呢，可能就会速度会慢一些
所以我们说呢，通常在尾部添加这个元素的速度呢是比较快的。
但是要注意我们对于Vector来讲，因为它本身就是一个数组
如果我在这个数组的中间去插入某一个元素的话，那么这个的
插入速度呢实际上还是非常慢的，因为这个过程呢他并不是
一个固定的时间，而是跟你本身数组的大小是有关系的
因为你需要去插入相应的元素并且把其后续的所有元素呢进行一下移动。
另外呢，我们在这个Vector这个容器上呢
可以使用后续要介绍的所有的STL的算法
所以我们说整个这个Vector的容器呢提供了非常强大的功能
那么对于Vector来讲呢，它包含了一系列的成员函数
那么首先呢大家会想到说我们实际上会要去利用构造函数 来对这个Vector容器呢进行初始化
那么初始，它这个初始化的构造函数呢，主要是包含了这样的几种
首先呢，你可以去使用这样的一个无参的构造函数
那么无参的构造函数呢，就是将这个容器呢直接初始化为空
此外呢，也可以去传递一个 整形的这个参数来作为这个
定义初始化的这样的一个，N个元素的一个个数，啊也就是说
我把这个容器呢初始化为包含n个元素的这样的一个数组
那么同时呢，你也可以去传递两个参数，第一个参数还是int
n，那么第二个参数呢，是一个const T类型的一个val的一个值
那么这实际上呢还是说假定呢我的这个 数组中间的元素的类型是T
那么通过这样的一个构造函数之后呢，我们会将整个容器
初始化为包含了n个元素，并且每个元素值都是
相应的这个val这个值所对应的值，那么这样的一个容器呢就被初始化为
n个元素且每个元素都是val的这样的一个数组。
最后呢,我们还可以利用传递两个迭代器的值
那么这个迭代器本身呢它实际上应该对应的是
另外一个容器的一个起始的迭代器和中止的迭代器
也就是说我们将这个容器初始化为另外一个容器上的
从迭代器first到迭代器last所指向的那一段区间上的内容。
注意这个区间呢，它是一个前闭后开的一个区间
所以呢我们可以利用这样的一个构造函数呢，直接把其他的
容器中间的内容啊初始化到我自身这个容器中间来。
那么除了这个相应的一系列构造函数之外呢，我们还有一些常用的函数
比方说我们刚才提到说对于Vector这个容器，你在尾部来进行一系列的操作呢
实际上速度是会非常快的而且非常的便捷，所以相应地我们就有了一个
在尾部去删除相应元素的函数叫做pop_back，啊，pop把它pop出去
那么同时呢我们还有一个去把相应的值添加进来的，这样的一个函数叫做push_back
我们把相应希望能够添加到容器末尾的这个元素呢，把它push进来
另外呢我们可以直接去调用size这样一个函数，去获取这个容器
当中包含元素的个数，另外呢我们还可以去利用font
back这两个函数去获取元素这个容器当中
第一个元素以及最后一个元素相应的引用
那么说了这么多，我们来具体看看这个Vector的这个容器呢是怎么样使用的。
这里给出了一个小的程序 我们可以看到说我们在这个小程序当中呢，因为要使用Vector，所以我们要引入
Vector这样的一个头文件。
那我们接着呢，就来具体看一下如何去使用Vector这样的一个动态数组。
我们在这个例1这个例子当中呢，简单地
解释了一下如何使用Vector来进行一些动态数组的操作
我们看到呢我们在程序当中首先定义了一个静态数组a
这个数组它包含了5个元素，这5个元素呢分别被初始化为了1、2、3、4、5
此外呢，我们利用Vector这样的一个容器去定义了一个动态数组v
这个元这个v呢，它中间的每一个元素都是int型的
此外呢，我们通过刚才介绍的第二种构造函数
来对这个v呢进行初始化，我们通过传递 一个int型的量
参数5来初始化说，我的这个v容器当中呢包含了5个元素
那么有了这个定义好的v之后呢，我们实际上就可以对这个数组
呃，本身或者说对于这个容器来讲呢进行一系列的操作了
我们可以让其返回相应首元素的迭代器v.begin
以及v这个数组 最后那个元素之后元素相应对应的这个迭代器。
我们看到说我们强调end这个函数呢，它返回的是我的这个
v当中最后这个元素之后
那个位置的迭代器，啊，所以呢我们可以
去返回相应这样两个迭代器之后，因为本身作用在
Vector上面呢这个迭代器呢，它是随机访问迭代器
所以呢,这两个迭代器是可以进行相减的，啊，有了相减这个操作我们就可以把它对应的值呢size出来
实际上就会包含整个这个 容器的大小，也就是相应的5，在这个例子当中。
那么除此之外呢我们也可以for循环
去让它对整个容器中间的每一个元素来进行赋值 那么要注意就是我们可以利用
这个方括号所对应的这个下标访问来访问容器当中的每一个元素。
当然我们也可以 去判断说i呢始终是要小于v.size
也就是说要不能超过我们定义的这个容器的这个元素个数。
除此之外呢我们还可以利用v.at这个函数
来访问相应的一个元素，就这个容器当中的某个元素 在这个例子当中呢我们访问的就是第5个元素
我们把v当中的这个第5个元素呢赋值为了100
那么有了上述的这样的一系列赋值之后呢
我们就可以相应的把v中间的每个元素呢size出来
除此之外呢我们还可以利用其它的构造函数来初始化相应的这个
我们用vector定义的这个动态数组。比方说我们利用 刚才介绍的第四种构造函数
通过去定义一个容器的起始的位置以及它末尾的位置
来初始化相应我们新定义出来的这样的一个
vector
v2。我们这里就利用了a这个数组 把a这个数组当中的这样的一段内容直接初始化给v2。
那么，有定义好这样的一个v2这样的一个动态数组之后呢，
我们可以做的事儿是什么呢？我们可以去调用insert这个函数
我们可以直接把相应希望插入的这个值呢，插入到我们指定的位置上。
也就说，我们现在呢希望能够在begin()+2的位置上插入13这个值
那么我们就首先在insert第一个参数当中呢，去传递我们希望插入的位置。
之后的第二个参数呢，去传递希望插入的具体的这个值。
通过这样的一个方式，调用这一个insert函数就可以实现我们之前在静态数组
当中所需要去进行一系列这个插入拷贝这样的一个过程的
繁琐的过程。只需要去调用这一个函数就可以完成了
那么我们就把13这个值相应地插到了v2这个数组当中。
那么有了这样的一个插入之后呢，我们来看一下最后这个
v2的形式。是吧？我们刚看到说我们首先做了这个v.end()-
begin()，我们得到一个5这样的一个值。那么我们通过一系列的这个赋值之后呢，就得到了这样0,1,2,3
100.我们最后把这个 at(4)这样的一个值，元素呢赋值为了100。最后呢，我们需要做的事儿呢就是
我们把原先的这个 a呢初始化给了v2，所以呢v2一开始呢是1,2
3,4,5这样的五个值。之后呢，我们希望把13
值呢插入到从begin()+2的位置上。比如说，我们希望把13呢插入到了这里
所以呢我们如果在这时候
所以呢如果我们在这时候cout v2的话， 我们会看到呢相应的这个输出就是1,2,13,3,4,5
那么除了去利用vector去构建一个
一维的动态数组之外呢，实际上vector也可以去形成一个二维的动态数组。
那么其实思路会非常的简单，就说我们在vector<int>这个类型的参数
设置的时候呢，把它再次去使用一个vector<int>这样的一个容器
来定义就可以。比如说我们这里只要嵌套地使用两个vector就可以实现一个
二维动态数组的一个实现。那么对于这里头举得这个例子，vector
v来讲的话呢，那么它当中包含了3个元素。那么每一个元素
对应的呢又是一个vector<int>这样的一个容器 我们具体来看一下。
我们利用这样的一个二维动态数组的一个定义，比如说利用vector<int>这样的一个容器
作为类型来初始化每一个 v中间相应的元素的类型。那么有了这样的一个定义之后呢，我们需要做的事儿，
如果我们希望能够去把相应的这个值都放到我们对应的这个二维数组当中呢，我们就可以写
这么一个二重的一个for循环。然后在
循环体当中呢，去把相应我们希望放在这个vi中间的内容呢把它push
back进去 那么有了这样的一个过程之后呢，我们把每一个对应的值都把它放进去
之后我们要做的事儿呢，我们把这个j都放进去之后，我们要做的事儿呢
就是相应地把它输出出来，然后我们会看到呢，我们这个程序呢实际上
就可以完成把这个0,1,2,3,4对应每一个值
相应地赋给这个v (3)，其中每一个元素中间的值也可以把它相应地输出出来就可以了。
所以这就是一个最简单的一个二维动态数组的一个实现
