STL读书笔记

《STL标准库和泛型编程》by候捷，读书笔记。

主要记录分配器思想与一些模块编程技巧。

allocator总结

allocator的作用：空间配置器，为STL的各个容器的内存管理（开辟与回收）。比如 vetor<int, allocator<int>>vec.

CPP对象构建四个步骤：分配内存、构造对象、析构对象、回收内存。STL的allocator将这四个操作分开：allocate、construct、destroy、deallocate

destroy过程并不简单：

• 对于基本数据类型的析构，无需显式调用trivial destructor。

• 对于其他类型（分配了空间），需要在析构函数中释放。

STL的两级配置器设计

SGI STL设计了两级配置器，分别应对申请内存区域大于128B的情况和小于等于128B的情况。这种设计能够很好解决小型区块带来的内存碎片问题。

STL的一级配置器直接包装malloc和free，从堆中分配内存。

STL的二级配置器

如果申请的内存大小小于128byte时，就启动第二级分配器，从一个预先分配好的内存池中取一块内存交付给用户，这个内存池由16个不同大小（8的倍数，8~128byte）的空闲列表组成，allocator会根据申请内存的大小（将这个大小round up成8的倍数）从对应的空闲块列表取表头块给用户。

这种做法有两个优点：

1. 小对象的快速分配。小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。

2. 避免了内存碎片的生成。程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。

STL二级配置器的free list设计

链表结点用union结构而不直接用类去声明?
因为用类声明要额外的去维护指针,会带来额外的内存开销,而用union的话, 由于占用的内存区域是重合的,所以就不会带来这个问题.

// free list 节点：union 实现
// 同一块内存，空闲时当链表节点用，分配后当用户数据用
union FreeListNode {
    FreeListNode* next;   // 空闲时：指向下一个空闲块
    char        data[1];  // 分配后：用户数据的起始地址（柔性数组技巧）
};

// 用类声明的问题：
// class FreeListNode {
//     FreeListNode* next;  // 额外 8 字节指针开销
//     char data[8];        // 用户数据区
// };
// 总共 16 字节，next 指针在分配给用户后完全浪费

// 用 union 的好处：
// union 大小 = max(sizeof(next), sizeof(data))
// next 和 data 共享同一块内存，零额外开销

迭代器设计模式

迭代器类似指针，但它提供了比指针更智能的功能。从设计模式上，迭代器提供了顺序访问容器元素的能力。

那么容器的实现与元素访问就能分开，原生指针是做不到这点的。譬如一个list的结点，自增原生指针是得不到下一个node的地址的。

类型萃取

在STL的算法中运用迭代器时，很可能会用到迭代器所指向的类别（比如声明一个中间变量）。

C++中并没有typeof（）这样的函数，即便是RTTI中的type_id（）函数也只是获得类别名称（typeid经常用来比较两个指针所指类别是否相同）

STL的萃取器不仅要得到迭代器指向的对象类别，还要支持原生指针指向的对象类型。

实现思想：

• 迭代器作为模版类实现，在内部定义自己的value type。
• Traits萃取器作为模版类实现，模版参数类型为迭代器或者指针
  • 如果传入的是迭代器，那么返回迭代器的value type
  • 如果传入的是指针，那么模版类是可以为原生指针设计偏特化的版本的

下面是完整的类型萃取实现：

// 1. 迭代器作为模板类，内部定义 value_type
template <class T>
struct MyIterator {
    typedef T value_type;  // 内部类型定义
    T* ptr;

    MyIterator(T* p) : ptr(p) {}
    T& operator*() { return *ptr; }
};

// 2. 通用 Traits：从迭代器的 value_type 中萃取
template <class Iterator>
struct iterator_traits {
    typedef typename Iterator::value_type value_type;
};

// 3. 偏特化：原生指针 T* → 萃取出 T
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};

// 4. 使用示例
#include <iostream>
#include <typeinfo>

int main() {
    // 情况1：传入自定义迭代器
    using Iter = MyIterator<double>;
    iterator_traits<Iter>::value_type a = 3.14;  // a 是 double
    std::cout << typeid(a).name() << std::endl;

    // 情况2：传入原生指针
    int arr[] = {1, 2, 3};
    iterator_traits<int*>::value_type b = arr[0];  // b 是 int
    std::cout << typeid(b).name() << std::endl;

    // 情况3：const 指针也需要处理
    // 如果不加偏特化，const int* 会被当作通用版本处理，编译失败
    // 因为原生指针没有 ::value_type
    iterator_traits<const int*>::value_type c = 42;  // c 是 const int
    std::cout << typeid(c).name() << std::endl;

    return 0;
}