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

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

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