我的书签
添加书签
移除书签第17章 STL动态数组类
动态数组让程序员能够灵活地存储数据，无需在编写应用程时就知道数组的长度。显然，这是一种常见的需求，标准模板库（STL）通过std::vector类提供了现成的解决方案。
在本章中，您将学习：
• std::vector的特点；
• 典型的vector操作；
• vector的大小与容量；
• STL deque类。
17.1 std::vector的特点
vector是一个模板类，提供了动态数组的通用功能，具有如下特点：
• 在数组末尾添加元素所需的时间是固定的，即在末尾插入元素的所需时间不随数组大小而异，在末尾删除元素也如此；
• 在数组中间添加或删除元素所需的时间与该元素后面的元素个数成正比；
• 存储的元素数是动态的，而vector类负责管理内存。
vector是一种动态数组，其结构如图17.1所示。
图17.1 vector的内部构造
要使用std::vector类，需要包含下面的头文件：
17.2 典型的vector操作
std::vector类的行为规范和公有成员是由C++标准定义的，因此，遵循该标准的所有C++编程平台都支持本章将介绍的vector操作。
vector是一个模板类，需要使用第14章介绍的方法进行实例化。要实例化vector，需要指定要在该动态数组中存储的对象类型：
要声明指向list中元素的迭代器，可以这样做：
如果需要可用于修改值或调用非const函数的迭代器，可使用iterator代替const_iterator。
鉴于std::vector有多个重载的构造函数，您可在实例化vector时指定它开始应包含的元素数以及这些元素的初始值，还可使用vector的一部分来实例化另一个vector。
程序清单17.1演示了几种实例化vector的方式。
程序清单17.1 各种实例化std::vector的方式：指定长度和初始值以及复制另一个vector中的值
分析：
上述代码演示了如何为整型具体化vector 类，即实例化一个存储整型数据的vector。该vector 名为vecIntegers，它使用了默认构造函数。在不知道容器最小需要多大，即不知道要存储多少个整数时，默认构造函数很有用。实例化vector的第2种和第3种方式如第10行和第13行所示，在这里，程序员知道vector至少应包含10个元素。注意，这并没有限制容器最终的大小，而只是设置了初始大小。第4种形式如第16行和第18行所示，它使用一个vector实例化另一个vector的内容，即复制vector对象或其一部分。这是所有 STL 容器都支持的构造函数。最后一种形式是使用迭代器。vecSomeElementCopied包含vecWithTenElements的前5个元素。
第4个构造函数只能用于类型类似的对象，因此可使用一个包含整型对象的vector来实例化 vecArrayCopy——另一个整型 vector，但如果其中一个 vector 包含的对象类型为float，代码将不能通过编译。
cbegin()和cend()是否导致编译错误？
如果您使用的编译器没有遵循C++11标准，请使用begin()和end()分别代替该程序中的cbegin()和cend()。
cbegin()和cend()的不同之处（优点）在于，它们返回一个迭代器，但较老的编译器不支持它们。
实例化一个整型vector后，接下来需要在vector中插入元素（整数）。在vector中插入元素时，元素将插入到数组末尾，这是使用成员方法push_back完成的：
程序清单17.2演示了如何使用push_back()在std::vector中动态地添加元素。
程序清单17.2 使用push_back在vector中插入元素
输出：
分析：
第9～12行的push_back是vector类的一个公有成员方法，用于在动态数组末尾插入对象。请注意函数 size ()的用法，它返回 vector中存储的元素数。
C++11
初始化列表
C++11通过std::initialize_list<>支持初始化列表，让您能够像处理静态数组那样，在实例化vector的同时初始化其元素：
如果在程序清单17.2中使用这种语法，可节省3行代码，但这里没有这样做，因为编写本书时， Microsoft Visual C++ 2010编译器的 std::vector实现不支持初始化列表。
push_back在vector末尾插入元素。如果要在中间插入元素，该如何办呢？很多STL容器（包括std::vector）都包含insert()函数，且有多个重载版本。
其中一个版本让您能够指定插入位置：
另一个版本让您能够指定插入位置、要插入的元素数以及这些元素的值（都相同）：
还可将另一个vector的内容插入到指定位置：
可使用迭代器（通常是由begin()或end()返回的）告诉insert()您想将新元素插入到什么位置。
也可将该迭代器设置为 STL 算法（如 std::find()函数）的返回值。std::find()可用于查找元素，然后在这个位置插入另一个元素（这将导致查找的元素向后移）。
程序清单17.3演示了vector::insert()的各种重载版本。
程序清单17.3 使用函数vector::insert在指定位置插入元素
输出：
分析：
上述代码演示了insert函数的强大功能，它让您能够将值插入到容器中间。第17行的vector包含4个元素，每个元素都被初始化为90；然后，使用了成员函数vector::insert的各种重载版本。第23行在开头添加了一个元素；第26行在末尾添加了两个元素，它们的值都是45。第35行演示了如何将一个vector的元素插入到另一个vector中间（这里是第一个元素后面，偏移量为1）。
虽然函数vector::insert功能众多，但给vector添加元素时，应首选push_back()。
请注意，将元素插入vector时，insert()可能是效率最低的（插入位置不是末尾时），因为在开头或中间插入元素时，将导致vector类将后面的所有元素后移（为要插入的元素腾出空间）。根据容器中包含的对象类型，这种移动操作可能需要调用复制构造函数或赋值运算符，因此开销可能很大。在上述例子中，vector包含的是int对象，移动开销不是很大。但在其他情况下，情况可能并非如此。
如果需要频繁地在容器中间插入元素，应选择使用第18章将介绍的std::list。
您使用的C++编译器是否较老
在程序清单17.3中，函数DisplayVector()使用了C++11关键字auto来声明迭代器的类型，如第6行所示。对于这个示例以及后面的示例，如果要使用非C++11编译器编译它们，需要将auto替换为显式类型，这里为vector<int>::const_iterator。
因此，如果您使用的是较老的编译器，需要将DisplayVector()修改成下面这样：
可使用下列方法访问 vector 的元素：使用下标运算符（[]）以数组语法方式访问；使用成员函数at()；使用迭代器。
程序清单17.1演示了如何创建一个包含10个元素的vector实例：
可使用类似于数组的语法访问并设置各个元素：
程序清单17.4演示了如何使用下标运算符（[]）访问元素。
程序清单17.4 使用数组语法访问vector中的元素
输出：
分析：
在第17、21和23行，像使用静态数组那样，使用下标运算符（[]）访问并设置了vector的元素。下标运算符接受一个从零开始的元素索引，与静态数组一样。注意到第 15 行的 for 循环将索引与vector::size()进行比较，确保它跨越vector的边界。
使用[]访问vector的元素时，面临的风险与访问数组元素相同，即不能超出容器的边界。使用下标运算符（[ ]）访问vector的元素时，如果指定的位置超出了边界，结果将是不确定的（什么情况都可能发生，很可能是访问违规）。
更安全的方法是使用成员函数at()：
at()函数在运行阶段检查容器的大小，如果索引超出边界（无论如何都不能这样做），将引发异常。
下标运算符（[ ]）只有在保证边界完整性的情况下才是安全的，如前一个例子所示
也可使用迭代器以类似于指针的语法访问vector中的元素，如程序清单17.5所示。
程序清单17.5 使用指针语法（迭代器）访问vector中的元素
输出：
分析：
在这个例子中，迭代器有点像指针，迭代器的用法很像指针算术运算，如第25和29行所示。在第25行，使用了解除引用运算符（*）来访问存储在vector中的值，而第29行使用了运算符++递增迭代器，使其指向下一个元素。第21行使用了std::distance来计算元素的偏移量（相对于开头的位置），这是根据begin()和指向元素的迭代器计算得到的。
除支持使用push_back方法在末尾插入元素外，vector还支持使用pop_back函数将末尾的元素删除。使用pop_back将元素从vector中删除所需的时间是固定的，即不随vector存储的元素个数而异。程序清单17.6演示了如何使用函数pop_back删除vector末尾的元素。
程序清单17.6 使用pop_back删除最后一个元素
输出：
分析：
上述输出表明，第29行的pop_back函数将vector的最后一个元素删除，从而减少了vector包含的元素数。第32行再次调用size()，以证明vector包含的元素少了一个，如输出所示。
在程序清单17.3中，DisplayVector()只能接受整型vector作为参数，而在程序清单17.6中，它是个模板函数（第4-13行）。这有助于将该模板函数重用于浮点型vector：
该模板函数接受任何类型的vector作为参数，只要该类型支持运算符*，且其返回值可被cout理解。
17.3 理解大小和容量
vector 的大小指的是实际存储的元素数，而 vector 的容量指的是在重新分配内存以存储更多元素前vector能够存储的元素数。因此，vector的大小小于或等于容量。
要查询vector当前存储的元素数，可调用size()：
要查询vector的容量，可调用capacity()：
如果vector需要频繁地给其内部动态数组重新分配内存，将对性能造成一定的影响。在很大程度上说，这种问题可以通过使用成员函数 reserve (number)来解决。reserve函数的功能基本上是增加分配给内部数组的内存，以免频繁地重新分配内存。通过减少重新分配内存的次数，还可减少复制对象的时间，从而提高性能，这取决于存储在vector中的对象类型。程序清单17.7说明了size()和capacity()之间的区别。
程序清单17.7 演示size()和capacity()
输出：
分析：
第8行实例化了一个包含5个整型对象的vector，这些整型对象使用默认值0。第11行和第12行分别显示vector的大小和容量，它们在实例化后相等。第15行在vector中插入了第6个元素。鉴于在插入前vector的容量为5，因此vector的内部缓冲区没有足够的内存来存储第6个元素。换句话说， vector 为扩大其容量以存储 6 个元素，需要重新分配内部缓冲区。重新分配的逻辑实现是智能的：为避免插入下一个元素时再次重新分配，提前分配了比当前需求更大的容量。
从输出可知，在容量为5的vector中插入第6个元素时，将容量增大到了7。size()总是指出vector存储的元素数，当前其值为6。第22行插入了第7个元素，这次没有扩大容量，因为已分配的内存足以满足需求。这时大小和容量相等，这表明vector的容量已经用完，再次插入元素将导致vector重新分配其内部缓冲区、复制现有的元素再插入新值。
在重新分配 vector 内部缓冲区时提前增加容量方面，C++标准没有做任何规定，这取决于使用的STL实现。
17.4 STL deque 类
deque是一个STL动态数组类，与vector非常类似，但支持在数组开头和末尾插入或删除元素。要实例化一个整型deque，可以像下面这样做：
要使用std::deque，需要包含头文件<deque>：
deque的内部结构如图17.2所示。
图17.2 deque的内部结构
deque 与 vector 极其相似，也支持使用方法 push_back()和 pop_back()在末尾插入和删除元素。与vector一样，deque也使用运算符[]以数组语法访问其元素。deque与vector的不同之处在于，它还允许您使用push_front和pop_front在开头插入和删除元素，如程序清单17.8所示。
程序清单17.8 实例化一个STL deque，并使用push_front和pop_front在开头插入和删除元素
输出：
分析：
第9行实例化了一个整型deque，其语法与实例化整型vector极其相似。第12～14行演示了deque的成员函数push_back的用法，然后第17～19行演示了push_front的用法，push_front是deque唯一不同于vector的地方。pop_front的用法类似，如第36行所示。要显示deque的内容，第一种方法是使用数组语法访问其元素，第二种方法是使用迭代器。使用迭代器时（如第 47～53 行所示），使用算法std::distance计算元素的偏移位置，这与程序清单17.5中处理vector时相同。
17.5 总结
本章介绍了将vector和deque用作动态数组的基本知识，还解释了大小与容量的概念。通过对vector进行优化，减少了重新分配内部缓冲区的次数。重新分配缓冲区时，需要复制容器包含的对象，这可能降低性能。vector是最简单的STL容器，也是最常用和最高效的。
17.6 问与答
问：vector会改变其存储的元素的顺序吗？
答：vector是一种顺序容器，元素的存储顺序与插入顺序相同。
问：要将元素插入到vector中，应使用哪个函数？元素将插入到vector的什么位置？
答：成员函数push_back将元素插入到vector末尾。
问：哪个函数用于获悉存储在vector中的元素个数？
答：成员函数 size ()返回存储在 vector中的元素个数。对于所有STL容器，该函数都如此。
问：随着vector包含的元素增多，在vector末尾插入或删除元素所需的时间是否更长？
答：否。在vector末尾插入或删除元素所需的时间是固定的。
问：使用成员函数reserve的优点是什么？
答：reserve (…)为 vector的内部缓冲区分配内存空间，这样在插入元素时 vector就不需要重新分配缓冲区并复制现有内容。根据vector存储的对象类型，为vector预留内存空间可能改善性能。
问：在插入元素方面，deque与vector是否不同？
答：没有。在插入元素方面，deque的特点与vector类似。将元素插入到末尾时，两者所需的时间都是固定的，而将元素插入到中间时，所需的时间与容器包含的元素数成正比。然而，vector 只允许在末尾插入，而deque允许在开头和末尾插入。
17.7 作业
作业包括测验和练习，前者帮助读者加深对所学知识的理解，后者提供了使用新学知识的机会。请尽量先完成测验和练习题，然后再对照附录D的答案。在继续学习下一章前，请务必弄懂这些答案。
1．在vector的开头或中间插入元素时，所需的时间是否是固定的？
2．有一个vector，对其调用函数size()和capacity()时分别返回10和20。还可再插入多少个元素而不会导致vector重新分配其缓冲区？
3．pop_back函数有何功能？
4．如果 vector <int>是一个整型动态数组，那 vector <CMammal>是什么类型的动态数组？
5．能否随机访问vector中的元素？如果是，如何访问？
6．哪种迭代器可用于随机访问vector中的元素？
1．编写一个交互式程序，它接受用户输入的整数并将其存储到vector中。用户应能够随时使用索引查询vector中存储的值。
2．对练习1中的程序进行扩展，使其能够告诉用户他查询的值是否在vector中。
3．Jack在eBay销售广口瓶。为帮助他打包和发货，请编写一个程序，让他能够输入每件商品的尺寸，将其存储在vector中再显示到屏幕上。
