C++ STL源碼學習之算法篇

C++ STL源碼學習之算法篇

///由於篇幅太長，因此，刪去了很多接口，只分析了內部實現，算法對迭代器的要求也被刪去

/// search.
template 
_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 
_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 
_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 
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
                            _EuclideanRingElement __n)
{
  while (__n != 0) {
    _EuclideanRingElement __t = __m % __n;
    __m = __n;
    __n = __t;
  }
  return __m;
}

///對forward_iterator采用的算法
///由於forward_iterator的限制，做了一些重復的復制工作
template 
_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 
_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 
_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 
_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 
_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 
_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 
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
  _RandomAccessIter __next = __last;
  --__next;
  while (__val < *__next) {
    *__last = *__next;
    __last = __next;
    --__next;
  }
  *__last = __val;
}


template 
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 
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 
void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
                                    _RandomAccessIter __last, _Tp*) {
  for (_RandomAccessIter __i = __first; __i != __last; ++__i)
    __unguarded_linear_insert(__i, _Tp(*__i));
}

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

///對部分排序的區間進行最後的整體排序
template 
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 
inline _Size __lg(_Size __n) {
  _Size __k;
  for (__k = 0; __n != 1; __n >>= 1) ++__k;
  return __k;
}

///部分排序，保證__first,__middle之間的元素最小並且有序
template 
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 
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 
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 
_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 
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 
_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 
_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 
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 
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 
_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 
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 
_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 
_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 
_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 
_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 
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 
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 
_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 
_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 
_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 
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;
}