第三次翻开这本书了，希望这次可以看下去，立个flag，以此为鉴。
STL六大组件
- 容器(containers)
各种数据结果，如vector, list, deque, set, map,用来存放数据。
- 算法(algorithms)
各种常用算法，如sort, search, copy, erase, 是一种function template
- 迭代器(iterators)
迭代器是一种将operator*, operator->, operator++, operator–等指针相关操作予以重载的class template, 是所谓的“泛型指针”。
- 仿函数(functors)
行为类似函数，可算作算法的某种策略(policy)，仿函数是一种重载了operator()的class或class template。
- 配接器(adapters)
一种用来修饰containers或functors或iterators接口的东西。如queue和stack，虽然看似内存，其实是一种容器配接器，因为它们的底层完全借助deque，所有的操作都由底层的deque供应。
- 配置器(allocators)
负责空间(内存，甚至可以是硬盘空间)的配置和管理
allocator
考虑到小型区块所可能造成得内存碎片问题，SGI设计了双层配置器
第一级配置器：
直接使用malloc()和free()
第二级配置器：
视不同情况采用不同的策略。
当申请空间大于128字节时，视之为“足够大”，便调用第一级配置器。
当申请空间小于128字节时，视之为“足够小”，使用复杂的memory pool方法。
第二级配置器
SGI第二级配置器会将任何小额内存需求量上调到8的倍数。并会维护16个free lists。各自管理大小为8，16，24 …128字节的链表。
- 大于128字节就调用第一级配置器
- 小于128字节就检查对应的free list, 如果free list有可用的区块，则直接拿来用
- 如果free list没有可用区块，就去内存池取空间给fress list使用。
内存池起始位置由内存起始位置的两个指针指定,中间的空间即为内存池空间。
static char* start_free;
static char* end_free;
- 如果内存池也没有足够空间，则用malloc heap空间，用来补充内存池。
- 如果山穷水尽，整个system heap空间都不够了，malloc行动失败，则会遍历寻找有无“尚有可用区块且区块够大”的free list, 找到了则挖一块交出，找不到则调用第一级配置器。第一级配置器其实也是使用malloc()来配置内存，但他有out of memory处理机制，或许有机会释放其它内存拿来此处使用，最差也可以发出bad_alloc异常。
iterator
iterator模式定义如下：提供一种方法，使之能依次巡访某个容器所含的各个元素，而又无需暴露该容器的内部表述方式。
iterator_traits
template<typename I>
struct iteraotr_traits { // traits 意为“特性”
typedef typename I::value_type value_type;
}
在每个容器定义中，会标识自自身迭代器的类型：
// vector 容器 随机迭代器。list 容器 双向迭代器。
template<...>
class vector{
public:
class iterator{
public:
typedef random_access_iterator_tag iterator_category;
// 类型定义： vector<T>::iterator::iterator_category 就是 random_access_iterator_tag
// 即类型里面还有一个类型， 而这个类型仅仅是用来标识 这个类是属于哪个类型的。
};
};
template<...>
class list{
public:
class iterator{
public:
typedef bidirectional_iterator_tag iterator_category;
};
};
这里选择迭代器模版和Advance的实现来讲解trait技术。
// advance为向前走n步
// advance 函数签名
template <class Iterator, class Distance>
void advance (Iterator& it, Distance n);
std::list<int> mylist;
for (int i=0; i<10; i++) mylist.push_back (i*10);
std::list<int>::iterator it = mylist.begin();
std::advance (it,5);
advance内部操作时候，需要知道advance的迭代器类型，看有哪些可用操作，比如随机访问器可以直接+= -=操作，前向仅支持++，输入输出均不支持，例子中的list属于双向，支持++，–。
所以在advance内部需要在取得某种类型信息，即迭代器的类型，进行不同的实现。
如何取得类型信息呢，容器类型::iterator::iterator_category（如上述2中的定义）
但是有一个问题，如果要支持内置类型，比如指针是一种随机迭代器类型，那么类型信息就不能放在类型内了，所以类型内的嵌套类的方式不能工作，所以类型的信息必须位于类型自身之外。
而trait标准技术是把它放进一个template，并进行一个偏特化版本，来实现迭代器所属类型trait。
// advance内部实现
// advance运行时确定使用哪种迭代器类型版本
template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
if (typeid(typename std::iterator_traits<IterT>::iterator_category)
== typeid(std::random_access_iterator_tag))
{
iter += d;
}
else if(前向迭代器类型)
{
if (d < 0){throw std::out_of_range("Negative distance");}
while (d--) ++iter;
}
else if(等等其他类型)
...
}
// 或者可以优化一下，不用typeid, 用函数重载机制
// advance编译器确定使用哪种迭代器类型版本
template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
doAdvance(iter, d, typename std::iterator_traits<IterT>::iterator_category());
}
// 比如 双向迭代器的函数 。重载doAdvance，实现不同的迭代器类型的具体操作。
// 可以看到迭代器类型仅仅是个重载的作用,使得重载机制得以运行，都不需要变量名。
void doAdvance(IterT& iter, DistT d, std::bidirectional_iterator_tag)
{
if (d >= 0) {while (d--) ++iter;}
else {while(d++) --iter;}
}
序列式容器
序列式容器：元素ordered, not sorted
关联式容器：
vector
与数组（array）十分类似，唯一差别就是array是静态空间，一旦配置了就不能改变，vector是动态空间，可以扩容。
评论区