第9章 顺序容器------(持续更新)

所有容器类都共享公共的接口，不同容器按不同方式对其进行扩展。
这个公共接口使容器的学习更加容易—我们基于某种容器所学习的内容也都适用于其他容器。
每种容器都提供了不同的性能和功能的权衡。

9.1、顺序容器概述

下表列出了标准库中的顺序容器, 所有顺序容器都提供了快速顺序访问元素的能力。但是,这些容器在以下方面都有不同的性能折中:

• 向容器添加或从容器中删除元素的代价
• 非顺序访问容器中元素的代价

除了固定大小的 array 外，其他容器都提供高效、灵活的内存管理。

• list和 forward_list 两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问:为了访问一个元素，我们只能遍历整个容器。而且，与 vector、deque和 array相比，这两个容器的额外内存开销也很大.
• deque是一个更为复杂的数据结构。与string和 vector类似，deque 支持快速的随机访问。与string和 vector一样，在 deque 的中间位置添加或删除元素的代价(可能）很高。但是，在 deque 的两端添加或删除元素都是很快的，与 list或forward_list添加删除元素的速度相当。
• forward_list 的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。
• 对其他容器而言size保证是一个快速的常量时间的操作。

9.2、容器库概览

一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。即，deque定义头文件 deque中，list定义在头文件list中，以此类推。

容器类型上的操作形成了一种层次:

• 某些操作是所有容器类型都提供的。
• 另外一些操作仅针对顺序容器、关联容器 或 无序容器。
• 还有一些操作只适用于一小部分容器。

对所有容器都适用的操作:

9.2.1 、迭代器

与容器一样，迭代器有着公共的接口:如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。

使用左闭合范围蕴含的编程假定

[begin, end)

标准库使用左闭合范围是因为这种范围有三种方便的性质。假定begin和 end 构成一个合法的迭代器范围，则

• 如果begin 与end相等，则范围为空
• 如果begin 与end不等，则范围至少包含一个元素，且 begin 指向该范围中的第一个元素
• 我们可以对begin递增若干次，使得 begin==end

这些性质意味着我们可以像下面的代码一样用一个循环来处理一个元素范围而这是安全的:

while (begin != end) {*begin = val;	//正确:范围非空，因此begin指向一个元素++begin;		//移动迭代器,获取下一个元素
}

9.2.2 、容器类型成员

9.2.3 、begin 和 end 成员

9.2.4 、容器定义和初始化

9.2.5 、赋值和 swap

9.2.6 、容器大小操作

9.2.7 、关系运算符

9.3、顺序容器操作

9.3.1 、向顺序容器添加元素

9.3.2 、访问元素

9.3.3 、删除元素

9.3.4 、特殊的forward_list操作

9.3.5 、改变容器大小

9.3.6 、容器操作可能使迭代器失效

9.4、vector对象是如何增长的

9.5、额外的string 操作…

9.6、容器适配器