C++ STL源码学习之算法篇

///由于篇幅太长，因此，删去了很多接口，只分析了内部实现，算法对迭代器的要求也被删去

/// search.
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
                     _ForwardIter2 __first2, _ForwardIter2 __last2)
{
  /// Test for empty ranges
  if (__first1 == __last1 || __first2 == __last2)
    return __first1;

  /// Test for a pattern of length 1.
  _ForwardIter2 __tmp(__first2);
  ++__tmp;
  if (__tmp == __last2)   ///如果欲寻找区间范围为1，则调用find函数处理
    return find(__first1, __last1, *__first2);

  /// General case.

  _ForwardIter2 __p1, __p;

  __p1 = __first2; ++__p1;

  _ForwardIter1 __current = __first1;

  while (__first1 != __last1) {
    ///先使用find找到欲寻找区间的第一个元素在主区间中出现的位置
    ///将其赋给__first1，其前面的区间已不需要再考虑
    __first1 = find(__first1, __last1, *__first2);

    if (__first1 == __last1)  ///第一个元素不存在，说明欲寻找区间一定不存在
      return __last1;

    __p = __p1;  ///__p为欲寻找区间的第二个元素
    __current = __first1;

    ///欲寻找区间的第一个元已经排除素为主区间的最后一个元素，由于前面
    ///已经排除欲寻找区间长度为1的情况，因此可判定寻找失败
    if (++__current == __last1)
      return __last1;

    ///挨个比较两个区间
    while (*__current == *__p) {
      ///欲寻找区间结束，查找成功，返回__first1，即欲寻找区间
      ///的第一个元素在主区间的位置
      if (++__p == __last2)
        return __first1;

    ///主区间先于欲寻找区间结束，查找失败
      if (++__current == __last1)
        return __last1;
    }

     ///某个元素不匹配，返回到主区间匹配到与查找区间第一个元素的位置
     ///继续匹配
    ++__first1;
  }
  return __first1;
}

/// search_n.  Search for __count consecutive copies of __val.

template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
                      _Integer __count, const _Tp& __val) {
  if (__count <= 0)
    return __first;
  else {
        ///先使用find找到第一个__val
    __first = find(__first, __last, __val);

    ///主区间尚未被遍历完
    while (__first != __last) {
      _Integer __n = __count - 1;
      _ForwardIter __i = __first;
      ++__i;

      while (__i != __last && __n != 0 && *__i == __val) {
        ++__i;
        --__n;
      }

      if (__n == 0)  ///匹配成功
        return __first;
      else        ///直接从主区间已遍历的下一个位置开始匹配
                  ///因为是n个相同元素的匹配，因此，前面不可能有漏配的区间
        __first = find(__i, __last, __val);
    }

    ///主区间已被遍历完，查找失败
    return __last;
  }
}

// unique and unique_copy

template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result, _Tp*) {
  _Tp __value = *__first;
  *__result = __value;

  while (++__first != __last)
  {
    ///如果__value != *__first，执行循环体进行复制，否则忽略
    ///进行下一个元素的处理
    if (!(__value == *__first)) {

      __value = *__first;
      *++__result = __value;
    }

  }

  return ++__result;
}

/// rotate and rotate_copy, and their auxiliary functions
///以middle为界，对first,last进行翻转的一组函数，即将[first,middle,last)
///转置成为[middle,last-1,first,middle)，采用了针对forward_iter,bidrectionaal_iter,
///random_iter三种迭代器的不同算法，力求高效

///辗转相除法求m和n的最大公约数
template <class _EuclideanRingElement>
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
                            _EuclideanRingElement __n)
{
  while (__n != 0) {
    _EuclideanRingElement __t = __m % __n;
    __m = __n;
    __n = __t;
  }
  return __m;
}

