C++标准程序库之vector

本人之前对STL的学习主要来自C++ Primer一书,随着时间的推进,对标准模板库的一些知识有些淡忘,遂再次对STL容器部分加以总结,用以温习。

1.容器通用操作

介绍vector之前,先总结容器的一些共用的操作。如下所列:

下面举几个实例:

(1)以一个容器的元素为初值,完成初始化操作:

(2)以某个数组的元素为初值,完成初始化操作:

此处有两点需要说明的:
1)在C++ 11新标准之后,提供了begin和end函数用于内置数组,因而可以简化上述操作,使得这种操作看起来像“类迭代器”操作似的。即,begin(array)/end(array)。
2)区间范围是左闭右开,即上述区间为[  array[0], array[6]  )

(3)以标准输入装置完成初始化操作:

(4)常用的比较操作符,有以下三条规则:

  • 比较操作的两端(两个容器)必须属于同一类型。
  • 如果两个容器的所有元素依序相等,那么这两个容器相等。采用operator==检查元素是否相等。
  • 采用字典式顺序比较原则来判断某个容器是否小于另一个容器。

(5)赋值(Assignment)和swap()

1)当对容器进行赋值元素时,源容器的所有元素被拷贝到目标容器内,后者原本的所有元素被移除。所以,容器的赋值操作代价比较高昂。
2)如果两个容器类型相同,而且拷贝后源容器不再使用,那么可以使用一个优化方法:swap()。
3)swap()的性能要比赋值优异得多,因为它只交换容器的内部数据。事实上它只交换某些内部指针,所以时间复杂度是“常数”,不像实际赋值操作的复杂度为“线性”。

2.vector

vector塑造出一个动态数组。因此,它本身是“将元素置于动态数组中加以管理”的一个抽象概念。

使用之前,必须加入头文件:
#include <vector>

其中,类型vector是一个定义在namespace std内的template:
namespace std {
template<class T, class Allocator = allcoator<T>>
class vector;
}

vector的元素可以是任意类型T,但必须具备assignable和copyable两个性质。

(1)vector的能力

1)vector支持随机存取,因此只要知道位置,你可以在常数时间内存取任何一个元素。vector迭代器是随机存取迭代器,所以对任何一个STL算法都可以奏效。

2)在末端添加或删除元素时,vector的性能相当好。可是如果是在前端或中部安插或删除元素,性能就不怎么样了,因为操作点之后的每一个元素都必须移到另一个位置,而每一次移动都得调用assignment操作符。

3)大小(size)和容量(capacity)

vector之中用于大小相关的函数有size(), empty(), max_size(),另一个与大小有关的函数是capacity(),它返回vector实际能够容纳的元素数量。

vector的容量之所以很重要,有以下两个原因:

  • 一旦内存重新配置,和vector元素相关的所有reference, pointers, iterators都会失效。
  • 内存重新配置很耗时间。

对此,我们可以使用reserve()保留适当容量,避免一再重新配置内存:
std::vector<int> v;
v.reserve(80);

另一种避免重新配置内存的方法是,初始化期间就向构造函数传递附加参数,构造出足够空间:
std::vector<T> v(5);
当然,要获得这种能力,此种元素类型必须提供一个default构造函数。

4)vector容量,概念上和string类似,有一个大不同点:vector不能使用reserve()来缩减容量,这一点和string不同

5)既然vector的容量不会缩减,我们便可确定,即使删除元素,其reference,poiter,iterator也会继续有效,继续指向动作发生前的位置。然而安插操作却可能使其失效。(因为安插可能导致vector重新配置空间)

(2)vector的操作函数

1)vector的构造函数和析构函数

2)vector的非变动性操作

3)vector的赋值操作

4)元素存取

5)迭代器相关函数

vector迭代器是Random access iterators(随机存取迭代器),因此从理论上讲,可以通过这个迭代器操作所有STL算法。

vector迭代器持续有效,除非发生两种情况:其一,使用者在一个较小索引位置上插入或移除元素;其二,由于容量变化而引起内存重新分配。

6)插入(insert)和移除(remove)元素

插入元素和移除元素,都会使“作用点”之后的各元素的reference,pointer,iterator失效。如果插入操作甚至引发内存重新分配,那么该容器身上的所有reference,pointer,iterator都会失效。

vector并未提供任何函数可以直接移除“与某值相等”的所有元素。这是算法发挥威力的时候:
std::vector<Elem> coll;

//remove all elements with value val
coll.erase(remove(coll.begin(), coll.end(), val), coll.end());

如果只是需要移除“与某值相等”的第一个元素,可以这么做:

pos = find(coll.begin(), coll.end(), val);
if (pos != coll.end())
coll.erase(pos);

(3)将vector当做一般array使用

对于vector v中任意一个合法索引i,以下表达式肯定为true:
&v[i] == &v[0] + i

保证了这一点,就可推导出一系列重要结果。任何地点只要你需要一个动态数组,你就可以使用vector。例如利用vector来存放常规C字符串(类型为char*或const char*):

对此,有两点需要注意:
1)必须确保上述vector的大小足够容纳所有数据,如果使用的是C-string,记住最后有个‘\0’元素。
2)不要把迭代器当做第一元素的地址来传递。vector迭代器并不是个一般指针:

(4)异常处理

vector只支持最低限度的逻辑错误检查。subscript下标操作符的安全版本at(),是唯一被标准规格书要求可能抛出异常的一个函数。

如果vector调用的函数抛出异常,C++标准程序库作出如下保证:

1)如果push_back()插入元素时发生异常,该函数不起作用。
2)如果元素拷贝操作(包括copy构造函数和assignment操作符)不抛出异常,那么insert()要么成功,要么不生效。
3)pop_back()决不会抛出任何异常。
4)如果元素拷贝操作(包括copy构造函数和assignment操作符)不抛出异常,erase()和clear()就不抛出异常。
5)swap()不抛出异常。
所有这些保证都基于一个条件:析构函数不得抛出异常

(5)vector运用实例

输出:

这个例子可以看出,当容量不足时,针对该程序,系统将容量扩充了一倍。

注:
本文总结的内容主要来自C++标准模板库一书,介于手里的版本出版于C++11之前,因此书中并未支持C++11特性的内容。对此,一些重要区别笔者会加以注明。

发表评论

电子邮件地址不会被公开。 必填项已用*标注