算法 — copy · STL源碼分析

為了效率，copy算法可謂無所不用其極，通過分析copy算法能夠體會STL的精妙。首先是三個對外接口： ~~~ 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); } ~~~ 如果傳入的迭代器是字符型的原生指針，那么直接使用底層的memmove拷貝，效率是非常高的，但如果是普通的迭代器，則需要進一步分析了。再看看__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)); } }; 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()); } }; ~~~ 首先分析泛化版本。如果迭代器仍為普通迭代器，則調用泛化版本。它要根據迭代器的類型（輸入或隨機）調用不同的函數： ~~~ 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> inline OutputIterator __copy(RandomAccessIterator first, RandomAccessIterator last, OutputIterator result, random_access_iterator_tag) // 隨機迭代器 { return __copy_d(first, last, result, distance_type(first)); } ~~~ 由于輸入迭代器的移動只能靠operator++，所以采用逐個賦值。如果是隨機迭代器，則繼續往下調用： ~~~ 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; } ~~~ 這里之所以要再單獨定義一個函數是因為下述的原生指針版本也可能會調用它。由于是隨機迭代器，所以它是以n是否大于0為循環判斷條件。相比于輸入迭代器的判斷條件first != last，這個版本顯然效率是要高一些的。這就充分利用了迭代器之間的區別盡可能的進行效率優化。下面分析兩個特化版本。當迭代器為原生指針時，調用__copy_t，它的第三個參數是用來判斷指針所指類型是否真的需要用復制操作符來一個個復制（也就是判斷是trivial還是non-trivial），這種判斷工作就交給了類型萃取器__type_traits來完成。根據是否需要單獨復制可以把__copy_t分成兩個版本： ~~~ template <class T> inline T* __copy_t(const T* first, const T* last, T* result, __true_type) { // trivial 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) { // non-trivial return __copy_d(first, last, result, (ptrdiff_t*) 0); } ~~~ trivial版本就很容易了，直接memmove，不需要做過多的復制動作。而non-trivial版本的拷貝則需要逐一進行。由于原生指針屬于隨機迭代器，所以它可以退而求其次，調用剛才介紹的__copy_d函數。至此，一個既支持泛化，又具有極高效率的copy函數誕生了！參考：《STL源碼剖析》 P314.