引言

copy()的函数原型如下：

template<class InputIterator, class OutputIterator> inline OutputIterator copy( InputIterator first, InputIterator last, OutputIterator result ); 参数: first, last 指出被复制的元素的区间范围[first，last) result 指出复制到的目标区间起始位置 返回值： 返回一个迭代器，指出已被复制元素区间的最后一个位置

其作用是将输入区间 [ first，last ) 内的元素复制到输出区间 [ result，result +( last - first ) )，即*（result + n）=*（first + n），赋值操作是向前推进的。

这个函数有非常多的特化与强化版本，用尽函数重载、型别特性、偏特化等编程技巧，会根据其所接收的迭代器特性调用合适的版本，可谓“强化效率无所不用其极”。

算法总览

算法实现细节

copy执行的是复制操作，而复制操作不外乎运用拷贝构造函数或赋值运算符（copy算法用的是后者），但是某些元素型别拥有的是trivial赋值运算符，因此，如果能使用内存直接复制行为，便能够节省大量时间。

1）copy()函数的特化版本 针对原生指针（可视为一种特殊的迭代器）const char*和const wchar_t*，进行内存直接拷贝操作：

// 特殊版本1，针对原生指针const char* inline char* copy(const char* first, const char* last, char* result) { memmove(result, first, last - first); return result + (last - first); } // 特殊版本2，针对原生指针const wchar_t* 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); } // memmove函数原型 // 作用是复制 src 所指的内存内容前 num 个字节到 dest 所指的地址上 // 它和memcpy的作用是一样的，唯一的区别是，当内存发生局部重叠的时候，memmove保证拷贝的结果是正确的，memcpy不保证拷贝的结果的正确，但memcpy比memmove的速度要快一些 void *memmove(void *dest, const void *src, size_t num);

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

// 完全泛化版本 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_traits<T>::has_trivial_assignment_operator t; return __copy(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(first, last, result, t()); } };

首先来看__copy_dispatch()的完全泛化版本，它会根据迭代器的种类不同，调用不同的__copy()，如下：

// 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; 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)); } // __copy_d()在其它地方也会用到 template <class RandomAccessIterator, class OutputIterator> inline OutputIterator __copy_d(RandomAccessIterator first, RandomAccessIterator last, OutputIterator result, Distance*) { // 以n决定循环的次数，速度快 for(Distance n = last - first; n > 0; --n, ++result, ++forst) { *result = *first; } return result; }

再来看__copy_dispatch()的两个偏特化版本。这两个偏特化版本是在“参数为原生指针形式”的前提下，希望进一步探测“指针所指之物”是否具有平凡赋值操作符。因为复制操作是由赋值操作符来完成的，如果指针所指对象拥有非平凡赋值操作符，复制操作就一定要靠它来执行；但如果对象拥有的是平凡赋值操作符，就可以直接以最快的内存拷贝方式来执行。

// 指针所指的对象具有平凡赋值操作符 template<class T> inline T* __copy_t(const T* first, const T* last, T* result, __true_type) { memmove(result, first, szeof(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()时，如果输入区间和输出区间完全没有重叠，当然毫无问题，否则需特别注意。copy算法是一一进行元素的赋值操作，如果输出区间的起点位于输入区间内，copy算法便（可能）会在输入区间的（某些）元素尚未被复制之前，就覆盖其值，导致错误结果。如果copy算法根据其所接收的迭代器的特性决定调用memmove()来执行任务，就不会造成上述错误，因为memmove()会先将整个区间的内容复制下来，没有被覆盖的危险。

例： #include <iostream> #include <vector> #include <deque> #include <iterator> #include <algorithm> using namespace std; int main() { int i; int ia[] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; // 原生指针 copy(ia + 2, ia + 7, ia + 4); for(i = 0; i < 9; i++) { cout << ia[i] << ' '; } cout << endl; int ib[] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; vector<int> ivec(ib, ib + 9); vector<int>::iterator first = ivec.begin(); vector<int>::iterator last = ivec.end(); ++++first; ----last; vector<int>::iterator result = ivec.begin(); ++++++++result; // vector的迭代器是原生指针 copy(first, last, result); for(i = 0; i < 9; i++) { cout << ivec[i] << ' '; } cout << endl; int ic[] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; deque<int> id(ib, ib + 9); deque<int>::iterator firstD = id.begin(); deque<int>::iterator lastD = id.end(); ++++firstD; ----lastD; deque<int>::iterator resultD = id.begin(); ++++++++resultD; // deque的迭代器被归类于random access iterator copy(firstD, lastD, resultD); for(deque<int>::iterator it = id.begin(); it != id.end(); it++) { cout << *it << ' '; } cout << endl; return 0; }

运行结果：

---

参考资料：《STL源码剖析》侯捷 著