欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL源码剖析——基本算法copy

程序员文章站 2024-02-11 20:42:58
...

copy算法可将指定区间[first, last)内的元素复制到输出区间[result, result + (last - first))内。它时常被调用,所以一个需要有一个高效率的算法。
SGI STL copy算法用了各种办法,包括函数重载、型别特性(type traits)、偏特化(partial specilization)等编程技巧加强效率。

SGI STL的copy算法的完整流程

STL源码剖析——基本算法copy

看不进去了,直接复制代码过来,头晕!!!

// 这是不支持随机访问的情况
template <class InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last,
                             OutputIterator result, input_iterator_tag)
{
  // first != last导致要进行迭代器的比较, 效率低
  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*)
{
  // 不进行迭代器间的比较, 直接指定循环次数, 高效
  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)
  {
    // 判断其内部是否具有trivial_assignment_operator, 以进行派发
    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 */
 
// 将[first, last)拷贝到result处
template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
                           OutputIterator result)
{
  // 此处进行函数派发操作
  return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
}
 
// 针对char字符串的特化, 效率至上, C++的设计理念
inline char* copy(const char* first, const char* last, char* result)
{
  memmove(result, first, last - first);
  return result + (last - first);
}
 
// 针对wchar_t字符串的特化, 效率至上, C++的设计理念
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);
}
 
 
template <class BidirectionalIterator1, class BidirectionalIterator2>
inline BidirectionalIterator2 __copy_backward(BidirectionalIterator1 first,
                                              BidirectionalIterator1 last,
                                              BidirectionalIterator2 result)
{
  while (first != last) *--result = *--last;
  return result;
}
 
 
template <class BidirectionalIterator1, class BidirectionalIterator2>
struct __copy_backward_dispatch
{
  BidirectionalIterator2 operator()(BidirectionalIterator1 first,
                                    BidirectionalIterator1 last,
                                    BidirectionalIterator2 result)
  {
    return __copy_backward(first, last, result);
  }
};
 
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 
template <class T>
inline T* __copy_backward_t(const T* first, const T* last, T* result,
                            __true_type)
{
  const ptrdiff_t N = last - first;
  memmove(result - N, first, sizeof(T) * N);
  return result - N;
}
 
template <class T>
inline T* __copy_backward_t(const T* first, const T* last, T* result,
                            __false_type)
{
  return __copy_backward(first, last, result);
}
 
template <class T>
struct __copy_backward_dispatch<T*, T*>
{
  T* operator()(T* first, T* last, T* result)
  {
    typedef typename __type_traits<T>::has_trivial_assignment_operator t;
    return __copy_backward_t(first, last, result, t());
  }
};
 
template <class T>
struct __copy_backward_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_backward_t(first, last, result, t());
  }
};
 
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 
// 将[first, last)的元素反向拷贝到(..., last)处, 其机制和copy非常接近, 不做说明
template <class BidirectionalIterator1, class BidirectionalIterator2>
inline BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
                                            BidirectionalIterator1 last,
                                            BidirectionalIterator2 result)
{
  return __copy_backward_dispatch<BidirectionalIterator1,
                                  BidirectionalIterator2>()(first, last,
                                                            result);
}
 
 
template <class InputIterator, class Size, class OutputIterator>
pair<InputIterator, OutputIterator> __copy_n(InputIterator first, Size count,
                                             OutputIterator result,
                                             input_iterator_tag)
{
  for ( ; count > 0; --count, ++first, ++result)
    *result = *first;
  return pair<InputIterator, OutputIterator>(first, result);
}
 
template <class RandomAccessIterator, class Size, class OutputIterator>
inline pair<RandomAccessIterator, OutputIterator>
__copy_n(RandomAccessIterator first, Size count,
         OutputIterator result,
         random_access_iterator_tag)
{
  // 使用copy()以选择最高效的拷贝算法
  RandomAccessIterator last = first + count;
  return pair<RandomAccessIterator, OutputIterator>(last,
                                                    copy(first, last, result));
}
 
// 从first拷贝n个值到result处
template <class InputIterator, class Size, class OutputIterator>
inline pair<InputIterator, OutputIterator>
copy_n(InputIterator first, Size count,
       OutputIterator result)
{
  // 进行函数派发, 选咋高效版本
  return __copy_n(first, count, result, iterator_category(first));
}

参考:
STL源码分析之copy算法

相关标签: STL源码剖析