///对forward_iterator采用的算法
///由于forward_iterator的限制，做了一些重复的复制工作
template <class _ForwardIter, class _Distance>
_ForwardIter __rotate(_ForwardIter __first,
                      _ForwardIter __middle,
                      _ForwardIter __last,
                      _Distance*,
                      forward_iterator_tag) {
  ///不需要翻转的情况
  if (__first == __middle)
    return __last;
  if (__last  == __middle)
    return __first;


  _ForwardIter __first2 = __middle;

  ///此循环保证把[middle,last)调整至最前端,其实这个循环出现主要是为了
  ///得到new_middle，而且轻微的提高性能(和最后面的循环相比，他的判断条件
  ///少了一个),如果不考虑这两点，这个循环完全可以去掉。
  do {
    swap(*__first++, *__first2++);

    if (__first == __middle)
      __middle = __first2;
  } while (__first2 != __last);

  ///此时，[middle,last)已经调整至最前端，现在只需在[first,middle)内部调整
  _ForwardIter __new_middle = __first;

  __first2 = __middle;

  while (__first2 != __last) {

    swap (*__first++, *__first2++);
    if (__first == __middle)
      __middle = __first2;
    else if (__first2 == __last)
      __first2 = __middle;
  }

  return __new_middle;
}

///对于BidrectionalIter采用的算法，通过不同条件下调用reverse实现
template <class _BidirectionalIter, class _Distance>
_BidirectionalIter __rotate(_BidirectionalIter __first,
                            _BidirectionalIter __middle,
                            _BidirectionalIter __last,
                            _Distance*,
                            bidirectional_iterator_tag) {

  if (__first == __middle)
    return __last;
  if (__last  == __middle)
    return __first;

  __reverse(__first,  __middle, bidirectional_iterator_tag());
  __reverse(__middle, __last,   bidirectional_iterator_tag());

  while (__first != __middle && __middle != __last)
    swap (*__first++, *--__last);

  if (__first == __middle) {
        ///__middle之前元素较少，因此需要将__middle,__last区间
        ///（此区间未被交换）翻转到原来的顺序
    __reverse(__middle, __last,   bidirectional_iterator_tag());
    return __last;
  }
  else {
    __reverse(__first,  __middle, bidirectional_iterator_tag());
    return __first;
  }
}

template <class _RandomAccessIter, class _Distance, class _Tp>
_RandomAccessIter __rotate(_RandomAccessIter __first,
                           _RandomAccessIter __middle,
                           _RandomAccessIter __last,
                           _Distance *, _Tp *) {

  _Distance __n = __last   - __first; ///总元素数
  _Distance __k = __middle - __first; ///__middle之前的元素数(不包括__middle)
  _Distance __l = __n - __k;   ///__middle之后的元素数

  _RandomAccessIter __result = __first + (__last - __middle); ///new middle

  if (__k == 0)
    return __last;

  else if (__k == __l) {   ///__middle前后元素数目相同
    swap_ranges(__first, __middle, __middle);
    return __result;
  }

  _Distance __d = __gcd(__n, __k);  ///__d是__middle之前元素数和总元素数的最大公约数

  for (_Distance __i = 0; __i < __d; __i++) {  ///循环__d次即可
    _Tp __tmp = *__first;
    _RandomAccessIter __p = __first;

    if (__k < __l) {      ///__middle前面的元素数目小于后面
      for (_Distance __j = 0; __j < __l/__d; __j++) {

        if (__p > __first + __l) {   ///__p在new middle 之后
          *__p = *(__p - __l);      ///*(__p - __l)应该放在__p所在位置
          __p -= __l;               ///将__p退后__l
        }

        *__p = *(__p + __k);     ///__p在new middle 之前时，这个赋值永远是精准地
        __p += __k;
      }
    }
    else {
      for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
        if (__p < __last - __k) {
          *__p = *(__p + __k);
          __p += __k;
        }

        *__p = * (__p - __l);
        __p -= __l;
      }
    }

    *__p = __tmp;
    ++__first;   ///每次循环将__first增1
  }

  return __result;
}

/// partition, stable_partition, and their auxiliary functions

template <class _ForwardIter, class _Predicate>
_ForwardIter __partition(_ForwardIter __first,
		         _ForwardIter __last,
			 _Predicate   __pred,
			 forward_iterator_tag) {
  if (__first == __last) return __first;

  while (__pred(*__first))  ///找到第一个不符合条件的元素
    if (++__first == __last) return __first;

  _ForwardIter __next = __first;

  while (++__next != __last)
    if (__pred(*__next)) {   ///找到符合条件的next将其交换到前面
      swap(*__first, *__next);
      ++__first;
    }

  return __first;
}

