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

清疚 2023-07-19 12:17 200阅读 0赞

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

### 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 容器的基础上改头换面而成，通常更习惯称它们为容器适配器

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

见下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]  
参考：  
[整理资料来源：C语言中文网][C]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]: /images/20230528/90c4db60bf8c4bbb89a53073a32d3a20.png
[C]: http://c.biancheng.net/view/409.html