C++ STL源码学习之算法篇 - c++编程基础

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

/// 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(__f

C++ STL源码学习之算法篇(一)