STL总结

什么是C++ STL？
是一个标准模板库。作为标准库的重要组成部分，STL占据了标准库一半以上的内容。
六大组件。分别是容器，算法， 迭代器，适配器，分配器，仿函数。
1 容器作为STL的主体，是许多不同的数据结构
2、分配器为容器的实现分配应有的空间。，从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的Class Template。
3、泛型算法用来处理容器中的数据。各种常用算法如Sort,Search,Copy,Erase,从实现的角度来看，STL算法是一种Function Templates。
4、迭代器是泛型算法和容器之间的粘合剂
5、仿函数使得算法可以有更加灵活的自定义模式
6、适配器保证了自定义的功能可以和STL中现有的功能相融合。STL提供的Queue和Stack，虽然看似容器，其实只能算是一种容器配接器，因为 它们的底部完全借助Deque，所有操作有底层的Deque供应。

容器有哪些，简要介绍一下
顺序容器：vector,list,deque.
关联容器：map,set,unordered_map,unordered_set
三种适配器：栈stack 、队列queue 和优先级队列priority_queue 。

vector简要介绍：是一个动态数组，连续的存储空间，支持随机访问，插入删除比较慢。
底层是三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。一旦空间用完，就会申请一块更大的，通常是1.5倍或者两倍。把数据拷贝过去，释放原来的空间。（为什么要在1.5倍或2倍，太小的话，频繁拷贝数据开销大，大于2倍的话，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用），并且，重新分配空间会使原来的迭代器失效。当然，erase删除某个元素那个迭代器也会失效的。erase方法会返回下一个有效的迭代器，所以当我们要删除某个元素时，需要it=vec.erase(it);。

vector中的reserve和resize的区别
resverve跟capacity有关，只有一个参数，表示预分配空间的大小，不会初始化的，不能访问，如果参数大于原来的容量，就会找一个新的空间，小于等于的话不变。
resize和size有关，代表实际元素的个数。resize(n,t)代表调整为n个，初始化为t。

正确释放vector的内存(clear(), swap(), shrink_to_fit())
vec.clear()：清空内容，但是不释放内存。所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露。
vector().swap(vec)：清空内容，且释放内存
vec.shrink_to_fit()：请求容器降低其capacity和size匹配。
vec.clear();vec.shrink_to_fit();：清空内容，且释放内存。因为size为0，所以容量也是0

vector的元素类型可以是引用吗？
vector的底层实现要求连续的对象排列，引用并非对象，没有实际地址，因此vector的元素类型不能是引用

vector<int> vec(10,100);        创建10个元素,每个元素值为100
vec.resize(r,vector<int>(c,0)); 二维数组初始化
reverse(vec.begin(),vec.end())  将元素翻转
sort(vec.begin(),vec.end());    排序，默认升序排列
vec.push_back(val);             尾部插入数字
vec.size();                     向量大小
find(vec.begin(),vec.end(),1);  查找元素
iterator = vec.erase(iterator)  删除元素

deque
deque和vector类似，支持快速随机访问。二者最大的区别在于，vector只能在末端插入数据，而deque支持双端插入数据。 deque还支持从开始端插入数据：push_front()
deque的内存空间分布是小片的连续，小片间用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新分配空间后，原有的元素是不需要拷贝的。

deque 容器的分段存储结构，提高了在序列两端添加或删除元素的效率，但也使该容器迭代器的底层实现变得更复杂。
struct __deque_iterator{
…
T* cur;
T* first;
T* last;
map_pointer node;//map_pointer 等价于 T**
}
cur：指向当前正在遍历的元素；first：指向当前连续空间的首地址；last：指向当前连续空间的末尾地址；node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。借助这 4 个指针，deque 迭代器对随机访问迭代器支持的各种运算符进行了重载，能够对 deque 分段连续空间中存储的元素进行遍历。
比如迭代器++，如果到达边缘，就会跳跃到下一个连续空间，对 cur 重新赋值，first,last重新赋值

//重载前置 ++ 运算符
self & operator++(){
    ++cur;
    //处理 cur 处于连续空间边缘的特殊情况
    if(cur == last){
        //调用该函数，将迭代器跳跃到下一个连续空间中
        set_node(node+1);
        //对 cur 重新赋值
        cur = first;
    }
    return *this;
}

deque 容器除了维护先前讲过的 map 数组，还需要维护 start、finish 这 2 个 deque 迭代器
借助 start 和 finish，以及 deque 迭代器中重载的诸多运算符，就可以实现 deque 容器提供的大部分成员函数。

