1、六大组件介绍
- 容器：数据结构，用来存放数据
- 算法：常用算法
- 迭代器：容器和算法之间的胶合剂，“范型指针”
- 仿函数：一种重载了operator()的类，使得这个类的使用看上去像一个函数
- 配置器：为容器分配并管理内存
- 适配器：修改其他组件接口
2、STL 常用的容器有哪些以及各自的特点是什么?
| 名称 | 特点 |
|---|---|
| vector | 底层数据结构为数组，支持快速随机访问 |
| list | 底层数据结构为双向链表，支持快速增删 |
| deque | 底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问 |
| stack | 底层一般用deque/list实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时 |
| queue | 底层一般用deque/list实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时 |
| priority_queue | 底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现 |
| set | 底层数据结构为红黑树，有序，不重复 |
| multiset | 底层数据结构为红黑树，有序，可重复 |
| map | 底层数据结构为红黑树，有序，不重复 |
| multimap | 底层数据结构为红黑树，有序，可重复 |
| unordered_set | 底层数据结构为hash表，无序，不重复 |
| unordered_multiset | 底层数据结构为hash表，无序，可重复 |
| unordered_map | 底层数据结构为hash表，无序，不重复 |
| unordered_multimap | 底层数据结构为hash表，无序，可重复 |
3、vector 和 list 的区别
- vector底层实现是数组，所以在内存中是连续存放的，随机读取效率高，但插入、删除效率低；list底层实现是双向链表，所以在内存中是任意存放的，插入、删除效率高，但访问元素效率低
- vector在中间节点进行插入、删除会导致内存拷贝，而list不会
- vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请
4、vector 扩容原理
以原内存空间大小的两倍配置一份新的内存空间，并将原空间数据拷贝过来进行初始化
5、map 和 set 有什么区别
- map中的元素是键值对；Set仅是关键字的简单集合
- set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key
- map支持用关键字作下标操作，set不支持下标操作
6、map 和 unordered_map 的区别
- map内部实现了一个红黑树，红黑树的每一个节点都代表着map的一个元素，因此所有元素都是有序的，对其进行查找、插入、删除得效率都是O(log n)；但是，因为每个结点都需要额外保存数据，所以空间占用率比较高
- unordered_map内部实现了一个哈希表，因此内部元素是无序的，对其进行查找、插入、删除得效率都是O(1)；但是建立哈希表比较费时
7、STL 中迭代器的作用，有指针为何还要迭代器
- Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示
- 迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、*、++、–等，相当于一种智能指针
- 迭代器产生原因：Iterator采用的是面向对象的思想，把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果