STL的介绍
STL,Standard Template Library，标准模板库，是一套基于模板的容器类库。STL包含6大部件：容器、迭代器、算法、仿函数、适配器和空间配置器。
容器：容纳一组元素的对象。包括序列式容器，关联式容器.
迭代器：提供一种访问容器中每个元素的方法。
仿函数：一个行为类似函数的对象，调用它就像调用函数一样。
算法：包括查找算法、排序算法等等。
适配器：用来修饰容器等，比如queue和stack，底层借助了deque。
空间配置器：负责空间配置和管理。
各种容器的特点和适用情况?
1.vector:底层数据结构为数组 ，支持快速随机访问。
2.list:底层数据结构为双向链表，支持快速增删。
3.deque:底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问。
4.stack:底层一般用 list 和 deque 实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
5.queue:底层一般用 list 和 deque 实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）
6.priority_queue:的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现
7.set 和 map:底层数据结构为红黑树，有序，不重复。
8.multiset 和 multimap:底层数据结构为红黑树，有序，可重复。
使用场景
1、如果你需要高效的随机存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随机存取，则应使用list
3、如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque。
4、如果你要存储一个数据字典，并要求方便地根据key找value，那么map是较好的选择
5、如果你要查找一个元素是否在某集合内存中，则使用set存储这个集合比较好
vector的底层原理
vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。
当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5倍或者2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间【vector内存增长机制】。
当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。
因此，对vector的任何操作一旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了
vector中的reserve和resize的区别？
reserve()是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化push_back），就可以提高效率，其次还可以减少多次要拷贝数据的问题。reserve只是保证vector中的空间大小（capacity）最少达到参数所指定的大小n。reserve()只有一个参数。 resize()可以改变有效空间的大小，也有改变默认值的功能。capacity的大小也会随着改变。resize()可以有多个参数。
vector中的size和capacity的区别？
size表示当前vector中有多少个元素（finish - start），而capacity函数则表示它已经分配的内存中可以容纳多少元素（end_of_storage - start）。
vector的元素类型可以是引用吗？
vector的底层实现要求连续的对象排列，引用并非对象，没有实际地址，因此vector的元素类型不能是引用。
vector 迭代器失效的情况
当插入一个元素到vector中，由于引起了内存重新分配，所以指向原内存的迭代器全部失效。
当删除容器中一个元素后,该迭代器所指向的元素已经被删除，那么也造成迭代器失效。erase方法会返回下一个有效的迭代器，所以当我们要删除某个元素时，需要it=vec.erase(it);。
正确释放vector的内存？
vec.clear()：清空内容，但是不释放内存。
vector
vec.shrink_to_fit()：请求容器降低其capacity和size匹配。
list 的底层原理
list的底层是一个双向链表，以结点为单位存放数据，结点的地址在内存中不一定连续，每次插入或删除一个元素，就配置或释放一个元素空间。
list不支持随机存取，如果需要大量的插入和删除，而不关心随即存取
deque 的底层原理
deque是一个双向开口的连续线性空间（双端队列），可在头尾两端进行元素的插入跟删除操作。
priority_queue 的底层原理
priority_queue：优先队列，其底层是用堆来实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。
map,set,multiset,multimap 底层原理
map 、set、multiset、multimap的底层实现都是红黑树 。
map,set,multiset,multimap 特点
set和multiset会根据特定的排序准则自动将元素排序，set中元素不允许重复，multiset可以重复。
map和multimap将key和value组成的pair作为元素，根据key的排序准则自动将元素排序（因为红黑树也是二叉搜索树，所以map默认是按key排序的），map中元素的key不允许重复，multimap可以重复。
map和set的增删改查速度为都是 O(logn)，是比较高效的。
为何 map 和 set 插入删除效率比其他序列容器高？而且每次inset之后，以前保存的iterator 不失效？
因为存储的是结点，不需要内存拷贝和内存移动。
因为插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指向内存的指针也不会变。
为何 map 和 set 不能像 vector 一样有个 reserve 来预分配数据？
因为在map和set内部存储的已经不是元素本身了，而是包含元素的结点
unordered_map, unordered_set 底层原理？
unordered_map的底层是一个防冗余的哈希表（采用除留余数法）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，时间复杂度为O(1)；而代价仅仅是消耗比较多的内存。
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数（一般使用除留取余法），也叫做散列函数），使得每个元素的key都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照key为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。
unordered_map 和 map 区别？
内部实现机理
map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。
unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的
map底层是红黑树，1.增删改查都是平稳的logn的复杂度，2.二叉查找树，数据有序
unordered_map底层是hash表，查找是o1，构造时候如果有冲突时间成本会增加，并且做不到数据有序；
冲突解决：当冲突数小于8的时候用链式地址法解决冲突，当冲突数大于8时使用红黑树
优缺点以及适用处
- map
- 优点
- 有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
- 红黑树，内部实现一个红黑书使得map的很多操作在的时间复杂度下就可以实现，因此效率非常的高
- 适用处：对于那些有顺序要求的问题，用map会更高效一些
- 缺点:
- 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间
- 优点
- unordered_map
- 优点：
- 因为内部实现了哈希表，因此其查找速度非常的快
- 适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map
- 缺点：
- 哈希表的建立比较耗费时间
- 优点：
- map
map 和 set 区别?
） map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。
2） map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。
3） set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。
4） map支持下标操作，set不支持下标操作。map可以用key做下标，
vector 和 list 区别?
1） vector， 连续存储的容器，动态数组，在堆上分配空间 ；
底层实现：数组。
如果没有剩余空间了，则会重新配置原有元素个数的两倍空间，然后将原空间元素通过复制的方式初始化新空间，再向新空间增加元素。
适用场景：经常随机访问，且不经常对非尾节点进行插入删除。
2）list，动态链表，在堆上分配空间，每插入一个元素都会分配空间，每删除一个元素都会释放空间。
底层：双向链表
访问：随机访问性能很差，只能快速访问头尾节点。
适用场景：经常插入删除大量数据
2） vector在中间节点进行插入删除会导致内存拷贝，list不会。
3） vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。
4） vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。
迭代器的底层原理？
迭代器是连接容器和算法的一种重要桥梁，通过迭代器可以在不了解容器内部原理的情况下遍历容器。它的底层实现包含两个重要的部分：萃取技术和模板偏特化。
萃取技术（traits）可以进行类型推导，根据不同类型可以执行不同的处理流程，比如容器是vector，那么traits必须推导出其迭代器类型为随机访问迭代器，而list则为双向迭代器。
迭代器的作用，有指针为何还要迭代器？
1） Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。
2） 迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->、*、++、–等，相当于一种智能指针。
3） 迭代器产生原因：
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。
迭代器的种类？
输入迭代器：是只读迭代器，在每个被遍历的位置上只能读取一次。例如上面find函数参数就是输入迭代器。
输出迭代器：是只写迭代器，在每个被遍历的位置上只能被写一次。
前向迭代器：兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。但它不支持operator–，所以只能向前移动。
双向迭代器：很像前向迭代器，只是它向后移动和向前移动同样容易。
随机访问迭代器：有双向迭代器的所有功能。而且，它还提供了“迭代器算术”，即在一步内可以向前或向后跳跃任意位置， 包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。
迭代器如何插入和删除的呢？
vector
1、当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。
2、当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。
3、当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。
对于 list,map，set，multimap，multiset），删除当前的 iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前的iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入，删除一个结点不会对其他结点造成影响
STL线程安全的情况？
- 多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能 有任何写入者操作这个容器；
- 对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。
STL线程不安全的情况？
- 在对同一个容器进行多线程的读写、写操作时；
- 在每次调用容器的成员函数期间都要锁定该容器；
- 在每个容器返回的迭代器（例如通过调用begin或end）的生存期之内都要锁定该容器；
- 在每个在容器上调用的算法执行期间锁定该容器。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
