文章目录
- 一、容器分类
- （1）序列性容器
- （2）关联式容器
- （3）容器适配器
- 二、容器共性
- 三、容器比较
一、容器分类
（1）序列性容器
-
序列式容器：按线性排列来存储某类型值的集合，每个元素都有自己特定的位置。顺序容器主要有vector、deque、list
-
vector：
- 本质是动态数组。它是在堆中分配内存，元素连续存放
- 有保留内存，清除元素后内存也不会释放。当请求空间超出现有空间时，会申请等同于当前自身空间大小的新空间
- 支持随机访问和任意位置插入删除。
- 因为vector是连续存放的，在尾部增删元素速度最快，否则就要进行数据的移动，速度会慢很多。如果vector的元素是结构或类，移动时也会进行构造和析构操作
-
deque：
- 本质是分段数组+一个数组首地址索引数组。参考：deque的实现原理
- 在容器任意位置的操作需要线性时间。随机访问速度比vector慢，但在随机位置增删数据比vector快
- 支持随机访问和任意位置插入删除。
- 和vector不同，deque支持高效地从起始和结尾端增删数据，这两个位置的操作不会引起其他数据移动
-
list：
- 本质是双向链表
- 是一种双线性列表，只能从前向后或从后向前顺序访问，不支持随机访问
（2）关联式容器
-
关联式容器：与顺序容器相比，关联式容器更注重快速和高效地检索数据的能力。这类容器是根据键值（key）来检索数据的，键可以是值，也可是容器内的某一成员。这一类中的成员初始化后都是按一定顺序排列好的。主要有set、multiset、map和muitmap
-
set：快速查找，不允许重复值 -
multiset：快速查找，允许重复值 -
map：一对一映射，基于关键字快速查找，不允许重复值 -
multimap：一对多映射，基于关键字快速查找，允许重复值
（3）容器适配器
-
容器适配器：对已有容器的进行某些特性的再封装，不是一个真正的新容器，主要有stack、queue
-
stack：堆栈类，后进后出 -
queue：队列类，先进先出
二、容器共性
- 容器一般提供一下函数
名称 | 说明 |
默认构造函数 | 提供容器默认初始化的构造函数 |
复制构造函数 | 将容器初始化为现有同类容器副本的狗杂函数 |
析构函数 | 释放容器空间时进行内存整理的析构函数 |
empty | 容器中无元素返回true；否则返回false |
max_size | 返回容器中可存储的最大元素数目 |
size | 返回容器中当前元素个数 |
= | 将一个容器赋给另一个容器 |
< / <= / > / >= / == / != | 容器间比较 |
swap | 交换两个容器元素 |
- 顺序容器和关联容器共有函数如下
名称 | 说明 |
begin | 此函数有两个版本，返回第一个元素的 迭代器指针 和 常迭代器指针 |
end | 此函数有两个版本，返回最后一个元素后面一位的 迭代器指针 和 常迭代器指针 |
rbegin | 此函数有两个版本，返回最后一个元素的 迭代器指针 和 常迭代器指针 |
rend | 此函数有两个版本，返回第一个元素前一位的 迭代器指针 和 常迭代器指针 |
erase | 从容器中清除一个或几个元素 |
clear | 清除容器中所有元素 |
三、容器比较
- vector：
- 连续空间存储
- 快速访问随机元素（可用
[]）；快速在末尾插入元素；在序列中随机增删元素比较慢 - 如果一开始分配的空间不够，有一个重新分配更大空间的过程
- deque：
- 小片的连续，小片间用链表相连，实际上内部有一个map指针。
- 快速随机访问元素（因为知道类型，所以还是可以用
[]取值，但速度没有vector快）；快速在首尾两端增删元素；在序列中随机增删元素比较慢；空间分配快于vector，重新分配空间后原有元素不需要备份。 - 对deque的排序操作，可以先复制到vector，排序后再复制回来
- list：
- 每个元素用链表相连
- 随机访问比vector慢；随机插入比vector快。对每个元素分配空间，所以不存在空间不足重新分配的情况
- set：
- 内部元素唯一，用一颗平衡树结构来存储。
- 遍历的时候就排序了。查找也比较快
- map：
- 一对一映射结合，key不能重复