9.1顺序容器概述

9.1顺序容器概述 顺序容器概述

一个容器就是一些特定类型对象的集合。

1.顺序容器类型

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

随机访问和顺序访问：

• 随机访问：可以直接访问任意位置的元素。如：vector、deque、array、string都是随机访问的容器。随机访问的容器，进行访问 *** 作是非常快的，时间复杂度只需要O(1)。但是，插入/删除 *** 作需要移动之后的所有元素，非常耗时，时间复杂度为O(n)。
• 顺序访问：必须从第一个元素开始逐个读取元素，不能跳着读取。如：list和forward_list是顺序访问。顺序访问的容器牺牲了随机访问的优点。访问速度为O(n)。但是，插入和删除 *** 作都很快速，在固定的位置插入多个元素的时间复杂度都是O(1)。

2.确定使用哪种顺序容器

通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。

以下是一些选择容器的基本原则：

• 除非你有很好的理由选择其他容器，否则应使用vector。
• 如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list。
• 如果程序要求随机访问元素， 应使用vector或deque。
• 如果程序要求在容器的中间插入或删除元素，应使用list或forward_list.
• 如果程序需要在头尾插入或删除元素，但不会再中间位置进行插入或删除 *** 作，应使用deque。