- 红黑树的特性与其在C++ STL中的应用
map 、set、multiset、multimap的底层实现都是红黑树,epoll模型的底层数据结构也是红黑树,linux系统中CFS进程调度算法,也用到红黑树。
红黑树的特性:
- 根节点是黑色
- 不能有两个连续的红节点
- 空指针是黑色
- 从任意一个结点出发,到后代中空指针的路径上,均包含相同数量的黑色结点。
- STL内存分配
- STL map
- STL 相关: STL 中的内存管理(allocator)的原理, 以及如何让它线程安全。
http://yaocoder.blog.51cto.com/2668309/1208465/ - STL 源码中的 hash 表的实现
- STL 的 unordered_map 和 map 的区别
- 介绍一下 STL 源码的内容。
- vector分配内存的方式
先申请一定的大小的数组, 当数组填满之后,另外申请一块原数组两倍大的新数组, 然后把原数组的数据拷贝到新数组, 最后释放原数组的大小。 详情参考 《STL源码剖析(侯捷)》。
问STL库,vector的内存管理,deque的内存管理,list的排序 - STL也问了一些问题:比如vecotr 和list 的区别,适用情况
vector的扩容机制,问到了源码层次。
4.STL中的迭代器失效问题
11.map /set容器的实现原理(红黑树知识+STL容器内部原理)
- STL中仿函数有什么用,和函数指针有什么不同,哪个效率高