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

/// 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 = http://www.mamicode.com/*__first;>
C++ STL源码学习之算法篇