copy() 是一个调用频率非常高的函数,所以SGI STL的copy算法用尽各种办法,包括函数重载(function overloading)、型别特性(type traits)、偏特化(partial specialization) 编程技巧,无所不用其极地加强效率。下图是整个copy()操作的脉络。

img

copy算法将输入区间[first, last)内的元素复制到result指向的输出区间内,赋值操作是向前推进的。如果输入区间和输出区间重叠,复制顺序需要多加讨论。当result位于[first, last)之内时,也就是说,如果输出区间的首部与输入区间重叠,copy的结果可能不正确,建议选用copy_backward;如果输出区间的尾部如输入区间重叠,copy_backward的结果可能不正确,建议选用copy。当然,如果两区间完全不重叠,copy和copy_backward都可以选用。

copy算法根据输出迭代器的特性决定是否调用memmove()来执行任务,memmove()会先将整个输入区间的内容复制下来,然后再复制到输入区间。这种情况下,即使输入区间和输出区间有重叠时,copy的结果也是正确的。这也回答了上文中提调的,为什么result位于[first, last)之内时,copy的结果只是“可能不正确”。

copy为输出区间内的元素赋予新值,而不是产生新元素,它不能改变输出区间的长度。换句话说,copy不能用来直接将元素插入到空容器中。如果你想要将元素插入序列之中,要么使用序列容器的insert成员函数,要么使用copy算法并搭配insert_iterator。

下面是copy算法唯三的对外接口,包括一个完全泛化版本和两个重载函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class InputIterator, class OutputIterator> 
inline OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result) {
return __copy_dispatch<InputIterator, OutputIterator>()(first, last, result);
}
inline char* copy(const char* first, const char* last, char* result) {
memmove(result, first, last - first);
return result + (last - first);
}
inline wchar_t* copy(const wchar_t* first, const wchar_t* last, wchar_t* result) {
memmove(result, first, last - first);
return result + (last - first);
}

copy()函数的泛化版本中调用了一个_copy_dispatch()的仿函数(老方法了^^),此仿函数有一个完全泛化版本和两个偏特化版本:

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
template <class InputIterator, class OutputIterator>  
struct __copy_dispatch {
OutputIterator operator(){InputIterator first, InputIterator last,
OutputIterator result) {
return __copy(first, last, result, iterator_category(first);
} ;

/*
* __copy_dispatch()的完全泛化版本根据迭代器种类的不同,调用
* 不同的__copy(),为的是不同的迭代器使用的循环条件不同,有快
* 慢之别
*/

template <class InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last,
OutputIterator result, input_iterator_tag) {
for( ; first != last; ++first, ++result)
*result = *first;
return result;
}
template <class RandomAccessIterator, class OutputIterator>
inline OutputIterator __copy(RandomAccessIterator first, RandomAccessIterator last,
OutputIterator result, random_access_iterator_tag) {
__return __copy_d(first, last, result, distance_typ(first));
}
template <class RandomAccessIterator, class OutputIterator, class Distance>
inline OutputIterator __copy_d(RandomAccessIterator first, RandomAccessIterator last,
OutputIterator result, Distance*) {
// 以n决定循环次数,速度快
for(Distance n = last - first; n > 0; --n, ++result, ++first) {
*result = *first;
return result;
}

template <class T>
struct __copy_dispatch<T*, T*> {
T* operator()(T* first, T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
};
template <class T>
struct __copy_dispatch<const T*, T*> {
T* operator()(T* first, T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_asssignment_operator t;
return __copy_t(first, last, result, t());
};
/*
* 这两个偏特化版本是在“参数为原生指针形式”的前提下,利用
* __type_traits<>编程技巧来探测指针所指向之物是否有
* trivial assignment operator. 如果指针所指对象拥有
* trivial assignment operator,则可以通过memmove()进行复制,速度要比
* 利用赋值操作赋快许多
*/
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __true_type) {
memmove(result, first, sizeof(T) *(last - first);
return result + (last - first);
}
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __false_type) {
return __copy_d(first, last, result, (ptrdiff_t *)0);
}

以上就是copy()的故事,一个无所不用其极强化效率的故事。

copy_backward()的实现与copy()极为相似,不同是它将[first, last)区间内的每一个元素,以逆行的方向复制到,以result-1为起点,方向同样为逆行的区间上。