《STL 源码剖析》内存管理，迭代器

《STL 源码剖析》内存管理，迭代器

阅读本文大概需要 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 提出的问题！也就是说算法通过仿函数来处理容器里面的元素）

路遥知马力，日久见人心，相信自己，相信相信的力量！

无论如何，这几个月都要扛过去鸭！

认真的人，自带光芒！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。