///克服了前面由于forward_iter的限制而产生的重复交换
template <class _BidirectionalIter, class _Predicate>
_BidirectionalIter __partition(_BidirectionalIter __first,
                               _BidirectionalIter __last,
			       _Predicate __pred,
			       bidirectional_iterator_tag) {
  while (true) {
    while (true)
      if (__first == __last)
        return __first;
      else if (__pred(*__first))
        ++__first;
      else
        break;

    --__last;

    while (true)
      if (__first == __last)
        return __first;
      else if (!__pred(*__last))
        --__last;
      else
        break;

    iter_swap(__first, __last);
    ++__first;
  }
}

///调用此函数需保证*__first<=__pivot<=*(__last-1),因为有这个前提条件
///所以不需要判断是否越界
template <class _RandomAccessIter, class _Tp>
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
                                        _RandomAccessIter __last,
                                        _Tp __pivot)
{
  while (true) {
    while (*__first < __pivot)
      ++__first;

    --__last;

    while (__pivot < *__last)
      --__last;

    if (!(__first < __last))
      return __first;

    iter_swap(__first, __last);
    ++__first;
  }
}

///STL sort函数，为了高效，可谓是把基本的排序算法都用到了
///其主体采用快速排序和插入排序，当快速排序的效率变得不可接受时
///采用堆排序。当划分的子区间小于等于一定程度(即下面的_stl_threshold)时
///退出快速排序，留给最后的插入排序处理

///下面是他的一些辅助函数和他本身的实现
const int __stl_threshold = 16;

/// sort() and its auxiliary functions.

///插入函数：是插入排序的辅助函数
///调用此函数同样必须保证*__first<__val,其中__first没有显式出现
///因此，同样不需要判断越界
template <class _RandomAccessIter, class _Tp>
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
  _RandomAccessIter __next = __last;
  --__next;
  while (__val < *__next) {
    *__last = *__next;
    __last = __next;
    --__next;
  }
  *__last = __val;
}


template <class _RandomAccessIter, class _Tp>
inline void __linear_insert(_RandomAccessIter __first,
                            _RandomAccessIter __last, _Tp*) {
  _Tp __val = *__last;

  if (__val < *__first) {
    copy_backward(__first, __last, __last + 1);
    *__first = __val;
  }
  else
    __unguarded_linear_insert(__last, __val);
}

///插入排序，是排序的规模小到一定程度时采用的排序方法
template <class _RandomAccessIter>
void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    __linear_insert(__first, __i, __VALUE_TYPE(__first));
}

///插入排序，此时必须保证*__first是最小值
template <class _RandomAccessIter, class _Tp>
void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
                                    _RandomAccessIter __last, _Tp*) {
  for (_RandomAccessIter __i = __first; __i != __last; ++__i)
    __unguarded_linear_insert(__i, _Tp(*__i));
}

template <class _RandomAccessIter>
inline void __unguarded_insertion_sort(_RandomAccessIter __first,
                                _RandomAccessIter __last) {
  __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
}

///对部分排序的区间进行最后的整体排序
template <class _RandomAccessIter>
void __final_insertion_sort(_RandomAccessIter __first,
                            _RandomAccessIter __last) {
  if (__last - __first > __stl_threshold) {
  ///长度大于16时，对前面的16个元素进行_insertion_sort后
  ///对后续元素则可直接调用__unguarded_insertion_sort以提高效率
    __insertion_sort(__first, __first + __stl_threshold);
    __unguarded_insertion_sort(__first + __stl_threshold, __last);
  }
  else ///长度小于16时不必调用两次函数
    __insertion_sort(__first, __last);
}

///lg 2 为底 n的对数，用于计算一定长度的序列排序需要的快速排序
///最大递归深度，以判断其效率是否已下降到不可接受的程度
template <class _Size>
inline _Size __lg(_Size __n) {
  _Size __k;
  for (__k = 0; __n != 1; __n >>= 1) ++__k;
  return __k;
}

///部分排序，保证__first,__middle之间的元素最小并且有序
template <class _RandomAccessIter, class _Tp>
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
                    _RandomAccessIter __last, _Tp*) {
  make_heap(__first, __middle);
  for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
    if (*__i < *__first)
      __pop_heap(__first, __middle, __i, _Tp(*__i),
                 __DISTANCE_TYPE(__first));
  sort_heap(__first, __middle);
}


