C++_STL_xx_番外01_关于STL的总结(常见容器的总结；关联式容器分类及特点；二叉树、二叉搜索树、AVL树(平衡二叉搜索树)、B树、红黑树)
文章目录
- 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树、红黑树，红黑树这样学才对！，红黑树、平衡二叉查找树