《STL源码剖析》读书笔记

Copy算法

STL中通过使用copy函数以提供一种方便的方式来输出容器中的元素。函数copy作为泛型算法的一部分，任何容器类型都可以使用。

copy算法利用函数重载，对char 和wchar_t 的操作直接memmove，利用模版特化对于有trivial operator=的操作memmove，对于RandomAccessIterator通过头尾间隔来确定循环次数，对于InputIterator通过不断累加是否到达last来确定循环次数。

它允许我们复制元素从一个地方到另一个地方。例如输出vector的元素或复制vector的元素到另一个vector，我们可以使用copy函数。函数原型是:

template <class inputIterator, class outputIterator>
outputIterator copy(inputIterator first1, inputIterator last, outputIterator first2);

参数first1指定了开始拷贝元素的位置；参数last指定了结束位置。参数first2指定了拷贝元素到哪里。因此，参数first1和last指定了源；参数first2指定了目的。

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;
}

template <class RandomAccessIterator, class OutputIterator, class Distance>
inline OutputIterator
    __copy_d(RandomAccessIterator first, RandomAccessIterator last,
    OutputIterator result, Distance*)
{
    //通过last - first来确定循环次数，比上面的那个快一些
    for (Distance n = last - first; n > 0; --n, ++result, ++first) 
        *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_type(first));
}

template <class InputIterator, class OutputIterator>
struct __copy_dispatch
{
    OutputIterator operator()(InputIterator first, InputIterator last,
        OutputIterator result) {
            return __copy(first, last, result, iterator_category(first));
    }
};

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 

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);
}

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()(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());
    }
};

#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

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, sizeof(wchar_t) * (last - first));
        return result + (last - first);
}