关联式容器面试题合集
- 说说你所知道的容器都有哪些？
vector，list，map，set，mulimap，muliset等等
- map与set的区别？使用map有哪些优势？
set是一种关联式容器，其特性如下：
- set以RBTree作为底层容器
- 所得元素的只有key没有value，value就是key
- 不允许出现键值重复
- 所有的元素都会被自动排序
- 不能通过迭代器来改变set的值，因为set的值就是键
map和set一样是关联式容器，它们的底层容器都是红黑树，区别就在于map的值不作为键，键和值是分开的。它的特性如下：
- map以RBTree作为底层容器
- 所有元素都是键+值存在
- 不允许键重复
- 所有元素是通过键进行自动排序的
- map的键是不能修改的，但是其键对应的值是可以修改的
- map的底层原理，说下红黑树？
底层容器是红黑树，再详细说一下红黑树
- map的迭代器会失效吗？什么情况下会失效？
会失效，删除erase的时候会失效，it迭代器被删除后，it就会失效，找不到下一个了。要用一个临时变量记住it++
- AVLTree和RBTree的对比，为什么map使用了红黑树？红黑树的优势是什么？
看下图：
- AVLTree和RBTree所达到的平衡有什么区别？
上图
- RBTree节点的颜色是红或者黑色？其他颜色行不行？
当然可以啊，换成其他色也可以，原理还是一样的。
- RBTree是如何插入？如何旋转的？
插入的时候和二叉搜索树插入方法是一样的，但是插入节点必须是红色，然后根据红黑树的规则进行旋转和变色。