《STL源码剖析》学习笔记(3)

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

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

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

19,sort算法,SGI中采用了IntroSort,其行为在大部分情况下几乎与median-of-3 Quick Sort完全相同,但是当分割行为有恶化为二次行为的倾向时,能够自我侦测,转而改用Heap Sort,又比一开始就使用Heap Sort来的好。SGI的sort采用__lg(Size n)来确定递归调用次数,一旦调用次数大于这个的时候就判定为恶化,然后调用Heap Sort。当元素个数少于16个的时候就会跳出Quick Sort,等待最后的插入排序。插入排序中还有一些小技巧,具体见源码。

 
template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, 
                            RandomAccessIterator last, T*) {
  T value = *last;
  if (value < *first) {  //尾大于头,直接移动
    copy_backward(first, last, last + 1);
    *first = value;
  }
  else
    __unguarded_linear_insert(last, value);
}
 
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
  RandomAccessIterator next = last;
  --next;
  while (value < *next) {
    *last = *next;
    last = next;
    --next;
  }
  *last = value;
}
 
template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, 
                            RandomAccessIterator last) {
  if (last - first > __stl_threshold) {
    __insertion_sort(first, first + __stl_threshold);
    __unguarded_insertion_sort(first + __stl_threshold, last);
  }
  else
    __insertion_sort(first, last);
}
 
 
template <class Size>
inline Size __lg(Size n) {
  Size k;
  for (k = 0; n > 1; n >>= 1) ++k;
  return k;
}
 
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
  while (last - first > __stl_threshold) { //元素个数少于16个话就跳出introsort
    if (depth_limit == 0) {  //调用次数太多,判定为恶化,调用Heap Sort
      partial_sort(first, last, last);
      return;
    }
    --depth_limit;
    RandomAccessIterator cut = __unguarded_partition
      (first, last, T(__median(*first, *(first + (last - first)/2),
                               *(last - 1))));
    __introsort_loop(cut, last, value_type(first), depth_limit);
    last = cut;
  }
}
 
template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
  if (first != last) {
	//先调用introsort,排序排个差不多,然后调用insertion_sort
    __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
    __final_insertion_sort(first, last);
  }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*