【C++】STL 标准模板库 ③ ( STL 容器简介

一、STL 容器简介1、STL 容器区别STL 容器 用于管理 一组 数据元素 , 不同类型的 STL 容器 的区别 主要是 节点 和 节点之间的关系模型 不同 ;

容器的内存空间是否连续 : 向量 vector 的内存空间是连续的 , 列表 List 的内存空间是不连续的 ;容器中的元素节点关系 : 顺序排列 , 单向链表 , 双向链表 , 树形关系 ;容器中的元素是否允许重复 : 集合 Set 中的元素不允许重复 ;容器中的元素插入限制 : 是否允许 插入到中间 , 插入到首部 , 插入到尾部 ;容器中的元素移除限制 : 是否允许 移除中间元素 , 移除首部元素 , 移除尾部元素 ;数据结构 主要是 研究 节点 与 节点 之间关系的 ;

2、STL 容器分类STL 容器 分为 2 大类 , 分别是 " 序列式容器 " 和 " 关联式容器 " ;

序列式容器 : Sequence Containers , 容器中每个元素的位置都是固定的 , 元素的位置取决于插入元素的 时间 和 位置 , 与元素值无关 ;

向量 Vector , 双端队列 Deque , 列表 List 是序列式容器 ;如下图所示 , 序列式容器的位置是固定的 ;

关联式容器 : Associated Containers , 元素的位置与插入顺序无关 , 容器中有一个特定排序标准 , 默认是哈希值 ;

集合 Set , 多重集合 MultiSet , 映射 Map , 多重映射 MultiMap 是 关联式容器 ;如下图所示 , 关联式容器的元素位置与特定规则有关 , 与插入时间和位置无关 ;3、常用的 STL 容器常用的 STL 容器 :

向量 vector : 是连续存储的元素 , 其内存是连续的 ;可以 访问和修改任意元素 , 但在 序列尾部 进行 插入 和 删除时 , 具有常量时间复杂度 ;需导入 头文件 ;双端队列 deque : 与向量类似 , 不同之处是 双端队列可以 在序列头部 插入和删除 操作 , 具有常量时间复杂度 ; 其本质是 连续存储 的 指向不同元素 的 指针 所组成的 数组 ;需导入 头文件 ;列表 list : 列表是由 节点 组成的双向链表 , 每个节点保存一个数据元素 , 同时有两个指针 , 分别指向 前驱和后继 ;对任意元素的访问与对两端的距离成正比，但对某个位置上插入和删除一个项的花费为常数时间需导入 头文件 ;集合 set : 元素不能重复的集合 ; 本质是 " 红黑树 " ;每个节点都包含一个元素 , 节点之间以某种作用于元素对的谓词排列 , 没有两个不同的元素能够拥有相同的次序 ;需导入 头文件 ;多重集合 multiset : 元素可以重复的集合 , 本质是 两个元素 次序相等 ; 多重集合 的元素在容器中根据指定的比较函数按键值排序 , 因此它是有序的 ;多重集合 的元素不需要具有唯一键 , 一个键值可具有多个相关联的元素值 ;需导入 头文件 ;映射 map : 存放键值对 , 一个键对应一个值 ; 需导入