C++ STL之序列式容器概述

声明：该文章内容为整理笔记内容，内容来源见参考。

一、什么是序列式容器

以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据

需要特殊说明的是:
该类容器并不会自动对存储的元素按照值的大小进行排序;
序列容器是一类容器的统称，并不指具体的某个容器

二、序列式容器的分类

1、array<T, N>（数组容器）：
表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值

2、vector<T>（向量容器）：
用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）

3、deque<T>（双端队列容器）：
和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶

4、list<T>（链表容器）：
是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素

5、forward_list<T>（正向链表容器）：
和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器

其实除此之外，stack<T>（栈容器）和queue<T> （队列）本质上也属于序列容器，只不过它们都是在 deque 容器的基础上改头换面而成，通常更习惯称它们为容器适配器

三、序列式容器之间的区别

见下图：

参考：
整理资料来源：C语言中文网