list
前面的都适合读多写少的场景，而list链表适合写入，不支持随机读取，适合写多读少的。ist是一个双向链表，因此它的内存空间是可以不连续的，通过指针来进行数据的访问，这使list的随机存储变得非常低效，因此list没有提供[]操作符的重载。但list可以很好地支持任意地方的插入和删除，只需移动相应的指针即可。

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。
关联容器支持高效的关键字查找与访问。两个主要的关联容器类型是map与set。

map
map容器提供一个键值对（key/value）容器，map与multimap差别仅仅在于multiple允许一个键对应多个值。对于迭代器来说，可以修改实值，而不能修改key。Map会根据key自动排序。

map 、set、multiset、multimap的底层实现都是红黑树，epoll模型的底层数据结构也是红黑树，linux系统中CFS进程调度算法，也用到红黑树。这里再详细说一下红黑树。

红黑树的特性：
每个结点或是红色或是黑色；
根结点是黑色；
每个叶结点是黑的；
如果一个结点是红的，则它的两个儿子均是黑色；
每个结点到其子孙结点的所有路径上包含相同数目的黑色结点。
背景：我们可以对树中所有节点进行排序和检索。所以有了二叉搜索树，左子树小于根，右子树大于根，二叉搜索树中序遍历升序。
但是如果插入一组元素正好是有序的时候，这时会让排序二叉树退化成链表。正常情况下的排序二叉树检索效率类似于二分查找，二分查找的时间复杂度为 O(log n)，但是如果排序二叉树退化成链表结构，那么检索效率就变成了线性的 O(n) 的。
所以有了平衡二叉树：左子树和右子树的深度之差的绝对值不超过1。递归定义。
但是AVL插入时需要调整，保持特点，开销有点大。所以有了红黑树，它放弃了深度之差的绝对值不超过1严格的定义，换来了插入调整次数少的优势（不大于3）
红黑树在最差情况下，最长的路径都不会比最短的路径长出两倍。其实红黑树并不是真正的平衡二叉树，它只能保证大致是平衡的。
红黑树插入元素时，插入的是红色节点，因为黑色肯定破坏最后一条性质。插入后可以变色保持性质，不行的话配合旋转，可以保证旋转不超过3次。

对于STL里的map容器，count方法与find方法，都可以用来判断一个key是否出现，mp.count(key) > 0统计的是key出现的次数，因此只能为0/1，而mp.find(key) != mp.end()则表示key存在。
map和set的增删改查速度为都是logn，是比较高效的。

map插入元素方式：主要两个，数组形式和pair形式,指定位置插入用Insert
mapStudent[key] = “student_one”;
mapStudent.insert(make_pair(1, “student_one”));

set也是一种关联性容器，它同map一样，底层使用红黑树实现，插入删除操作时仅仅移动指针即可，不涉及内存的移动和拷贝，所以效率比较高。

set获取元素：不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。
set 容器不提供下标操作符。为了通过键从 set 中获取元素，可使用 find运算。

unordered_map、unordered_set的底层原理
底层是哈希表，哈希函数（除留余数法），拉链法解决冲突。使得插入查找删除都是O(1)复杂度，代价就是内存大一点，

什么时候需要用hash_map，什么时候需要用map?
当你的业务有排序需求，可以用map；
当没有排序需求，且数据量很大，用hash_map。因为常数级别。数据量小的话都可以其实。
如果对内存要求比较严格，对时间不要求，用map。

queue
是在deque的基础上封装的。之所以选择deque而不选择vector是因为deque在删除元素的时候释放空间，同时在重新申请空间的时候无需拷贝所有元素。只能在尾部插入，头部删除。
stack是实现先进后出的功能，和queue一样，也是内部封装了deque。

适配器
在STL中扮演着转换器的角色，本质上是一种设计模式，用于将一种接口转换成另一种接口，从而使原本不兼容的接口能够很好地一起运作。
容器、迭代器、和仿函数都有适配器, 适配器不提供迭代器。

算法就是函数模板。算法通过迭代器来操纵容器中的元素。STL算法部分主要由头文件 algorithm,numeric,functional 组成。
查找算法(13个)：判断容器中是否包含某个值 find count
排序和通用算法(14个)：提供元素排序策略 sort
删除和替换算法(15个) swap replace
还有很多。算术，堆算法，关系算法等

如果一个类将()运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。函数对象是一个对象，但是使用的形式看起来像函数调用，实际上也执行了函数调用，因而得名。
函数对象有自己的类型，而普通函数则没有。在使用STL的容器时可以将函数对象的类型传递给容器作为参数来实例化相应的模板，从而来定制自己的算法，如排序算法。

