copy

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

        copy算法可将输入区间[first,last)内的元素复制到输出区间[result, result+(last-first))内，也就是说，它会执行赋值操作*result = *first,*(result+i)=*(first+i)直到first+i达到last。最终返回一个迭代器result + (last-first).copy对其template参数所要求的条件非常宽松。其输入区间只需要是InputIterator构成即可，输出区间只需要是OutputIterator构成即可。这意味着你可以使用copy算法，将任何容器的任何一段区间的内容，复制到任何容器的任何一段区间上。

        对于每个从0到last-first的整数n，copy执行赋值操作*(result+n) = *(first+n).赋值操作是向前操作的。

        如果输入区间和输出区间完全没有重叠，当然毫无问题，否则便需特别注意。如下图所示：

第二种情况当result位于first与last当中时，可能会出现错误。

从稍后即将显示的源码可知，copy元素时一一进行元素的赋值操作，如果输出区间的起点位于输入区间内，copy算法便(可能)会在输入区间的(某些)元素尚未被复制之前，就覆盖其值，导致错误的结果。在这里我们一再使用可能这个字眼，是因为，如故宫copy算法根据其所接收迭代器的特性决定调用memmove()来执行任务，就不会造成上述错误，因为memmove()，会考虑重叠的情况再进行处理，保证不会出现值还没被拷贝就被覆盖的情况。

下面的测试代码，是对上图copy的测试

#include <iostream>
#include <algorithm>
#include <deque>
#include <list>
using namespace std;template <class T>
struct display {void operator() (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 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);auto first = id.begin(); // 此处用了auto关键字，需要c++11才能编译通过auto last = id.end();++first;++first;cout << *first << endl;  // 2--last;--last;cout << *last << endl;  // 7auto result = id.begin();cout << *result << endl ; // 0copy(first, last, result);for_each(id.begin(), id.end(), display<int>());  // 2 3 4 5 5 6 7 8cout << endl;}{int ia[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};list<int> id(ia, ia+9);auto first = id.begin(); // 此处用了auto关键字，需要c++11才能编译通过auto last = id.end();++first;++first;cout << *first << endl;  // 2--last;--last;cout << *last << endl;  // 7auto result = id.begin();advance(result, 4);  // result + 4cout << *result << endl ; // 4copy(first, last, result);for_each(id.begin(), id.end(), display<int>());  // 0 1 2 3 2 3 2 3 2cout << endl;// 本例结果错误，因为调用copy算法不是使用memmove执行实际复制操作}return 0;
}

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

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

        如果我们想将元素插入(而非赋值)序列之内，那么明白使用序列容器的insert成员函数，要么使用copy算法搭配insert_iterator.

        现在我们来看看copy算法庞大的实现细节。下面是对外接口

template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) {return __copy_dispatch<InputIterator, OutputIterator>()(first, last, result);// 注意此处是先构造了对象，而后将参数传递给了给对象
}

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

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

        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)
template <class T>
struct __copy_dispatch<T*, T*> {OutputIterator operator()(T* first, T* last, T* result) {typedef typename __type_traits<T>::has_trivial_assignment_operator t;return __copy_t(first, last, result, t());}
};// 偏特化版本(2)
template <class T>
struct __copy_dispatch<const T*, T*> {OutputIterator 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());}
};

        这里必须从完全泛化版和偏特化版本的区别进行区分。首先__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 InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last, OutputIterator result, random_access_iterator_tag) {return copy_d(first, last, result, distance_type(first));
}template <class InputIterator, class OutputIterator, class Distance>
inline OutputIterator __copy_d(RandomAccessIterator first, RandomAccessIterator last, OutputIterator result, Distance*) {for (Distance n = last - first; n > 0; --n, ++result, ++first) *result = *first;return result;
}

        这是__copy_dispatch()完全泛化的故事。现在看看连个偏特化版本。这连个偏特化版本再"参数为原生指针形式"的前提下，希望进一步探测"指针所指之物是否具有trivial assignment operator(平凡赋值操作符)".这一点对效率影响不小，因为这里的复制操作是有assignment操作符负责，如果指针所指对象拥有non-trivial assignment operator,复制操作就一定得通过它来进行。但如果指针所指对象拥有的是trivial assignment operator，复制操作可以不通过它，直接以最快速的内存拷贝方式(memmove())完成。C++语言本身无法让我们侦测某个对象的型别是否具有trivial assignment operator，但是SGI STL采用__type_traits<>编程技巧来弥补，参见迭代器与traits编程技法-CSDN博客 。注意，通过增加一层间接性的手法。我们得以区分两个不同的copy_t():

//以下版本适用于所指对象具备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, const T* last, T* result, __false_type) {return __copy_d(first, last, result, (ptrdiff_t*)0);
}

        以上就死copy()的故事，一个无所不用其极地强化执行效率的故事。具体的测试用例，留给读者自行测试。

copy_backward

template<class BidrectionalIterator1, class BidrectionalIterator2>
inline BidrectionalIterator2 copy_backward(BidrectionalIterator1 first, BidrectionalIterator1 last, BidrectionalIterator2 result) ;

        这个算法的考虑以及实现的技巧与copy()十分类似，其操作示意图如下所示

        将[first,last)区间的每一个元素，以逆行的方式复制到result-1为起点，方向亦为逆行的区间上，换句话说，copy_backward算法会执行操作*(result-1)=*(last-1),*(result-2)=*(last-2),...依此类推。返回一个迭代器result - (last - first).copy_backward所接受的迭代器必须是BidrectionalIterator，才能够指针--。我们可以使用copy_backward算法，将任何一段区间的内容，复制到任何容器的任何一段区间上。关于区间重叠的问题，和copy函数处理是大体相当的逻辑，此处不在赘述，有兴趣的读者，可以再参考STL源码进行学习。

参考文档《STL源码剖析》--侯捷