template <class _RandomAccessIter, class _Tp, class _Size>
void __introsort_loop(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Tp*,
                      _Size __depth_limit)
{
  ///长度不大于16退出，由最后的插入排序处理
  ///以减小递归深度
  while (__last - __first > __stl_threshold) {

    if (__depth_limit == 0) {
    ///说明快速排序效率已经不可接受，转而采用堆排序
    ///这里虽然调用partial_sort，但实际上使用了其完全的堆排序(__middle = __last)
      partial_sort(__first, __last, __last);
      return;
    }

    ///每进行一次递归调用，__depth_limit减少1次
    --__depth_limit;

    ///快速排序的标志元用首、尾元素和中间元素的中间值得到，得到的值
    ///一定大于等于first而小于等于__last-1，因而采用__unguarded_partition
    ///并根据中间值来划分子序列
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1))));

    ///对后一半子序列进行递归调用快速排序
    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);

    __last = __cut; ///在while循环中处理前一半子序列，从而减少了递归调用的次数
  }
}


template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
                 _LessThanComparable);
  if (__first != __last) {

    __introsort_loop(__first, __last,
                     __VALUE_TYPE(__first),
                     __lg(__last - __first) * 2);
    ///最后的插入排序处理
    __final_insertion_sort(__first, __last);
  }
}


template <class _InputIter, class _RandomAccessIter, class _Distance,
          class _Tp>
_RandomAccessIter __partial_sort_copy(_InputIter __first,
                                      _InputIter __last,
                                      _RandomAccessIter __result_first,
                                      _RandomAccessIter __result_last,
                                      _Distance*, _Tp*) {
  if (__result_first == __result_last) return __result_last;
  _RandomAccessIter __result_real_last = __result_first;

  while(__first != __last && __result_real_last != __result_last) {
    *__result_real_last = *__first;
    ++__result_real_last;
    ++__first;
  }

  make_heap(__result_first, __result_real_last);

  while (__first != __last) {   ///将源区间内剩余的较小元素调整至目标区间
    if (*__first < *__result_first)

      __adjust_heap(__result_first, _Distance(0),
                    _Distance(__result_real_last - __result_first),
                    _Tp(*__first));
    ++__first;
  }
  sort_heap(__result_first, __result_real_last);
  return __result_real_last;
}

/// nth_element() and its auxiliary functions.
///保证排序以后nth之前的元素均比nth小，nth之后的元素均比nth大
template <class _RandomAccessIter, class _Tp>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                   _RandomAccessIter __last, _Tp*) {

  while (__last - __first > 3) {
        ///长度大于3时进行分割，
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),

                                        *(__last - 1))));

    ///缩小分割区间
    if (__cut <= __nth)
      __first = __cut;
    else
      __last = __cut;
  }

  ///区间长度不大于3时直接插入排序即可
  __insertion_sort(__first, __last);
}

