前言

本节将会分析 algobase.h 中的算法，algobase.h 中存放的都是一些比较基础的算法，如 max()、min()、copy() 等，这里就挑其中最具有代表性的 copy() 函数来分析，除了 copy() 外还有许多如 copy_backward()、move()、move_backward() 等函数，STL 对这些函数效率上的优化方式与 copy() 的处理基本是一致的，就不再分析。

copy

不论是对客端程序或对 STL 内部而言，copy() 都是一个常常被调用的函数。由于 copy 进行的是复制操作，而复制操作不外乎运用 assignment operator 或 copy constructor （copy算法用的是前者），但是某些元素型别拥有的是 trivialassignment operator，因此，如果能够使用内存直接复制行为（例如标准函数 memmove 或 memcpy），便能够节省大量时间。为此，SGI STL的copy 算法用尽各种办法，包括函数重载（function overloading）、型别特性（type traits）、偏特化（partial specialization）等编程技巧，无所不用其极地加强效率。下图展示了整个 copy() 操作的脉络。

7.png

从上面的流程可以大概梳理出 copy() 的调用脉络。

首先，copy 函数本身除了一个模板函数的泛化版本，还为 char* 以及 wchar_t* 提供了两个特化版本，针对这两种类型的 copy 直接调用 memmove()，其余类型元素的 copy 均转调用 __copy_dispatch；

__copy_dispath 有一个完全泛化版本以及两个针对原生指针 T* 和 const T* 的偏特化版本；

  • 完全泛化版本的 __copy_dispatch 根据输入的迭代器类型转调用 __copy，__copy 有处理 input_iterator 与 random_access_iterator 的两个重载，均会针对迭代器类型采取最有效率的措施。
  • 针对原生指针的 __copy_dispatch 会根据指针所指元素的 is_trivially_copy_assignable 特性来决定拷贝策略，若为平凡类型则直接调用 memmove()，否则转调用 __copy_d。

可以看到 STL 中的 copy 函数的实现确实复杂，通过函数重载、偏特化、型别特性等一系列手段对不同的类别采取不同的方法，但这也是为了效率的最优，it deserves。

上面这样说明还是有些抽象，下面列出 TinySTL 中实现的代码并且在每个函数中都加入了输入，配合测试案例一起理解会清晰许多。

MyTinySTL 中对于 algobase.h 中函数的具体实现与 STL 中还是有不小的差距，因此 copy 这部分还是遵循 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/// @brief 完全泛化版本 copy
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) {
    std::cout << "copy" << std::endl;
    return __copy_dispatch(first, last, result);
}

/// @brief 特殊版本（1），针对 char* 的特化
char* copy(const char* first, const char* last, char* result) {
    std::memmove(result, first, last - first);
    std::cout << "char* copy" << std::endl;
    return result + (last - first);
}

/// @brief 特殊版本（2），针对 wchar_t* 的特化
wchar_t* copy(const wchar_t* first, const wchar_t* last, wchar_t* result) {
    std::memmove(result, first, sizeof(wchar_t) * (last - first));
    std::cout << "wchar_t* copy" << std::endl;
    return result + (last - first);
}

/// @brief copy_dispatch 的完全泛化版本
template <class InputIterator, class OutputIterator>
OutputIterator __copy_dispatch(InputIterator first, InputIterator last, OutputIterator result) {
    std::cout << "InputIterator __copy_dispatch" << std::endl;
    return __copy(first, last, result, iterator_category(first));
};

/// @brief copy_dispatch 的偏特化版本（1），针对 T*
template <class T>
T* __copy_dispatch(T* first, T* last, T* result) {
    using trivial = typename std::is_trivially_copy_assignable<T>::type;
    std::cout << "T* __copy_dispatch" << std::endl;
    return __copy_t(first, last, result, trivial());
};

/// @brief copy_dispatch 的偏特化版本（2），针对 const T*
template <class T>
T* __copy_dispatch(const T* first, const T* last, T* result) {
    using trivial = typename std::is_trivially_copy_assignable<T>::type;
    std::cout << "const T* __copy_dispatch" << std::endl;
    return __copy_t(first, last, result, trivial());
};

/// @brief __copy 的 InputIterator 的版本，以迭代器是否相等作为循环结束的条件，效率较低
template <class InputIterator, class OutputIterator>
OutputIterator __copy(InputIterator first, InputIterator last, 
    OutputIterator result, tinystl::input_iterator_tag) {
    for (; first != last; ++first, ++result) {
        *result = *first;
    }
    std::cout << "input_iterator_tag __copy" << std::endl;
    return result;
}

/// @brief __copy 的 RandomAccessIterator 的版本，以 n 作为循环结束的条件，效率较高
template <class RandomAccessIterator, class OutputIterator>
OutputIterator __copy(RandomAccessIterator first, RandomAccessIterator last, 
    OutputIterator result, tinystl::random_access_iterator_tag) {
    // 又划分出一个函数，为的是其他地方也可以用到
    std::cout << "random_access_iterator_tag __copy" << std::endl;
    return __copy_d(first, last, result, distance_type(first));
}

