vector

概述

vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于 空间的运用的灵活性。array是静态空间，一旦配置了就不能改变；要换个大（或 小）一点的房子，可以，一切琐细得由客户端自己来：首先配置一块新空间，然后将元素从旧址一一搬往新址，再把原来的空间释还给系统。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对 于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始就要求一个大块头array 了，我们可以安心使用vector，吃多少用多少。

数据结构

vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage 指向整块连续空间（含备用空间）的尾端：

1
2
3
4
5
6
7
8
9

template〈class T, class Alloc = alloc>
class vector {
...
protected：
	iterator start；	//表示目前使用空间的头
	iterator finish；	//表示目前使用空间的尾
	iterator end_of_storage; //表示目前可用空间的尾
...
}

为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量（capacity)的观念。换句话说， —个vector的容量永远大于或等于其大小。一旦容量等于大小，便是满载，下次再有新增元素，整个vector就得另觅居所.

当我们以push_baCk()将新元素插入于vector尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 finish,使vector变大。如果没有备用空间了，就扩充空间（重新配置、移动数据、释放原空间）.

注意，所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原 空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就 都失效了。这是程序员易犯的一个错误，务需小心。

vector的迭代器

vector维护的是一个连续线性空间，所以不论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如 operator*, operator->, operator++, operator–，operator+, operator-,operator+=,operator-=,普通指针天生就具备。vector支持随机存取，而普通指针正有着这样的能力。所以vector迭代器其实是原生指针.

所以，vector提供的是Random Access Iterators。

priority_queue

概述

priority_queue带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。权值最髙者，排在最前面。

数据结构

缺省情况下priority_queue系利用一个max-heap完成，max-heap 可以满足priority_queue所需要的“依权值高低自动递增排序”的特性。而max-heap的数据结构是完全二叉树.

完全二叉树整棵树内没有任何节点漏洞，这带来一个极大的好处：我们可以利用array来储存所有节点。将array的#0元素保留（或设为无限大值或无限小值），那么当完全二叉树中的某个节点位于array的i处时，其左子节点必位于array的2i处，其右子节点必位于array的2i+i处，其父节点必位于“i/2”处（此处的“/”权且代表高斯符号，取其整数）。

这么一来，我们需要的工具就很简单了：一个array和一组heap算法（用来插入元素、删除元素、取极值，将某一整组数据排列成一个heap)。array的缺点是无法动态改变大小，而heap却需要这项功能，因此，以vector代替array是更好的选择。

priority_queue没有迭代器

priority_queue的所有元素，进出都有一定的规则，只有queue顶端的元素(权值最高者），才有机会被外界取用。priority_queue不提供遍历功能，也不提供迭代器。