/// Binary search (lower_bound, upper_bound, equal_range, binary_search).
///看lower_bound和upper_bound实现的区别
template <class _ForwardIter, class _Tp, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
                           const _Tp& __val, _Distance*)
{
  _Distance __len = 0;
  distance(__first, __last, __len);
  _Distance __half;
  _ForwardIter __middle;

  while (__len > 0) {

    __half = __len >> 1;   ///右移1位，相当于除2
    __middle = __first;

    advance(__middle, __half);  ///找到middle，并比较

    ///只有当val > *__middle时才向后查找
    if (*__middle < __val) {
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
    else   ///val <= *__middle时均向前查找
      __len = __half;
  }
  return __first;
}

template <class _ForwardIter, class _Tp, class _Distance>
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
                           const _Tp& __val, _Distance*)
{
  _Distance __len = 0;
  distance(__first, __last, __len);
  _Distance __half;
  _ForwardIter __middle;

  while (__len > 0) {
    __half = __len >> 1;
    __middle = __first;
    advance(__middle, __half);

    ///只有当val < *__middle时才向前查找
    if (__val < *__middle)
      __len = __half;
    else {    ///val >= *__middle时均向后查找
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
  }
  return __first;
}


template <class _ForwardIter, class _Tp, class _Distance>
pair<_ForwardIter, _ForwardIter>
__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
              _Distance*)
{
  _Distance __len = 0;
  distance(__first, __last, __len);
  _Distance __half;
  _ForwardIter __middle, __left, __right;

  while (__len > 0) {
    __half = __len >> 1;
    __middle = __first;
    advance(__middle, __half);
    ///先采用类似lower_bound的方法找到一个等于val的值
    if (*__middle < __val) {
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
    else if (__val < *__middle)
      __len = __half;
    else {     ///找到后分区间调用lower和upper_bound找到__left和__right的位置
            ///这样做要比一开始就调用lower_bound和upper_bound高效一些
      __left = lower_bound(__first, __middle, __val);
      advance(__first, __len);
      __right = upper_bound(++__middle, __first, __val);
      return pair<_ForwardIter, _ForwardIter>(__left, __right);
    }
  }

  ///说明未找到
  return pair<_ForwardIter, _ForwardIter>(__first, __first);
}

///二分查找，依赖lower_bound实现
template <class _ForwardIter, class _Tp>
bool binary_search(_ForwardIter __first, _ForwardIter __last,
                   const _Tp& __val) {

  _ForwardIter __i = lower_bound(__first, __last, __val);
  return __i != __last && !(__val < *__i);
}

/// merge, with and without an explicitly supplied comparison function.
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
                  _InputIter2 __first2, _InputIter2 __last2,
                  _OutputIter __result) {

  while (__first1 != __last1 && __first2 != __last2) {
    if (*__first2 < *__first1) {
      *__result = *__first2;
      ++__first2;
    }
    else {
      *__result = *__first1;
      ++__first1;
    }
    ++__result;
  }
  return copy(__first2, __last2, copy(__first1, __last1, __result));
}

/// Set algorithms: includes, set_union, set_intersection, set_difference,
/// set_symmetric_difference.  All of these algorithms have the precondition
/// that their input ranges are sorted and the postcondition that their output
/// ranges are sorted.
///集合类操作需要保证集合元素是已排序的，算是根据已排序
///序列的特性实现的

template <class _InputIter1, class _InputIter2>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
              _InputIter2 __first2, _InputIter2 __last2) {

  while (__first1 != __last1 && __first2 != __last2)
    if (*__first2 < *__first1)
      return false;
    else if(*__first1 < *__first2)
      ++__first1;
    else
      ++__first1, ++__first2;

  return __first2 == __last2;
}

///和merge很相似，但不会重复包含两个区间的公共元素
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _InputIter2 __last2,
                      _OutputIter __result) {

  while (__first1 != __last1 && __first2 != __last2) {
    if (*__first1 < *__first2) {
      *__result = *__first1;
      ++__first1;
    }
    else if (*__first2 < *__first1) {
      *__result = *__first2;
      ++__first2;
    }
    else {
      *__result = *__first1;
      ++__first1;
      ++__first2;
    }
    ++__result;
  }
  return copy(__first2, __last2, copy(__first1, __last1, __result));
}

///得到两个序列的交集
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _OutputIter __result) {

  while (__first1 != __last1 && __first2 != __last2)
    if (*__first1 < *__first2)
      ++__first1;
    else if (*__first2 < *__first1)
      ++__first2;
    else {
      *__result = *__first1;
      ++__first1;
      ++__first2;
      ++__result;
    }
  return __result;
}

///得到两个序列的差集
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
                           _InputIter2 __first2, _InputIter2 __last2,
                           _OutputIter __result) {

  while (__first1 != __last1 && __first2 != __last2)
    if (*__first1 < *__first2) {
      *__result = *__first1;
      ++__first1;
      ++__result;
    }
    else if (*__first2 < *__first1)
      ++__first2;
    else {
      ++__first1;
      ++__first2;
    }

  return copy(__first1, __last1, __result);
}

///两个集合的对称差集
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
                         _InputIter2 __first2, _InputIter2 __last2,
                         _OutputIter __result) {

  while (__first1 != __last1 && __first2 != __last2)
    if (*__first1 < *__first2) {
      *__result = *__first1;
      ++__first1;
      ++__result;
    }
    else if (*__first2 < *__first1) {
      *__result = *__first2;
      ++__first2;
      ++__result;
    }
    else {
      ++__first1;
      ++__first2;
    }
  return copy(__first2, __last2, copy(__first1, __last1, __result));
}

