C++ STL读书笔记：算法

备注：

本读书笔记基于侯捷先生的《STL源码剖析》，截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL，部分代码删除了头部的版权注释，但代码版权属于原作者。
小弟初看stl，很多代码都不是太懂，注释可能有很多错误，还请路过的各位大牛多多给予指导。
为了降低学习难度，作者这里换到了SGI-STL-2.91.57的源码来学习，代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】

这里只简单的笔记下部分算法的代码实现方式，详细的介绍可以参考网址【 http://www.cplusplus.com/reference/algorithm/ 】。

stl_numeric.h部分函数笔记：

power：

power是计算某个数x的n次方。代码实现的比较有意思，这里小弟语文学的不好，不知道怎么描述，这里用几个数来举个例子吧。

template <class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op) {
  if (n == 0)
    return identity_element(op);//如果是0，直接返回1
  else {
		//把前面的0全部循环干掉
    while ((n & 1) == 0) {
      n >>= 1;
      x = op(x, x);
    }
    T result = x;
    n >>= 1;
    while (n != 0) {
      x = op(x, x);	//把前面的0全部循环干掉
      if ((n & 1) != 0)//不为0了，就把值取出来和之前的值乘一起（由于是幂，这里的相乘在幂上反映为指数相加）
        result = op(result, x);
      n >>= 1;
    }
    return result;
  }
}

stl_algobase.h部分函数笔记：

min：

//该函数很简单，但是需要注意的是传入和返回的参数都是const类型的引用，这样可以保证传入和返回的
//是同一个对象，而不是拷贝构造函数构造出来的。
template <class T>
inline const T& min(const T& a, const T& b) {
  return b < a ? b : a;
}

copy:

copy为了提高效率，进行了很多特化，如下图所示：

template <class InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last,
                             OutputIterator result, input_iterator_tag)//iterator不支持随机读取
{
	//通过判断first和last是否相等来控制循环，速度比判断整数n是否大于0要慢。
  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*)//在iterator支持随机读取的情况下，可以通过first和last得到要复制的元素的数目有多少，这样可以加快for循环的速度。
{
	//首先计算出需要循环的次数n，然后通过简单的判断整数n来控制循环，比调用iterator重载的!=要快。
  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)//iterator支持随机读取
{
  return __copy_d(first, last, result, distance_type(first));
}

//__copy_dispatch完全泛化版本,传入全部是iterator，根据iterator的属性进行不同的判断。
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 

//__copy_t偏特化版本，注意__true_type，说明拷贝构造函数很简单，可以直接复制内存
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);
}

//__copy_t偏特化版本，注意__false_type，说明拷贝构造函数比较复杂，不能简单的赋值内存，必须通过
//显式的调用拷贝构造函数才可以。
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);
}

//__copy_dispatch特化版本1，传入为原始指针类型，其实说明可以随机读取（类似数组）。
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());
  }
};

//__copy_dispatch特化版本2，注意第一个参数为const类型，传入为原始指针类型，其实说明可以随机读取（类似数组）。
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 */


//主入口函数1。完全泛化版本
template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
                           OutputIterator result)
{
  return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
}

//主入口函数2，当输入参数类型为char*时，直接调用memmove
inline char* copy(const char* first, const char* last, char* result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

//主入口函数3，当输入参数类型为wchar_t*时，直接调用memmove
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);
}

stl_algo.h部分函数笔记：

for_each:

//for_each的函数实现。
//示例代码参考 http://www.cplusplus.com/reference/algorithm/for_each/
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f) {
  for ( ; first != last; ++first)
    f(*first);
  return f;
}

find_if:

//find_if的函数实现。
//示例代码参考 http://www.cplusplus.com/reference/algorithm/find_if/
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
                      Predicate pred) {
  while (first != last && !pred(*first)) ++first;
  return first;
}

__insertion_sort：

//循环插入式排序
//在循环中对【first，i】区间内的元素进行排序，然后不断的递增i，扩大排序区间。
//这里有个默认的逻辑是当i指向的元素要插入区间【first,i-1】时，这里的【first,i-1】是已经排序好的。
template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
  if (first == last) return; 
  for (RandomAccessIterator i = first + 1; i != last; ++i)
    __linear_insert(first, i, value_type(first));
}

__linear_insert：

//插入式排序。
//由于调用逻辑的关系，可以知道【first,last-1】是已经排序好的。这里只需要把last指向的元素
//插入到这个已经排序好的区间即可。
template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, 
                            RandomAccessIterator last, T*) {
  T value = *last;
  if (value < *first) {//如果*last<*first，那么说明*last小于区间内的所有元素，应该放到区间的头部。
  	//这里采取的方法是所有的元素向后拷贝一格，然后把*last的值赋值到头部。
    copy_backward(first, last, last + 1);
    *first = value;
  }
  else//如果*last>*first，就需要遍历区间，查找*last可以放置的位置，这里采取的是从区间尾部开始反向查找的方法。
    __unguarded_linear_insert(last, value);
}

__unguarded_linear_insert：

//上述插入式排序的后续逻辑。
//从last指向的元素开始反向查找，找到一个位置能够放下value，使该区间满足排序规律。
//由于是内部实现函数，因此这里使用了unguarded，即一定能够找到这个位置，无需进行有效性判断。
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;
}

__unguarded_insertion_sort：

//内部调用了__unguarded_insertion_sort_aux。
template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first, 
                                RandomAccessIterator last) {
  __unguarded_insertion_sort_aux(first, last, value_type(first));
}

__unguarded_insertion_sort_aux：

//该函数循环调用__unguarded_linear_insert,即从i处开始反向查找符合排序要求的位置。
template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
                                    RandomAccessIterator last, T*) {
  //注意这里的循环是从first开始的，因此排序区间是【first，i】，i通过不断递增。
  //和__insertion_sort的实现是一致的。
  for (RandomAccessIterator i = first; i != last; ++i)
    __unguarded_linear_insert(i, T(*i));
}

sort：

const int __stl_threshold = 16;
//最终版本的插入法排序，通过判断待排序的数目来选择不同的排序方式。
template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, 
                            RandomAccessIterator last) {
  if (last - first > __stl_threshold) {//如果元素个数大于16个
    __insertion_sort(first, first + __stl_threshold);//那么就先将前16个元素排好序
    __unguarded_insertion_sort(first + __stl_threshold, last);
    //再排序剩下的（这里是不是可以循环判断剩下未排序的个数是否大于16）。
  }
  else
    __insertion_sort(first, last);//小于16个，直接排序。
}

//下面的注释拷贝自《STL源码剖析》P396

//寻找2^k <= n 的最大值k
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) {
    if (depth_limit == 0) {
      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_loop(first, last, value_type(first), __lg(last - first) * 2);
    __final_insertion_sort(first, last);
  }
}