本文主要是介绍【C++ 面试 - STL】每日 3 题(九),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
✍个人博客:Pandaconda-CSDN博客
📣专栏地址:http://t.csdnimg.cn/fYaBd
📚专栏简介:在这个专栏中,我将会分享 C++ 面试中常见的面试题给大家~
❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创作的最大动力💪
25. 说一下 STL 每种容器对应的迭代器
26. STL 的两级空间配置器
allocate 包装 malloc,deallocate 包装 free
allocator 就是用来分配内存的,最重要的两个函数是 allocate 和 deallocate,就是用来申请内存和回收内存的,外部(一般指容器)调用的时候只需要知道这些就够了。
1、首先明白为什么需要二级空间配置器?
我们知道动态开辟内存时,要在堆上申请,但若是我们需要频繁的在堆开辟释放内存,则就会在堆上造成很多外部碎片,浪费了内存空间;
每次都要进行调用 malloc、free 函数等操作,使空间就会增加一些附加信息,降低了空间利用率;
随着外部碎片增多,内存分配器在找不到合适内存情况下需要合并空闲块,浪费了时间,大大降低了效率。
于是就设置了二级空间配置器,当开辟内存 <= 128 bytes 时,即视为开辟小块内存,则调用二级空间配置器。
关于 STL 中一级空间配置器和二级空间配置器的选择上,一般默认选择的为二级空间配置器。 如果大于 128 字节再转去一级配置器器。
一级配置器
一级空间配置器中重要的函数就是 allocate、deallocate、reallocate。 一级空间配置器是以 malloc(),free(),realloc() 等 C 函数执行实际的内存配置。大致过程是:
1、直接 allocate 分配内存,其实就是 malloc 来分配内存,成功则直接返回,失败就调用处理函数。
2、如果用户自定义了内存分配失败的处理函数就调用,没有的话就返回异常。
3、如果自定义了处理函数就进行处理,完事再继续分配试试。
二级配置器
1、维护 16 条链表,分别是 0-15 号链表,最小 8 字节,以 8 字节逐渐递增,最大 128 字节,你传入一个字节参数,表示你需要多大的内存,会自动帮你校对到第几号链表(如需要 13 bytes 空间,我们会给它分配 16 bytes 大小),在找到第 n 个链表后查看链表是否为空,如果不为空直接从对应的 free_list 中拔出,将已经拨出的指针向后移动一位。
2、对应的 free_list 为空,先看其内存池是不是空时,如果内存池不为空:
(1)先检验它剩余空间是否够 20 个节点大小(即所需内存大小(提升后) * 20),若足够则直接从内存池中拿出 20 个节点大小空间,将其中一个分配给用户使用,另外 19 个当作自由链表中的区块挂在相应的 free_list 下,这样下次再有相同大小的内存需求时,可直接拨出。
(2)如果不够 20 个节点大小,则看它是否能满足 1 个节点大小,如果够的话则直接拿出一个分配给用户,然后从剩余的空间中分配尽可能多的节点挂在相应的 free_list 中。
(3)如果连一个节点内存都不能满足的话,则将内存池中剩余的空间挂在相应的 free_list 中(找到相应的 free_list),然后再给内存池申请内存,转到 3。
3、内存池为空,申请内存。此时二级空间配置器会使用 malloc() 从 heap 上申请内存,(一次所申请的内存大小为 2 * 所需节点内存大小(提升后)* 20 + 一段额外空间),申请 40 块,一半拿来用,一半放内存池中。
4、malloc 没有成功。在第三种情况下,如果 malloc() 失败了,说明 heap 上没有足够空间分配给我们了,这时,二级空间配置器会从比所需节点空间大的 free_list 中一一搜索,从比它所需节点空间大的 free_list 中拔除一个节点来使用。如果这也没找到,说明比其大的 free_list 中都没有自由区块了,那就要调用一级适配器了。而一级配置器其实也是使用 malloc(),但是它有 out-of-memeory 处理机制,或许有机会拿其它的内存拿来此处使用。如果还是申请不成功,就会发出 bad_alloc 异常。
释放时调用 deallocate() 函数,若释放的 n > 128,则调用一级空间配置器,否则就直接将内存块挂上自由链表的合适位置。
STL 二级空间配置器虽然解决了外部碎片与提高了效率,但它同时增加了一些缺点:
- 因为自由链表的管理问题,它会把我们需求的内存块自动提升为 8 的倍数,这时若你需要 1 个字节,它会给你 8 个字节,即浪费了 7 个字节,所以它又引入了内部碎片的问题,若相似情况出现很多次,就会造成很多内部碎片;
- 二级空间配置器是在堆上申请大块的狭义内存池,然后用自由链表管理,供现在使用,在程序执行过程中,它将申请的内存一块一块都挂在自由链表上,即不会还给操作系统,并且它的实现中所有成员全是静态的,所以它申请的所有内存只有在进程结束才会释放内存,还给操作系统,由此带来的问题有:
- 即我不断的开辟小块内存,最后整个堆上的空间都被挂在自由链表上,若我想开辟大块内存就会失败;
- 若自由链表上挂很多内存块没有被使用,当前进程又占着内存不释放,这时别的进程在堆上申请不到空间,也不可以使用当前进程的空闲内存,由此就会引发多种问题。
一级分配器
GC4.9 之后就没有第一级了,只有第二级
二级分配器
—— default_alloc_template 剖析
有个自动调整的函数:你传入一个字节参数,表示你需要多大的内存,会自动帮你校对到第几号链表(0-15 号链表,最小 8 字节,最大 128 字节)
allocate 函数:如果要分配的内存大于 128 字节,就转用第一级分配器,否则也就是小于 128 字节。那么首先判断落在第几号链表,定位到了,先判断链表是不是空,如果是空就需要充值,(调节到 8 的倍数,默认一次申请 20 个区块,当然了也要判断 20 个是不是能够申请到,如果只申请到一个那就直接返回好了,不止一个的话,把第 2 到第 n 个挨个挂到当前链表上,第一个返回回去给容器用,n 是不大于 20 的,当然了如果不在 1 - 20 之间,那就是内存碎片了,那就先把碎片挂到某一条链表上,然后再重新 malloc 了,malloc 2*20 个块)去内存池去拿或者重新分配。
27. sort 的底层实现
std::sort 主要是三种算法的结合体:插入排序,快速排序,堆排序。
std::sort 根据上文提到的几种算法的优缺点,对排序算法进行整合。
- 快速排序,递归排序到一定深度后,数据已经被分为多个子区域,子区域里面的数据可能是无序的,但是子区域之间已经是有序了。
- 在这多个子区域里,如果某个子区域数据个数大于阈值(16),采用堆排序,使得某个子区域内部有序。
- 剩下的没有被堆排序的小区域,数据量都是小于阈值的,最后整个数据区域采用插入排序。
- std::sort 采用的是分治思维,先采用快速排序,将整个区域分成多个子区域,每个子区域内部根据数据量采用不同算法。
- 分治后,各个子区域局部有序后再通过整个区域进行排序。
哪些容器可以用 sort 进行排序?
STL 的所有关联型容器都有自动排序的功能(底层结构采取 RB-tree),所以不需要用到这个 sort 算法。
至于序列式容器中的 stack、queue 和 priority-queue 都有特定的出入口,不允许用户对元素进行排序。
剩下的 vector、deque 和 list,前两者的迭代器都属于 RandomAccessIterators,适合使用 sort 算法;list 的迭代器则属于 BidirectionalIterators;不在 STL 标准之列的 slist,其迭代器更属于 ForwardIterator,都不适合使用 sort 算法,如果是要对 list 或者 slist 中的元素进行排序,应该使用他们自己的 member function sort()。
这篇关于【C++ 面试 - STL】每日 3 题(九)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!