- 《面向对象C++程序设计》皮德常 编著 清华大学出版社 2017
- 《C++ Primer Plus (第6版)中文版》Stephen Prata 著 张海龙 袁国忠 译 人民邮电出版社 2012
1 C++容器类的底层实现
以下分别用K、T指代泛型参数。
| C++ | 特点 | 底层数据结构 |
|---|---|---|
T 变量名[数值]、array<T,数值> |
固定大小数组。支持快速随机访问，不能添加和删除元素 | 普通数组 |
vector<T> |
可变大小数组。支持快速随机访问，在尾部之外的位置插入或删除元素可能很慢 | 数组 |
list<T> |
双向循环链表。只支持双向顺序访问，在任何位置进行插入删除操作都很快 | 链表 |
forward_list<T> |
单向链表。只支持单向顺序访问，在任何位置进行插入删除操作都很快 | 链表 |
stack<T> |
栈。后进先出容器 | 数组或链表 |
queue<T> |
队列。先进先出容器 | 数组或链表 |
deque<T> |
双端队列。支持首尾快速增删，也支持随机访问 | 底层数据结构为一个中央控制器和多个缓冲区 |
priority_queue<T> |
优先级队列。队列中的元素具有优先级，优先级最高的元素位于队首，队首元素可以弹出队列 | 二叉大根堆 |
unordered_set<T> |
集合。关键字无序且不可重复出现 | 哈希表 |
set<T> |
集合。关键字有序且不可重复出现 | 红黑树 |
unordered_map<K,T> |
关联数组。保存键值对，键值对无序且键不可重复出现 | 哈希表 |
map<K,T> |
关联数组。保存键值对，键值对有序且键不可重复出现 | 红黑树 |
注意 stack、queue、priority_queue 均为容器适配器。stack 和 queue 底层一般用 list 或 deque 实现，不用 vector 的原因应该是容量大小有限制，扩容耗时。priority_queue 一般用 vector 作底层容器。
2 unordered_map 和 map 区别
- map 内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而 AVL 是严格平衡二叉搜索树），因此 map 内部的所有元素都是有序的，存取一个元素时间复杂度是 O(logn)
- unordered_map 内部实现了一个哈希表，其元素的排列顺序是无序的，取一个元素时间复杂度是 O(1)
3 红黑树
红黑树是一颗满足如下性质的二叉查找树：
- 每个结点或者为黑色或者为红色；
- 根结点为黑色；
- 每个叶节点为黑色；
- 如果一个结点为红色，那么他的两个子结点为黑色；
- 对于每个结点，从该节点到其所有子孙叶结点的路径中，所包含的黑色结点数量必须相同。
红黑树的每个结点的属性除了有一个key、3个指针(parent、lchild、rchild)以外，还有个color属性。
通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。