STL源码之copy算法深入学习

copy算法可将输入区间[first, last)内的元素复制到输出区间[result, result+(last-first))内。也就是说，它会执行赋值操作*result = *first, *(result+1) = *(first+1), …依次类推。返回一个迭代器：result+(last-first))。

SGI STL的copy算法，内部实现机制：

1. copy算法，需要特别注意区间重叠的情况：
   
   （1）copy算法(可能)会在输入区间的(某些)元素尚未被复制之前，就覆盖其值，导致错误。
   （2）如果copy算法根据其所接收的迭代器的特性决定调用memmove()来执行任务，就不会造成上述错误，因为memmove()会先将整个输入区间的内容复制下来，没有被覆盖的危险。下面看一个实例：
   
   C++

   #include <iostream> #include <algorithm> #include <deque> //deque拥有RandomAccessIterator using namespace std; template <class T> struct { void opreator()(const T& x) { cout << x << ' '; } }; int main() { { int ia[] = {0,1,2,3,4,5,6,7,8}; //以下，输出区间的终点与输入区间重叠，没问题 copy(ia+2, ia+7, ia); for_each(ia, ia+9, display<int>()); //2 3 4 5 6 7 8 cout << endl; } { int ia[] = {0,1,2,3,4,5,6,7,8}; //以下，输出区间的起点与输入区间重叠，可能会有问题 copy(ia+2, ia+7, ia+4); for_each(ia, ia+9, display<int>()); //0 1 2 3 2 3 4 5 6 cout << endl; //本例结果正确， 因为调用的copy算法使用memmove()执行实际复制操作 } { int ia[] = {0,1,2,3,4,5,6,7,8}; deque<int> id(ia, ia+9); deque<int>::iterator first = id.begin(); deque<int>::iterator last = id.end(); ++++first; //advance(first, 2); cout << *first << endl; //2 ----last; //advance(first, -2); cout << *last << endl; //7 deque<int>::iterator result = id.begin(); cout << *result << endl; //0 //以下，输出区间的终点与输入区间重叠，没问题 copy(first, last, result); for_each(id.begin(),id.end(), display<int>()); //2 3 4 5 6 5 6 7 8 cout << endl; } { int ia[] = {0,1,2,3,4,5,6,7,8}; deque<int> id(ia, ia+9); deque<int>::iterator first = id.begin(); deque<int>::iterator last = id.end(); ++first; //advance(first, 2); cout << *first << endl; //2 --last; //advance(first, -2); cout << *last << endl; //7 deque<int>::iterator result = id.begin(); advance(result, 4); cout << *result << endl; //4 //以下，输出区间的起点与输入区间重叠，可能会有问题 copy(first, last, result); for_each(id.begin(), id.end(), display<int>()); //0 1 2 3 2 3 2 3 2 cout << endl; //本例结果错误，因为调用的copy算法不再使用memmove()执行实际复制操作 } }

   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

   #include <iostream> #include <algorithm> #include <deque> //deque拥有RandomAccessIterator using namespace std;   template <class T> struct { void opreator()(const T& x) { cout << x << ' '; } };   int main() { { int ia[] = {0,1,2,3,4,5,6,7,8}; //以下，输出区间的终点与输入区间重叠，没问题 copy(ia+2, ia+7, ia); for_each(ia, ia+9, display<int>()); //2 3 4 5 6 7 8 cout << endl; } { int ia[] = {0,1,2,3,4,5,6,7,8}; //以下，输出区间的起点与输入区间重叠，可能会有问题 copy(ia+2, ia+7, ia+4); for_each(ia, ia+9, display<int>()); //0 1 2 3 2 3 4 5 6 cout << endl; //本例结果正确， 因为调用的copy算法使用memmove()执行实际复制操作 } { int ia[] = {0,1,2,3,4,5,6,7,8}; deque<int> id(ia, ia+9); deque<int>::iterator first = id.begin(); deque<int>::iterator last = id.end(); ++++first; //advance(first, 2); cout << *first << endl; //2 ----last; //advance(first, -2); cout << *last << endl; //7 deque<int>::iterator result = id.begin(); cout << *result << endl; //0 //以下，输出区间的终点与输入区间重叠，没问题 copy(first, last, result); for_each(id.begin(),id.end(), display<int>()); //2 3 4 5 6 5 6 7 8 cout << endl; } { int ia[] = {0,1,2,3,4,5,6,7,8}; deque<int> id(ia, ia+9); deque<int>::iterator first = id.begin(); deque<int>::iterator last = id.end(); ++first; //advance(first, 2); cout << *first << endl; //2 --last; //advance(first, -2); cout << *last << endl; //7 deque<int>::iterator result = id.begin(); advance(result, 4); cout << *result << endl; //4 //以下，输出区间的起点与输入区间重叠，可能会有问题 copy(first, last, result); for_each(id.begin(), id.end(), display<int>()); //0 1 2 3 2 3 2 3 2 cout << endl; //本例结果错误，因为调用的copy算法不再使用memmove()执行实际复制操作 } }

   
   注意：如果以vector取代上述的deque进行测试，复制结果将是正确的，因为vector迭代器其实是个原生指针(native pointer)，导致调用的copy算法以memmove执行实际复制操作。

   （3）copy更改的是[result, result+(last-first))中的迭代器所指对象，而非迭代器本身。它会为输出区间的元素赋予新值，而不是产生新的元素。它不能改变输出区间的迭代器个数。换句话说，copy不能直接用来将元素插入空容器中。