/// @brief 针对原生 non_trivally_copy_assignable 指针 和 RandomAccessIterator 的版本
template <class RandomAccessIterator, class OutputIterator, class Distance>
OutputIterator __copy_d(RandomAccessIterator first, RandomAccessIterator last, 
    OutputIterator result, Distance*) {
    for (Distance n = last - first; n > 0; --n, ++first, ++result) {
        *result = *first;
    }
    std::cout << "__copy_d" << std::endl;
    return result;
}

/// @brief __copy_t 针对 trivally_copy_assignable 类型的版本
template <class T>
T* __copy_t(const T* first, const T* last, T* result, std::true_type) {
    std::memmove(result, first, sizeof(T) * (last - first));
    std::cout << "T* trivally_copy_assignable __copy_t" << std::endl;
    return result + (last - first);
}

/// @brief __copy_t 针对 non_trivally_copy_assignable 类型的版本
template <class T>
T* __copy_t(const T* first, const T* last, T* result, std::false_type) {
    std::cout << "T* non_trivally_copy_assignable __copy_t" << std::endl;
    return __copy_d(first, last, result, static_cast<ptrdiff_t*>(nullptr));
}

测试案例

下面的案例中，代码底部的注释即为运行的输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
tinystl::vector<int> v1{1, 2, 3, 4, 5};
tinystl::vector<int> v2(5);
tinystl::copy(v1.begin(), v1.end(), v2.begin());
for (auto i : v2) {
    cout << i << " ";
}
cout << endl;

// copy
// const T* __copy_dispatch
// T* trivally_copy_assignable __copy_t
// copy
// T* __copy_dispatch
// T* trivally_copy_assignable __copy_t
// 1 2 3 4 5

上面的输出还是很耐人寻味的。

首先，为什么明明是 vector<int> 调用的却是 T* 的 copy 方法？答案其实比较明显了，在 vector 容器中说过，vector 的迭代器就是普通的指针，因此这里确实会调用 __copy_t 方法进行拷贝，合理。

其次，为什么调用了两次 copy？这其实是 vector 的初始化列表构造的原因，vector 的初始化列表构造会调用 uninitialized_copy()，从而间接调用 copy()，但这只是在 trivally_copy_assignable 类型的情况下。

当我们不使用初始化列表构造时，就只会输出一次 copy 的信息了。

1
2
3
4
5
6
7
8
9
10
11
12
tinystl::vector<int> v1(5);
tinystl::vector<int> v2(5);
tinystl::copy(v1.begin(), v1.end(), v2.begin());
for (auto i : v2) {
    cout << i << " ";
}
cout << endl;

// copy
// T* __copy_dispatch
// T* trivally_copy_assignable __copy_t
// 0 0 0 0 0

我们再定义一个 non-trivial 的类型 A 并进行测试，发现 copy 也会调用相应的版本。

这里有一点比较奇怪，虽然说 SGI-STL 中对于所有的用户自定义类型都采用了最保守的 type traits，但不同版本的 STL 貌似策略并不相同，而且在 TinySTL 中使用的是诸如 std::is_trivially_copy_assignable<T> 来判断 type traits，所以运行结果会与预期的有所差别。

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
class A {

public:
    A() : a("A") {}
    A(const A& other) : a(other.a) {}
    friend ostream& operator<<(ostream& os, const A& a) {
        os << a.a;
        return os;
    }

private:
    string a;
};

tinystl::vector<A> v1(5);
tinystl::vector<A> v2(5);
tinystl::copy(v1.begin(), v1.end(), v2.begin());
for (auto i : v2) {
    cout << i << " ";
}
cout << endl;

// copy
// T* __copy_dispatch
// T* non_trivally_copy_assignable __copy_t
// __copy_d
// A A A A A

换一个不是迭代器不为原生指针的容器类型，如 deque，再进行测试，可以发现 copy 也会转调用 random_access_iterator 版本的 __copy_dispatch 重载。

1
2
3
4
5
6
7
8
9
10
11
12
13
tinystl::deque<int> d1(5);
tinystl::deque<int> d2(5);
tinystl::copy(d1.begin(), d1.end(), d2.begin());
for (auto i : d2) {
    cout << i << " ";
}
cout << endl;

// copy
// InputIterator __copy_dispatch
// random_access_iterator_tag __copy
// __copy_d
// 0 0 0 0 0

最后是 char* 类型，copy 直接在最外层针对该类型做了特化，不会进一步向下调用。

1
2
3
4
5
6
7
const char s1[] = "hello";
char s2[10];
tinystl::copy(s1, s1 + 5, s2);
cout << s2 << endl;

// char* copy
// hello

总结

这一节简单分析了 algobase.h 中最具有代表性的一个函数：copy，该函数通过各种精妙的设计来实现运行时的效率最优，很好地体现了 STL 中函数的设计思想，algobase.h 中还有许多类似的函数，这里就不一一分析了，下一节将会进入最为庞大的 algo.h 部分的分析。