[toc]

前提：所说的都是《STL 源码剖析》这本书内的 CPP 源码的逻辑，书中使用的是 SGI C++，其他版本的基本上无法参考，但是大体思路应该可以借鉴

# 大体结构

六大组件的关系:
Container 通过 Allocator 取得数据储存空间， Algorithm 通过 Iteator 存取 Container 内容， Functor 可以协助 Algorithm 完成不同的策略变化， Adapter 可以修饰或套接 Functor

前闭后开区间

STL 的迭代器是前闭后开的，即 first () 只想第一个元素，而 end 指向的则是 最后一个元素的后一位 另外，由于迭代器本身是通过 Adaptor 实现的，所以其物理顺序并不需要连续

# 仿函数 (function call)

通常，在 C++ 中如果我们需要 将函数作为参数传递唯一的方法就是传递函数指针
但是这种方法存在着缺陷，即所传递的函数是 无状态的
而 STL 中提供了一种 用起来像是函数的东西 来代替函数指针，即 仿函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
using namespace std;

//重载operator(),plus变成了一个仿函数
template <class T>
struct M_plus {
    T operator()(const T& x, const T& y) const { return x + y; }
};

template<class T>
struct M_minus {
    T operator()(const T& x, const T& y) const { return x - y; }
};

int main() {
    M_plus<int> plusobj;
    M_minus<int> minusobj;

    //以下使用仿函数,就类似于一般函数一样
    cout << plusobj(3, 5) << endl;
    cout << minusobj(3, 5) << endl;

    //临时对象仿函数
    cout << M_plus<int>()(43, 50) << endl;
    cout << M_minus<int>()(43, 50) << endl;

    return 0;
}

但是这种实现还缺乏 "可配接 (Adaptor)" 的能力

# 空间分配器 (allocator)

allocator 是用来给容器分配空间 (内存) 的适配器，如果需要构建一个新的 allocator, 则需要声明类似于下面代码中的变量和函数 (根据 C++ 版本和编译器不同需要做出对应的改变):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

template<class T>
class allocator {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    //rebind allocator of type U
    template<class U>
    struct rebind {
        typedef allocator<U> other;
    };

    pointer allocate(size_type n, const void* hint = 0) {
        return _allocate((difference_type)n, (pointer)0);
    }
    void deallocate(pointer p, size_type n) { _deallocate(p); }
    void construct(pointer p, const T& value)
    {
        _construct(p, value);
    }
    void destroy(pointer p) { _destroy(p); }
    pointer address(reference x) { return (pointer)&x; }
    const_pointer const_address(const_reference x) {
        return (const_pointer)&x;
    }
    size_type max_size() const {
        return size_type(UINT_MAX / sizeof(T));
    }
};

使用时直接传递给容器的 allocator 模板即可

如图，容器的某个模板类型上存在一个 allocator, 需要把自己构建好的 allocator 传递给这个默认模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include "jjaloc.h"
#include <vector>
#include <iostream>
using namespace std;


int main() {
    int ia[5] = { 0,1,2,3,4 };
    unsigned int i;

    vector<int, JJ::allocator<int>> iv(ia, ia + 5);
    for (i = 0; i < iv.size(); ++i) {
        cout << iv[i] << " ";
    }
    cout << endl;

    return 0;
}

实际上，目前的 allocator 只是 new 和 delete 的一层包装，再向下一层，我们知道，通常手动分配内存走的是 malloc 接口，而上述的 allocator 只是对 new/delete 的一层封装，那么再向下一层就是对于 new/delete 的封装了 再向下一层的封装是在 stl_alloc.h 文件中 (这个根据不同的 CPP 版本和实现方式存在不同的地方吧)。其大体的结构图如下：
如上图所示，vector 容器的第二个参数传递的是一个 alloc，一个平凡的 alloc 需要实现下面四个函数
上面有说 alloc 的引用对象中有一个是 __malloc_alloc_template (被称为 第一级内存配置 )，这个类的 allocate 实现如下:

# 一级内存配置器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

static void * allocate(size_t n)
{
    void *result = malloc(n);
    if (0 == result) result = oom_malloc(n);
    return result;
}

template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    for (;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
        (*my_malloc_handler)();
        result = malloc(n);
        if (result) return(result);
    }
}

可以看出，在 oom_alloc 的实现中调用了最底层的 malloc 方法。可以发现第一级内存配置始终调用 malloc 来进行内存分配，并没有做任何优化。

# 二级内存配置器

__default_alloc_template ，第二级内存配置器是为了防止小区块内存分配造成的碎片和分配内存造成的性能负担而诞生的。

1. 分配内存大于 128bytes 时，交给第一级配置器处理。
2. 小于 128bytes 时，交给内存池管理 (又称次级配置)。

这里有一个比较迷的分配:
其中次级分配是放在池子中的: 池子中的每个节点的结构体如下:

1
2
3
4

union obj {
      union obj * free_list_link;
      char client_data[1];    /* The client sees this.        */
};

这里需要结合上图来看，当内存区块还 在池中 时，会使用 free_list_link 作为指向下一个空闲区块的指针。
而在使用时，这个指针会变更为client_data，即相比指针仅占用1字节，但将其他所有的内存交给用户使用，节省内存空间 ，只有在池子中时才会占用指针的空间

二级内存分配

1. 判断是否大于 128kb，是的话调用一级分配器
2. 寻找 16 个 free_list 是否存在满足条件的 list，存在的话分配，否则重新填充 refill
3. 调整 free_list

二级内存释放

1. 是否大于 128kb，是的话用一级释放
2. 寻找 free_list
3. 将内存回收至 free_list

内存池

二级分配器申请内存时，如果发现 free_list 中不存在了，会先向内存池进行申请，如果不足，则向堆中申请新内存