迭代器及其失效的情况
STL的 算法 和 容器 是分离的，两者通过迭代器连接。算法的实现并不知道自己被传进来的参数是什么类型的容器。迭代器相当于一种泛型指针。
（失效和容器的底层内存实现有关）
序列式容器：以vector为例：如果push_back添加元素，如果容器有剩余空间，直接添加到尾部，这时只有end()失效，其他安全；如果没有空间了，会导致容器重新分配内存，然后将数据从原内存复制到新内存，再在尾部添加新元素。此时，由于内存重新分配，原迭代器(所有)都失效。 pop_back删除最后一个元素时最后一个元素的迭代器和end()会失效。
erase(iterator) 将删除点及之后的元素都向前移动一位，然后删除最后一个元素。因此，原迭代器中删除点之前的迭代器都有效，删除点之后的元素迭代器都失效。
insert会导致插入点元素后移动，后面的迭代器失效。
deque如果插入点之前的元素较少，会在容器头部插入一个元素，然后将插入点及其之前的所有元素向前移动一位，再在插入点创建新元素。否则，将插入点及其之后的元素向后移动一位，再在插入点创建新元素。因此，向前移动则导致原迭代器中插入点及插入点之前的迭代器都失效；向后移动则导致迭代器中插入点及插入点之后的迭代器都失效。

而在关联式容器以及list中，insert不会使迭代器失效，所有操作都只是针对节点移动指针，不会涉及到位置变化，操作影响的范围很小。（同样,list等非连续存储的容器，insert都不会失效，因为都是构造一个元素加到链表或者树上，不会出现空间不够的问题。）erase(iterator)只有被删除元素的迭代器失效，其他的没事（对于list也一样），所以在for循环中可以通过先保存iter++来避免这个问题。

分配器

空间配置器：空间配置器使用了两级配置器，如果配置空间大于128字节，使用一级配置器，若小于128字节，为了尽量避免内部存片，使用二级配置器。一级空间配置器直接调用malloc/free； 二级配置器使用了内存池技术和伙伴算法。
我们在编程中经常会用到malloc，free动态申请，释放内存。这就造成六个问题：
1.外部内存碎片问题。就是你申请的内存有一两个释放，因为太小了，新来的大一点的要求就无法满足，这块内存就浪费，也就是说，内存剩余总量足够，但是都是分散的。
（内部碎片指的是内存对齐,为了提高cpu访问效率，我们申请char,只需要1字节，但是会分配四个字节）
2、因为小块内存经常调用malloc，会产生调用性能问题。要知道，寻找空闲内存块需要时间，如果找不到合并内存块也是要时间的。
3、如果没有及时释放空间会造成内存泄漏。
那么，stl中空间配置器的实现策略是：
**如果用户申请空间大于128字节，就调用一级空间适配器，直接向系统申请，小于128字节，调用二级空间适配器，向内存池索取。**目的是减少内存碎片，增加系统性能。对于小块内存，我们使用内存池管理，因为内存池是连续分配的一块空间，不会产生很多内存碎片。虽然内部碎片无可避免。
一级空间配置器就是封装了malloc,free。

那么第二级空间配置器的做法是：
小于128的内存需求给内存池管理，此法也称为次层配置。每次配置一块大内存，并维护一个自由链表。
为了方便管理，SGI配置器会将需求调成8的倍数，比如需要30字节，分配32字节。自由链表分成16个，分别管理8,16，…,128字节大小的内存需求。如果下次有相等大小的需求，则从对应链表拨出，同时，内存释放时回收到自由链表中。所以，配置器不仅负责分配，还负责回收。
自由链表用union，保存指向下一个节点的指针和数据。union的长度在于最长变量的长度。union中所有变量是共享内存的，在obj中也就是一物二用。

怎么分配呢？比如一次需求为96字节
1、如果对应的自由链表不为空。则直接分配；
2.如果对应的自由链表为空，则从内存池中申请20个大小为96字节的节点。如果内存池不足20个，则拿出一个给用户，其余尽可能多的放到该链表中。
3、如果内存池连一个大小为96的节点都无法满足，则使用malloc函数为内存池在堆上申请内存。
4、如果申请失败，说明堆上也没有足够的空间分配了。则会从大于96的链表中拨出一个节点使用。
5、如果大于96的链表节点都没有的话，就调用终极办法----一级空间配置器函数oom-allocate函数。