前言

以STL的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在一切组件（更具体地说是指容器，container）的背后，默默工作，默默付出。但若以 STL 的实现角度而言，第一个需要介绍的就是空间配置器，因为整个STL 的操作对象（所有的数值）都存放在容器之内，而容器一定需要配置空间以置放资料。不先掌握空间配置器的原理，难免在阅读其它STL组件的实现时处处遇到挡路石。
———— 《STL源码剖析》侯捷

本篇博客将介绍 Allocator 的最后一部分：内存处理工具，之所以要介绍完 Iterator 之后再写这篇是因为理解这部分的实现需要 traits 的前置知识。

内存处理工具

STL 定义有五个全局函数，作用于未初始化空间上。这样的功能对于容器的实现很有帮助，看到它们肩负的重任。前两个函数是用于构造的construct() 和用于析构的 destroy()，另三个函数是 uninitialized_copy()，uninitialized_fill()，uninitialized_fill_n()，下面将依次介绍这些函数。

construct & destroy

这两个函数定义在 construct.h 中，负责对象的构造与析构

destroy() 这个函数，多次被我写成 destory() 导致 debug 了一晚上，希望大家不要因为这个出问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class Ty>
void construct(Ty* ptr) {
    // 将 ptr 强转为 void*，然后在 ptr 上调用默认构造函数
    ::new ((void*)ptr) Ty();  
}

template <class Ty1, class Ty2>
void construct(Ty1* ptr, const Ty2& value) {
    // 将 ptr 强转为 void*，然后在 ptr 上调用拷贝构造函数
    ::new ((void*)ptr) Ty1(value);  
}

// ... 的作用是将参数包展开，详见 note2.md
template <class Ty, class... Args>
void construct(Ty* ptr, Args&&... args) {
    // 带参数构造与移动构造均使用这个函数
    ::new ((void*) ptr) Ty(tinystl::forward<Args>(args)...);
}

construct() 比较容易理解，就是调用全局的 operator new 在传入的指针处构造 Ty 类型的对象，根据参数的不同使用该类型不同的构造函数。

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
35
36
// 平凡析构，不做任何处理
template <class Ty>
void destroy_one(Ty*, std::true_type) {}

// 非平凡析构，调用对象的析构函数
template <class Ty>
void destroy_one(Ty* pointer, std::false_type) {
    if (pointer != nullptr) {
        pointer->~Ty();
    }
}

// 平凡析构，不做任何处理
template <class ForwardIterator>
void destroy_cat(ForwardIterator, ForwardIterator, std::true_type) {}

// 非平凡析构，调用对象的析构函数
template <class ForwardIterator>
void destroy_cat(ForwardIterator first, ForwardIterator last, std::false_type) {
    for (; first != last; ++first) {
        destroy(&*first);
    }
}

template <class Ty>
void destroy(Ty* pointer) {
    // 判断是否是平凡析构
    destroy_one(pointer, std::is_trivially_destructible<Ty>{});
}

template <class ForwardIterator>
void destroy(ForwardIterator first, ForwardIterator last) {
    // 通过 iterator_traits 获取迭代器的类型，然后判断是否是平凡析构
    destroy_cat(first, last, std::is_trivially_destructible<
    typename iterator_traits<ForwardIterator>::value_type>{});
}

上述 destory() 的逻辑也很好理解，根据输入性别的特性来选择不同的析构方式，如果型别具有 “可平凡析构” 的特点，那么 destroy() 什么都不会做，否则会调用该类型的析构函数，对对象进行析构。

std::is_trivially_destructible

这里使用到了 std::is_trivially_destructible 而不是自定义的 type_traits 功能，之后的类似功能都会使用 std 中的方法。

std::is_trivially_destructible 是 C++ 标准库中的一个类型特性检测工具，用于判断一个类型是否具有平凡析构函数。平凡析构函数是指析构函数不会执行任何操作，对对象进行销毁，或释放资源。

一个类具有平凡析构的特点，需要满足以下的条件：

  1. 类型没有用户自定义的析构函数：用户自定义的析构函数可能会执行一些清理操作，从而使析构不再是平凡的。

  2. 类型没有虚析构函数：虚析构函数会导致类型具有虚函数表，从而不再是平凡析构。

  3. 类型的基类与非静态成员也具有平凡析构：如果类型的基类或某个非静态成员不具有平凡析构，那么整个类型也不具有平凡析构。

uninitialized_copy

由于剩下三个函数的逻辑都很类似，均是根据传入类型的型别特性采取两种不同的做法，这里仅分析 uninitialized_copy()

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
35
36
37
38
39
40
41
42
43
/*****************************************************************************************/
// uninitialized_copy
// 把 [first, last) 上的内容复制到以 result 为起始处的空间，返回复制结束的位置
/*****************************************************************************************/

/// @brief uninitialized_copy 的 trivial 版本
template <class InputIterator, class  ForwardIterator>
ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last, 
    ForwardIterator result, std::true_type) {
    return tinystl::copy(first, last, result);
}

/// @brief uninitialized_copy 的非 trivial 版本
template <class InputIterator, class ForwardIterator>
ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last, 
    ForwardIterator result, std::false_type) {
    auto cur = result;
    try {
        for (; first != last; ++first, ++cur) {
            // 移动构造
            tinystl::construct(&*cur, *first);
        }
    } 
    // commit or rollback，要么产生出所有的元素，要么一个都不产生
    // catch(...) 会捕获所有异常
    catch(...) {
        for (; result != cur; ++result) {
            // 析构
            tinystl::destroy(&*result);
        }
    }
    return cur;
}

/// @brief 把 [first, last) 上的内容复制到以 result 为起始处的空间，返回复制结束的位置
template <class InputIterator, class ForwardIteraotr>
ForwardIteraotr uninitialized_copy(InputIterator first, InputIterator last, 
    ForwardIteraotr result) {
    // 判断是否为 POD 类型，这里使用了 std::is_trivially_copy_assignable
    return tinystl::__uninitialized_copy(first, last, result, 
        std::is_trivially_copy_assignable<typename iterator_traits<InputIterator>::value_type>{});
    // MyTinySTL 中这里判断的是 ForwardIterator 的 value_type，感觉有点问题
}

POD 意指 Plain Old Data，也就是标量型别 (scalar types) 或传统的 C struct 型别。POD 型别必然拥有 trivial ctor/dtor/copy/assignment 函数，因此、我们可以对 POD 型别采用最有效率的初值填写手法，而对 non-POD 型别采取最保险安全的做法。

值得注意的是，SGI 针对 char* 和 wchar_t* 两种型别，特化了两个函数版本，采用最具效率的做法 memmove (直接移动内存内容) 来执行复制行为，这里并没有实现而是推给了上层的 copy() 函数（最终的效果应该相同，都是直接调用 memmove），为了内容的完整性，下面还是列出 SGI-STL 中的特化版本 uninitialized_copy()。

1
2
3
4
5
6
7
8
9
10
11
inline char* uninitialized_copy(const char* first, const char* last,
                                char* result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
                                   wchar_t* result) {
  memmove(result, first, sizeof(wchar_t) * (last - first));
  return result + (last - first);
}

总结

STL 的内存处理工具，如用于构造的construct() 和用于析构的 destroy()， uninitialized_copy()，uninitialized_fill()，uninitialized_fill_n() 等，均使用了 traits 技巧，针对类型特性 (type_traits) 的不同而选取最有效率的做法，更加印证了 traits 编程技法在 STL 中的重要性。