# 迭代器 (iterators)

# 迭代器相应型别 (associated types)

一个简单的型别范式:
即通过 fucntion template 参数推导机制将实际的比较放到 func_impl 中，实际的入口则可以都放在 func 中

# Traits 编程技法

上述参数型别在不需要确定返回值类型时是比较方便的，但如果需要确定返回值类型，就不方便了。

内嵌型别声明

通俗来讲，内嵌型别声明就是在类中将需要的类型声明出来
如:

1
2
3
4
5
6
7
8
9
10
11

template<class T>
struct MyIter{
    typedef T value_type;//内嵌型别声明
}

//使用时  
template<class I>
typename I::value_type //这一整行是func的返回值类型(必须加入typename)
func(I ite){
    return *ite;
}

但是如果迭代器是 指针 而不是 class type ，就无法做到了，这时候就需要用到偏特化

# 偏特化 (Partial Specialization)

偏特化就是如果 class template 有一个以及以上的 template 参数时，我们可以针对其中某个或多个 template 参数进行特化 偏特化的一个例子:

1
2
3
4
5
6
7
8

//泛化
template<typename T>
class C{...}

//偏特化
//更进一步限制T为T的原生指针
template<typename T>
class C<T*> {...}

# 使用偏特化改进迭代器入口模板

使用特化来萃取参数类型

1
2
3
4

template <class I>
struct iterator_traits{//traits 意为 "特性"
    typedef typename I::value_type value;
}

即：如果对象内定义了 value_type, 则 iterator_traits 的 value_type 就是 I::value_type 模板的返回值就可以改写成这样:

1
2
3
4

template <class I>
typename iterator_traits<I>::value_type //返回类型
func(I ite)
{return *ite;}

如果我们需要返回指针，只需要多加一个偏特化的模板即可:

1
2
3
4
5

template <class T>
struct iterator_traits<T*> //使用偏特化实现指针的迭代器,返回的类型是指针的原始类型
{
    typedef T value_type;
}

如果想要干掉 const

1
2
3
4
5

template<class T>
struct iterator_traits<const T>
{
    typedef T value_type;
}

至此，不停类型的迭代器就可以单独声明了，需要特化就加一个偏特化的模板即可

# iterator_category

这个主题主要是和 STL 的 Algorithm 层有关的，由于算法层在执行不同的操作时需要对容器进行不同类型迭代的遍历，以及 不同的容器也可能需要不同种类的迭代器遍历方法 ，所以出现了这玩意，sgi 版本的 stl 主要有五个 category
简单的使用方法: 上层算法的入口:

# 更泛化的 traits: __type_traits

上面介绍了 traits 的语法，但其实 sgi stl 提供了 更泛化的traits ：__type_traits iterator_traits 主要用来萃取迭代器特性，而__type_traits 则主要用来萃取 类型特性 比如我们希望程序可以获得某一个类的某些特性:
那么就可以对不同的类型进行泛化声明:

1. 公共

2. 泛化例子
   

使用时，直接定义一个泛型类型，判断一下它内部定义的 type_traits 即可

# 序列式容器

# vector

array 是静态空间，vector 是动态空间
vector 的空间分配示意图: 从这点来看，和 C# 等语言的扩容方法近似
当没有备用空间，触发扩容时:
1. 扩容
2. 重新配置
3. 移动数据到新空间
4. 释放原空间 注意的点：时分配的新空间，而非旧空间

# list

简单来说，双向链表，没有扩容的操作，但同时效率和随机访问就很弱

# deque

双向开口的线性空间，可以在头部 / 尾部 添加 / 删除 vector 由于单向线性表，所以头部插入的效率极差，deque 并不是 deque 的实现方式是: 在头部和尾部由一段一段连续的空间组合而成，而不是整个容器都像vector一样是个连续空间 在实际使用时，是双向队列的使用方式

push_front

# stack 和 queue

这俩容器都是用 list 作为底层容器实现的，所以并不是顺序的

# heap 和 priority_queue

前者是大根 / 小根堆，后者是基于 heap 实现的优先队列 (元素是有顺序的) 具体算法不赘述

# slist

单向链表

# 关联式容器

map/set/multimap/hashtable 前三者底层是用 RB-Tree 实现的，后者是哈希桶 hash_set/hash_map/hash_multiset/hash_multimap 以 hashtable 为底层实现

# hash_functions

对于不同类型的哈希算法，用上述的 traits 范式对不同类型进行模板特化即可

# 算法

即 stl 中的 nth_element / sort / power 等这种函数
algorithm 中的 但其实算法也参与了泛化 (偏特化) 的过程，这个过程主要借助于迭代器的泛化和 category / 仿函数等实现

# 仿函数 (函数对象 function objects)

及类似于 C# 等语言中的回调函数 (Action/Delegate) 由于 C++ 中虽然可以将函数指针作为参数传递，但不够抽象。
使用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<iostream>
#include<functional>
using namespace std;

int main() {
    //一下产生一些仿函数实体
    plus<int> plusobj;  //加法
    minus<int> minusobj;//减法
    divides<int> dividesobj;//乘法
    multiplies<int> multipliesobj;//除法
    modulus<int> modulusobj;//模取(余数)
    negate<int> negateobj;//否定(取反)


    cout << plusobj(3, 5) << endl;
    cout << minusobj(3, 5) << endl;
    cout << dividesobj(3, 5) << endl;
    cout << multipliesobj(3, 5) << endl;
    cout << modulusobj(3, 5) << endl;
    cout << negateobj(3) << endl;

    return 0;
}

还有其他类似于关系运算符等一系列仿函数 事实上，使用 sort 时可以将 greater 传入，将小于转换为大于，这也是仿函数的一种用法