/// next_permutation and prev_permutation
///在当前序列中，从尾端往前寻找两个相邻元素，前一个记为*__i，后一个记为*__ii，
///并且满足*__i < *__ii。然后再从尾端寻找另一个元素*__j，如果满足*__j，即将
///第__i个元素与第__j个元素对调，并将第__ii个元素之后（包括__ii）的所有元素颠倒排序，
///即求出下一个序列了。
template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {

  if (__first == __last)
    return false;
  _BidirectionalIter __i = __first;
  ++__i;
  if (__i == __last)
    return false;
  __i = __last;
  --__i;

  for(;;) {
    _BidirectionalIter __ii = __i;
    --__i;
    if (*__i < *__ii) {
      _BidirectionalIter __j = __last;
      while (!(*__i < *--__j))
        {}
      iter_swap(__i, __j);
      reverse(__ii, __last);
      return true;
    }

    if (__i == __first) {
      reverse(__first, __last);
      return false;
    }
  }
}

template <class _BidirectionalIter>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {

  if (__first == __last)
    return false;
  _BidirectionalIter __i = __first;
  ++__i;
  if (__i == __last)
    return false;
  __i = __last;
  --__i;

  for(;;) {
    _BidirectionalIter __ii = __i;
    --__i;
    if (*__ii < *__i) {
      _BidirectionalIter __j = __last;
      while (!(*--__j < *__i))
        {}
      iter_swap(__i, __j);
      reverse(__ii, __last);
      return true;
    }
    if (__i == __first) {
      reverse(__first, __last);
      return false;
    }
  }
}

template <class _InputIter, class _ForwardIter>
_InputIter find_first_of(_InputIter __first1, _InputIter __last1,
                         _ForwardIter __first2, _ForwardIter __last2)
{

  for ( ; __first1 != __last1; ++__first1)
    for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
      if (*__first1 == *__iter)
        return __first1;

  return __last1;
}


/// find_end,  Search [first2, last2) as a subsequence in [first1, last1), and return
/// the *last* possible match.  Note that find_end for bidirectional iterators
/// is much faster than for forward iterators.

/// find_end for forward iterators.
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
                         _ForwardIter2 __first2, _ForwardIter2 __last2,
                         forward_iterator_tag, forward_iterator_tag)
{
  if (__first2 == __last2)
    return __last1;
  else {
    _ForwardIter1 __result = __last1;
    while (1) {
      _ForwardIter1 __new_result
        = search(__first1, __last1, __first2, __last2);
      if (__new_result == __last1)
        return __result;
      else {
        __result = __new_result;
        __first1 = __new_result;
        ++__first1;
      }
    }
  }
}

/// find_end for bidirectional iterators.
template <class _BidirectionalIter1, class _BidirectionalIter2>
_BidirectionalIter1
__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
           _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
           bidirectional_iterator_tag, bidirectional_iterator_tag)
{

  typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
  typedef reverse_iterator<_BidirectionalIter2> _RevIter2;

  _RevIter1 __rlast1(__first1);
  _RevIter2 __rlast2(__first2);
  ///使用reverse_iterator查找
  _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
                               _RevIter2(__last2), __rlast2);

  if (__rresult == __rlast1)
    return __last1;
  else {
    ///找到出现序列的一个元素的位置
    _BidirectionalIter1 __result = __rresult.base();
    advance(__result, -distance(__first2, __last2));
    return __result;
  }
}

/// is_heap, a predicate testing whether or not a range is
/// a heap.  This function is an extension, not part of the C++
/// standard.
template <class _RandomAccessIter, class _Distance>
bool __is_heap(_RandomAccessIter __first, _Distance __n)
{
  _Distance __parent = 0;
  for (_Distance __child = 1; __child < __n; ++__child) {
    if (__first[__parent] < __first[__child])  ///子节点不得大于其父节点
      return false;
    if ((__child & 1) == 0)   ///__child为偶数
      ++__parent;
  }
  return true;
}