文章目录
- 1. 常用容器总结
- 2. 关联式容器分类
- 3. 二叉树、二叉搜索树、AVL树、B树、红黑树
1. 常用容器总结
针对常用容器的一些总结:
2. 关联式容器分类
关联式容器分为两大类: 基于红黑树的set和map;基于hash表的unorder_set和unorder_map
-
set和map: 用于
存储键值唯一的元素
;默认按照键值升序排布;基于平衡二叉搜索树
,因此采用中序遍历之后是升序
,这也是为什么能够实现有序排布的原因;适合有序排布需求,时间复杂度O(logn)
-
unorder_set和unorder_map:
用于存储键值唯一的元素
,与set和map一致;元素是无序的;操作的时间复杂度O(1)
-
multiset和multimap与set和map的区别就是允许键值重复
-
不管是map还是multimap unorder_map存储的都是pair(对组),C++中提供了相应的模板,对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用pair的两个公有属性first和second访问,pair的第一元素被视为键值,第二元素被视为实值
3. 二叉树、二叉搜索树、AVL树、B树、红黑树
二叉树、二叉搜索树、AVL树、B树、红黑树相关知识查看:教程资料,二叉树、二叉搜索树、AVL树、B树、红黑树,红黑树这样学才对!,红黑树、平衡二叉查找树