STL的定义：包括了三类，算法容器和迭代器。
算法：包括排序、复制等常用算法，以及不同容器特定的算法。
容器：数据存放的形式，包括序列式容器和关联式容器。序列式容器就是list、vector等。关联式容器就是set、map等。
迭代器：就是在不暴露容器内部结构的情况下对容器的遍历。
容器
1 vector的底层原理
vector底层是一个动态数组，包含三个迭代器。start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。
当空间不够装下数据的时候，回自动申请另一片更大的空间（1.5倍或2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间。
当释放或者删除（vec.clear())里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。因此，对vector的任何操作一旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了。
2 list的底层原理
list底层是一个双向链表，以结点为单位存放数据，结点的地址在内存中不一定连续，每次插入或删除一个元素，就配置或者释放一个元素空间。
list不支持随机存取，适合需要大量的插入和删除，而不关心随机存取的应用场景。
3 deque的底层原理
deque是一个双向开口的连续线性空间(双端队列）,在头尾两端进行元素的插入跟删除操作都有理想的时间复杂度。
q：什么情况下用vector，什么情况下用list，什么情况下用deque？
A：vector可以随机存储元素，不需要挨个查找，但是在非尾部插入删除数据时，效率很低，适合对象简单，对象数量变化不大随机访问频繁。
list不支持随机存储，适用于对象大、对象数量变化频繁、插入和删除频繁、比如写多读少的场景。
需要从首尾两端进行插入或删除操作的时候需要选择deque。
4 map、set、multiset、multimap的底层原理
map、set、multiset、multimap的底层实现都是红黑树，epoll模型的底层数据结构也是红黑树。
set和multiset会根据特定的排序准则自动将元素排序，set中元素不允许重复，multiset可以重复。
map和multimap将key和value组成的pair作为元素，根据key的排序准则自动将元素排序，map中元素的key不允许重复，multimap可以重复。
5 unordered_map、unoredred_set的底层原理
unordered_map的底层是一个防冗余的哈希表（采用除留余数法）。
迭代器
1 迭代器的底层原理
迭代器是连接容器和算法的一种重要桥梁，通过迭代器可以在不了解容器内部原理的情况下遍历容器。它的底层实现包含两个重要的部分：萃取技术和模板偏特化。
萃取技术（traits）可以进行类型推导，根据不同类型可以执行不同的处理流程，比如容器是vector，那么traits必须推导出其迭代器类型为随机访问迭代器，而list则为双向迭代器。
例如STL算法库中的distance函数，distance函数接受两个迭代器参数，然后计算他们两者之间的距离。显然对于不同的迭代器计算效率差别很大。比如对于vector容器来说，由于内存是连续分配的，因此指针直接相减即可获得两者的距离；而list容器是链式表，内存一般都不是连续分配，因此只能通过一级一级调用next()或其他函数，每调用一次再判断迭代器是否相等来计算距离。vector迭代器计算distance的效率为O(1),而list则为O(n),n为距离的大小。
使用萃取技术（traits）进行类型推导的过程中会使用到模板偏特化。模板偏特化可以用来推导参数，如果我们自定义了多个类型，除非我们把这些自定义类型的特化版本写出来，否则我们只能判断他们是内置类型，并不能判断他们具体属于是个类型。
当函数，类或者一些封装的通用算法中的某些部分会因为数据类型不同而导致处理或逻辑不同时，traits会是一种很好的解决方案。
2 迭代器的种类
输入迭代器：是只读迭代器，在每个被遍历的位置上只能读取一次。例如上面find函数参数就是输入迭代器。
输出迭代器：是只写迭代器，在每个被遍历的位置上只能被写一次。
前向迭代器：兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。但它不支持operator–，所以只能向前移动。
双向迭代器：很像前向迭代器，只是它向后移动和向前移动同样容易。
随机访问迭代器：有双向迭代器的所有功能。而且，它还提供了“迭代器算术”，即在一步内可以向前或向后跳跃任意位置， 包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it – n、it += n、 it -= n、it1 – it2和it[n]等操作。
