第9章顺序容器

前言

本章是对第三章——字符串、向量和数组的扩展延伸，在第三章我们对标准库的顺序容器有一定了解，那么学习完本章我们对顺序容器的知识将会更加完整。

标准库定义了几种关联容器，关联容器中元素的位置由元素相关联的关键字值决定。我们将在本章对关联容器做一定了解，在第十一章将会介绍关联容器特有的操作。

在第三章我们就发现，顺序容器在操作上似乎有共通性，原因是在容器类共享公共的接口，不同容器按照不同方式对其进行扩展。当然每种容器都提供不同的性能和功能的权衡。

容器可以看作一些特定类型对象的集合。顺序容器（sequential container)则是为用户（一般是程序员）提供控制元素存储和访问顺序的能力，根据元素加入容器的位置相对应。与之相对的则是关联容器，其依赖于元素的值，根据关键字的值来存储元素。

此外，标准库还提供三种容器适配器，分别为容器操作定义不同的接口，来借此与容器类型进行适配。

9.1 顺序容器概述

在前言简述了顺序容器的概念，标准库中存在以下顺序容器：

顺序容器类型	解释
vector	可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
array	固定大小数组。支持快速随机访问。不能添加或删除元素
string	与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入/删除速度快
deque	双端队列。支持快速随机访问。在头尾位置插入/删除速度很快
list	双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快
forward_list	单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快

从上述的解释中，我们不难发现顺序容器有着不同的性能折中。

例如：

插入/删除元素较慢（以向容器添加或删除元素为代价）

无法进行快速随机访问（以非顺序访问容器元素为代价）

补充

forward_list和array是C++11中新增加的类型。

forward_list在设计之初，其目的就是为了获得与最好的手写单向链表数据结构一致的性能，所以该类型并没有size操作，毕竟保存或计算其大小也会比手写链表多出额外开销:)。

array类型与内置类型概念上一致，但是array更为安全、容易使用。当然，array对象大小是固定的，所以不支持添加和删除元素以及改变容器大小的操作。

虽然我们不愿承认大多数开发者设计的数据结构比标准库中容器运行速度慢，但事实便是如此:)。在C++下的标准库中容器的性能几乎与精心设计优化的同类数据结构一样好（通常更好?）。