这是OOP课留下的作业，要求阅读别人的项目。

我选择的是SGI STL，项目地址：github.com/steveLauwh/SGI-STL

下边是我在阅读过程中的一些笔记（并不一定都是STL相关的，但肯定是C++相关）

template偏特化

template<typename T>
void func<T *> () {}

接受的是指针类型，使用func<int *>();才能正确调用

template中class和typename的区别

如果要用模版类型T的作用域中的东西T::，就必须在T前声明typename，来指明T是一种类型，比如

template<typename T>
class A {
    typename T::iterator it;
};

A<vector<int>> a;

traits classes

将一些模版类型（一般是迭代器类型或者指针）中的信息给封装好的类

比如

template <typename T>
struct get_value_type {
    typedef typename T::value_type the_value_type;
};

get_value_type<vector<int>::iterator>::the_value_type a; // int a

就可以获得STL中容器的迭代器所指类型（前提是迭代器类都定义了value_type这个类型）

由于迭代器也可以是指针，因此要特化一下

template <typename T>
struct get_value_type<T *> {
    typedef T the_value_type;
};

那么get_value_type<int *>::the_value_type同样也能得到int类型

STL的六大组件

• 容器（container）：一些数据结构。是类模板（class template）。
• 算法（algorithm）：一些算法。是函数模版（function template）。
• 迭代器（iterator）：是容器与算法之间的黏合剂；是所谓的泛型指针；是一种将指针相关操作（++、--等操作符）进行重载的类模板。每个STL容器都有自己的迭代器。C语言中的指针也是一种迭代器。
• 仿函数（functor）：是重载了()操作符的类或者类模板。
• 配接器（adapter）：继承于已有类型，隐藏一些接口、重新暴露一些接口来形成的一种新的类型。
• 配置器（allocator）：是管理内存的类模板。

STL源码中的文件

源码中每一个容器都有3个文件对应，比如vector模板类，那么有以下3个文件：

• vector：就是我们平常include的文件，#include <vector>；里面包含的是依赖头文件。
• vector.h：和vector差不多，不过考虑到了兼容有C语言习惯的人，直接将std中的vector给暴露出来。
• stl_vector.h：真正实现vector模板类的文件。

vector

由于我对vector内部的内存分配比较感兴趣，因此我选择查看vector的代码

concept_check.h文件

vector中include了concept_checks.h，看了下该文件，应该是定义了很多STL要用到的宏（各种用于检查的宏等）

traits技术

代码中大量用到了traits技术，这个技术的思想还是很niub的。

我们想通过仅仅一个value_type *来获取一些信息该怎么做呢？请看代码：

template <typename T>
struct the_trait <T *> {
    typedef T value_type;
    typedef T * pointer;
};

那么你就可以通过the_trait<int *>::value_type和the_trait<int *>::pointer得到相应的类型int和int *。

你说这大可不必？那么我们再看一个例子。

假如你有一个m_iterator泛型指针（即是一个类），那么你想要得到这个m_iterator的value_type怎么办呢？用m_iterator::value_type吗？那你怎么兼容T *的value_type（即T）？写两份代码？No，这不符合OOP。

你可以这样

template <typename T>
struct the_trait <T> {
    typedef typename T::value_type value_type;
    typedef typename T::pointer pointer;
};

template <typename T>
struct the_trait <T *> {
    typedef T value_type;
    typedef T * pointer;
};

// 那么你可以这样
typedef int * iterator_1;
typedef vector<int>::iterator iterator_2;

the_trait<iterator_1>::value_type a1; // int a1
the_trait<iterator_1>::pointer a2; // int * a2
the_trait<iterator_2>::value_type b1; // int b1
the_trait<iterator_2>::pointer b1; // vector<int>::iterator b2

// 如果放到模板里就可以这样
template <typename Iterator>
void func() {
    the_trait<Iterator>::value_type value;
    the_trait<Iterator>::pointer ptr;
}

只需要特化模版类the_trait就完美了！是不是十分帅气，十分OOP？！

这个技术在STL中大量使用。

iterator

在vector中，迭代器其实就是value_type *的别名，即C语言中的指针。

_Vector_alloc_base 类

定义了__STL_USE_STD_ALLOCATORS宏后才有的类（即表示使用STL提供的内存管理器）。

这是管理vector内存的模版基类，该类还有静态的模版特化类。

只提供两个方法_M_allocate和_M_deallocate，分别表示内存申请和释放。还提供了三个指针：

• _M_start：指向动态数组的开始位置
• _M_finish：指向动态数组的结束位置的后一位（但并不是所申请连续一段内存的结束位置的后一位）
• _M_end_of_storage：指向所申请连续一段内存的结束位置的后一位（往往_M_finish不等于_M_end_of_storage，因为要预留一些空间出来，而不至于频繁的申请内存）

_Vector_alloc_base析构的时候并不释放内存。

注意在STL里，范围一般都是左闭右开的。

_Vector_base 类

若定义了__STL_USE_STD_ALLOCATORS宏，则该类直接继承于_Vector_alloc_base类，并在析构时释放所申请的内存；

否则不继承任何类。并且使用使用者提供的allocator来管理内存。同时实现了_Vector_alloc_base类里的两个方法_M_allocate和_M_deallocate，并在析构时也释放所申请内存。

可以看做是真正意义上的vector的用于管理内存的基类。

vector 类

继承于_Vector_base类。

在这里我挑一些比较有代表性的东西出来：

• Q：为什么在vector的析构函数中有个destroy？在_Vector_base中的析构函数不是已经释放了内存吗？

destroy方法定义在stl_construct.h中，总结一下就是，调用迭代器所指对象的析构函数（若迭代器是基础数据类型的指针，则不做任何操作）。注意此方法并不会delete掉迭代器所指对象！而delete掉迭代器所指对象这个活，是由_Vector_base的析构函数中的deallocate来做的。具体来说是这样的：

class_A *a = new class_A();

a->~a(); // destroy所做的事
delete a; // _Vector_base析构函数中的deallocate所做的事

• Q：stl_construct.h中的_Construct函数的奇怪语句new ((void*) __p) _T1();是什么？

这是placement new，表示在指针__p所指地址上用默认构造函数重新构建对象。

• erase方法并不会释放内存

erase方法中用的是destory方法，并不会释放内存。若要释放vector内存只有析构它或者调用_M_deallocate方法手动释放（实际上是调用不了_M_deallocate的，没权限）。

• 真正核心的东西在_M_insert_aux方法里

若vector预留的空间满了怎么办？重新开辟一个2倍大小的空间（stl_vector.h的第645行const size_type __len = __old_size != 0 ? 2 * __old_size : 1;）！然后将之前的数据迁移过去。

很容易证明这样的插入操作时间复杂度是均摊$O(1)$的。

总结

• 模版类、方法
• 模版的特化、方法的重载
• 普通的is-a继承关系
• 大量宏
• traits技术

参考资料

STL——STL六大组件概念：https://blog.csdn.net/bian_cheng_ru_men/article/details/80735221

《STL源码剖析》总结：https://blog.csdn.net/bian_cheng_ru_men/article/details/80735221

细说 C++ Traits Classes：https://blog.csdn.net/lihao21/article/details/55043881

C++ new关键字深入理解：https://blog.csdn.net/bbs375/article/details/53202079