2. copy算法部分实现细节
   （1）完全泛化版本
   
   C++

   //完全泛化版本 template <class InputIterator, class OutputIterator> inline OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) { return __copy_dispatch<InputIterator, OutputIterator>()(first, last, result); }

   1 2 3 4 5 6

   //完全泛化版本 template <class InputIterator, class OutputIterator> inline OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) { return __copy_dispatch<InputIterator, OutputIterator>()(first, last, result); }

   
   （2）下面两个是多载函数，针对原生指针(可视为一种特殊的迭代器)const char*和const wchar_t*，进行内存直接拷贝操作：
   
   C++

   //特殊版本(1),重载形式 inline char* copy(const char* first, const char* last, char* result) { memmove(result, first, last-first); return result + (last - first); } //特殊版本(2),重载形式 inline wchar_t* copy(const wchar_t* first, const wchar_t* last, wchar_t* result) { memmove(result, first, sizeof(wchar_t) * (last - first)); return result + (last - first); }

   1 2 3 4 5 6 7 8 9 10 11

   //特殊版本(1),重载形式 inline char* copy(const char* first, const char* last, char* result) { memmove(result, first, last-first); return result + (last - first); }   //特殊版本(2),重载形式 inline wchar_t* copy(const wchar_t* first, const wchar_t* last, wchar_t* result) { memmove(result, first, sizeof(wchar_t) * (last - first)); return result + (last - first); }

   
   （3）copy函数的泛化版本中调用了一个__copy_dispatch()函数，此函数有一个完全泛化版本和两个偏特化版本：
   
   C++

   //完全泛化版本 template <class InputIterator, class OutputIterator> struct __copy_dispatch { OutputIterator operator()(InputIterator first, InputIterator last, OutputIterator result){ return __copy(first, last, result, iterator_category(first)); } }; //偏特化版本(1),两个参数都是T*指针形式 template <class T> struct __copy_dispatch<T*, T*> { T* operator()(T* first, T* last, T* result){ typedef typename __type_tiraits<T>::has_trivial_assignment_operator t; return __copy_t(first, last, result, t()); } }; //偏特化版本(2),第一个参数为const T*指针形式，第二参数为T*指针形式 template <class T> struct __copy_dispatch<const T*, T*> { T* operator()(const T* first, const T* last, T* result) { typedef typename __type_traits<t>::has_trivial_assignment_operator t; return __copy_t(first, last, result, t()); } };

   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

   //完全泛化版本 template <class InputIterator, class OutputIterator> struct __copy_dispatch { OutputIterator operator()(InputIterator first, InputIterator last, OutputIterator result){ return __copy(first, last, result, iterator_category(first)); } };   //偏特化版本(1),两个参数都是T*指针形式 template <class T> struct __copy_dispatch<T*, T*> { T* operator()(T* first, T* last, T* result){ typedef typename __type_tiraits<T>::has_trivial_assignment_operator t; return __copy_t(first, last, result, t()); } };   //偏特化版本(2),第一个参数为const T*指针形式，第二参数为T*指针形式 template <class T> struct __copy_dispatch<const T*, T*> { T* operator()(const T* first, const T* last, T* result) { typedef typename __type_traits<t>::has_trivial_assignment_operator t; return __copy_t(first, last, result, t()); } };

   
   （4）__copy_dispatch的完全泛化版根据迭代器种类的不同，调用了不同的__copy()，为的是不同种类的迭代器所使用的循环条件不同，有快慢之分。
   
   C++

   //InputIterator版本 template <class InputIterator, class OutputIterator> inline OutputIterator __copy(InputIterator first, InputIterator last, OutputIterator result, input_iterator_tag) { //以迭代器等同与否，决定循环是否继续。速度慢 for( ; first != last;++result, ++first) *result = *first; //assignment operator return result; } //RandomAccessIterator版本 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_type(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; }

   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

   //InputIterator版本 template <class InputIterator, class OutputIterator> inline OutputIterator __copy(InputIterator first, InputIterator last, OutputIterator result, input_iterator_tag) { //以迭代器等同与否，决定循环是否继续。速度慢 for( ; first != last;++result, ++first) *result = *first; //assignment operator return result; }   //RandomAccessIterator版本 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_type(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; }

   
   （5）SGI STL采用所谓的__type_traits<>编程技巧来侦测某个对象的类型是否具有trivial assignment opeator：
   
   C++

   //以下版本适用于“指针所指对象具备trivial assignment operator” 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); } //以下版本适用于“指针所指对象具备non-trivial assignment operator" template <class T> inline T* __copy_t(const T* first, T* last, T* result, __falsr_type) { //原生指针毕竟是一种RandonAccessIterator，所以交给__copy_d()完成 return __copy_d(first, last, result, (ptrdiff_t*)0); }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   //以下版本适用于“指针所指对象具备trivial assignment operator” 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); }   //以下版本适用于“指针所指对象具备non-trivial assignment operator" template <class T> inline T* __copy_t(const T* first, T* last, T* result, __falsr_type) { //原生指针毕竟是一种RandonAccessIterator，所以交给__copy_d()完成 return __copy_d(first, last, result, (ptrdiff_t*)0); }

   
   参考：STL源码剖析