《STL 源码剖析》内存管理，迭代器
这是 herongwei 的第 86 篇原创
阅读本文大概需要 6.6 分钟。
最近一段时间，公众号没有更新文章了，后台一些可爱的读者们在催我了，说咋好久没更新了，很抱歉，自己这段日子，既要忙着找工作，也要准备写论文，事情稍微多一些，但是没有及时更新确实是不可争辩的，自己偷懒，这没啥好说的。
想起羽毛球天王林丹的一段话：既然选择职业选手这条路，不是你状态不好你就随便能输球，不是你不想参加比赛就不能参加！
这段话，送给最近和我一样既要忙着找工作又要忙着写论文的同学们，同时也送给我自己，希望大家能把握好这几个月，努力拼一把，相信自己，相信相信的力量！
关于公众号的定位，以及输出内容的方向，必须明确下来，该写什么？该怎么写？让读者清楚的知道这个公众号核心在哪里？以及是否需要关注？非常有必要！下面把这个公众号的定位简单说明一下：
包括但不限于 Linux C/C++，后台，分布式开发一些技术分享；
考研，读研相关，编程学习，精力管理，认知管理的分享；
平常读书笔记，个人思考，随笔的分享；
后续可能会开通另外一个小号，关于小号，可能主要写一些自己的平常感悟，随笔为主~后续开通了第一时间会通知大家，有兴趣的持续关注就好~~
1、正文 STL 介绍
C++ STL 一共提供了六大组件，包括容器，算法，迭代器，仿函数，配接器和配置器，彼此可以组合套用。
容器通过配置器取得数据存储空间；
算法通过迭代器存取容器内容；
仿函数可以协助算法完成不同的策略变化；
配接器可以应用于容器、仿函数和迭代器。
1、容器：包括各种数据结构，如vector，queue， deque，set， map，用来存放数据，分为序列式容器和关联式容器，实现的角度来讲是一种类模板。
2、算法：各种常用的算法，如sort (插入，快排，堆排序)， search (二分查找），从实现的角度来讲是一种方法模板。
3、迭代器：从实现的角度来看，迭代器是一种将 operator，operator->，operator++，operator-等指针相关操作赋予重载的类模板，所有的 STL 容器都有自己的迭代器。
4、仿函数：从实现的角度看，仿函数是一种重载了 operator() 的类或者类模板。可以帮助算法实现不同的策略。
5、配接器：一种用来修饰容器或者仿函数或迭代器接口的东西。
6、配置器：负责空间配置与管理，从实现的角度讲，配置器是一个实现了动态空间配置、空间管理,空间释放的类模板。
2、内存管理 allocator
C++ SGI 设计了双层级配置器。
第一级配置器：__malloc_alloc_template
第二级配置器 ：__default_alloc_template
第一级配置器直接使用 malloc()和 free()完成内存的分配和回收。第二级配置器则根据需求量的大小选择不同的策略执行。
对于第二级配置器，如果需求块大小大于 128bytes，则直接转而调用第一级配置器，使用 malloc()分配内存。
如果需求块大小小于 128 bytes，第二级配置器中维护了 16 个自由链表，负责 16 种小型区块的次配置能力。
即当有小于 128bytes 的需求块要求时，首先查看所需需求块大小所对应的链表中是否有空闲空间，如果有则直接返回，如果没有，则向内存池中申请所需需求块大小的内存空间，如果申请成功，则将其加入到自由链表中。
如果内存池中没有空间，则使用 malloc() 从堆中进行申请，且申请到的大小是需求量的二倍（或二倍＋n 附加量），一倍放在自由空间中，一倍（或一倍＋n）放入内存池中。
如果 malloc()也失败，则会遍历自由空间链表，四处寻找“尚有未用区块，且区块够大”的 freelist，找到一 块就挖出一块交出。
如果还是没有，仍交由 malloc()处理，因为 malloc()有 out-of-memory 处理机制或许有机会释放其他的内存拿来用，如果可以就成功， 如果不行就报 bad_alloc 异常。
3、迭代器 traits
traits 萃取迭代器的性质：
value_type,difference_type,pointer, reference,iteratior_category。
自己开发的容器，要有自己的迭代器，要继承有这五个部分的 typedef，才能是自己的定义与原来的一些算法更兼容。
另外，迭代器有五个类型：
InputIterator（输入迭代器）；
OutputIterator（输出迭代器）；
ForwardIterator（前向迭代器）；
BidirectionalIterator（双向迭代器）；
RandomAccessIterator（随机迭代器）；
将迭代器分为几种类型是因为在算法中根据 traits 萃取出 的不同迭代器类型，内部可以写出更加高效合适的实现功能的代码。
iterator_traits 就像是一种萃取机，你想要什么东西，你丢给这个萃取机器，它返回给你想要的东西。萃取 iterator 的特性（为什么要这样设计？因为算法要知道，这是算法给 iterator 提出的问题！也就是说算法通过仿函数来处理容器里面的元素）
路遥知马力，日久见人心，相信自己，相信相信的力量！
无论如何，这几个月都要扛过去鸭！
推荐阅读
认真的人，自带光芒！