本文原创

stl_algobase.h 头文件定义了一些最为基本的简单操作，包括 swap、copy、fill、lexicographical_compare 等。

先看 swap 及 iter_swap：

template <class _Tp>
inline void swap(_Tp& __a, _Tp& __b)
{
    _Tp __tmp = __a;
    __a = __b;
    __b = __tmp;
}

template <class _ForwardIter1, class _ForwardIter2, class _Tp>
inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*)
{
    _Tp __tmp = *__a;
    *__a = *__b;
    *__b = __tmp;
}

template <class _ForwardIter1, class _ForwardIter2>
inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)
{
    __iter_swap(__a, __b, __value_type(__a));
}

iter_swap 通过 __value_type 萃取出类型，从而能对指向同一类型的迭代器进行所指向的值交换。

min 和 max 非常简单：

template <class _Tp>
inline const _Tp& min(const _Tp& __a, const _Tp& __b)
{
    __STL_REQUIRES(_Tp, _LessThanComparable);
    return __b < __a ? __b : __a;
}

template <class _Tp>
inline const _Tp& max(const _Tp& __a, const _Tp& __b)
{
    __STL_REQUIRES(_Tp, _LessThanComparable);
    return  __a < __b ? __b : __a;
}

template <class _Tp, class _Compare>
inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
    return __comp(__b, __a) ? __b : __a;
}

template <class _Tp, class _Compare>
inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
    return __comp(__a, __b) ? __b : __a;
}

copy 操作与迭代器类型相关：

template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result, input_iterator_tag, _Distance*)
{
    for ( ; __first != __last; ++__result, ++__first)
        *__result = *__first;
    return __result;
}

template <class _RandomAccessIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_RandomAccessIter __first, _RandomAccessIter __last,
                          _OutputIter __result, random_access_iterator_tag, _Distance*)
{
    for (_Distance __n = __last - __first; __n > 0; --__n)
    {
        *__result = *__first;
        ++__first;
        ++__result;
    }
    return __result;
}
/* 一般模板，_BoolType 为 __false_type 时匹配 */
template <class _InputIter, class _OutputIter, class _BoolType>
struct __copy_dispatch
{
    static _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result)
    {
        typedef typename iterator_traits<_InputIter>::iterator_category _Category;
        typedef typename iterator_traits<_InputIter>::difference_type _Distance;
        return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
    }
};
/* 对有 trivial assignment operator 类型直接调用 memmove */
template <class _Tp>
inline _Tp* __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
{
    memmove(__result, __first, sizeof(_Tp) * (__last - __first));
    return __result + (__last - __first);
}
/* _BoolType 的 __true_type 特化 */
template <class _Tp>
struct __copy_dispatch<_Tp*, _Tp*, __true_type>
{
    static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
    {
        return __copy_trivial(__first, __last, __result);
    }
};
/* _BoolType 的 __true_type 特化 */
template <class _Tp>
struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
{
    static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
    {
        return __copy_trivial(__first, __last, __result);
    }
};

template <class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result)
{
    typedef typename iterator_traits<_InputIter>::value_type _Tp;
    typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _Trivial;
    return __copy_dispatch<_InputIter, _OutputIter, _Trivial>::copy(__first, __last, __result);
}

copy_backward 和 copy_n 的实现手段一样，不再赘述。fill 及其非模板重载版本和 fill_n 如下：

template <class _ForwardIter, class _Tp>
void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
{
    for ( ; __first != __last; ++__first)
        *__first = __value;
}

template <class _OutputIter, class _Size, class _Tp>
_OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
{
    for ( ; __n > 0; --__n, ++__first)
        *__first = __value;
    return __first;
}

// Specialization: for one-byte types we can use memset.
inline void fill(unsigned char* __first, unsigned char* __last,
                 const unsigned char& __c)
{
    unsigned char __tmp = __c;
    memset(__first, __tmp, __last - __first);
}
// Specialization: for one-byte types we can use memset.
inline void fill(char* __first, char* __last, const char& __c)
{
    char __tmp = __c;
    memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}

mismatch 和 equal 如下：

template <class _InputIter1, class _InputIter2>
pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
                                        _InputIter1 __last1,
                                        _InputIter2 __first2)
{
    while (__first1 != __last1 && *__first1 == *__first2)
    {
        ++__first1;
        ++__first2;
    }
    return pair<_InputIter1, _InputIter2>(__first1, __first2);
}

template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
                                        _InputIter1 __last1,
                                        _InputIter2 __first2,
                                        _BinaryPredicate __binary_pred)
{
    while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
    {
        ++__first1;
        ++__first2;
    }
    return pair<_InputIter1, _InputIter2>(__first1, __first2);
}

template <class _InputIter1, class _InputIter2>
inline bool equal(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2)
{
    for ( ; __first1 != __last1; ++__first1, ++__first2)
        if (*__first1 != *__first2)
            return false;
    return true;
}

template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
                  _InputIter2 __first2, _BinaryPredicate __binary_pred)
{
    for ( ; __first1 != __last1; ++__first1, ++__first2)
        if (!__binary_pred(*__first1, *__first2))
            return false;
    return true;
}

lexicographical_compare 根据字典序进行比较：

template <class _InputIter1, class _InputIter2>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2)
{
    for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
    {
        if (*__first1 < *__first2)
            return true;
        if (*__first2 < *__first1)
            return false;
    }
    return __first1 == __last1 && __first2 != __last2;
}

template <class _InputIter1, class _InputIter2, class _Compare>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _Compare __comp)
{
    for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
    {
        if (__comp(*__first1, *__first2))
            return true;
        if (__comp(*__first2, *__first1))
            return false;
    }
    return __first1 == __last1 && __first2 != __last2;
}

inline bool lexicographical_compare(const unsigned char* __first1,
                                    const unsigned char* __last1,
                                    const unsigned char* __first2,
                                    const unsigned char* __last2)
{
    const size_t __len1 = __last1 - __first1;
    const size_t __len2 = __last2 - __first2;
    const int __result = memcmp(__first1, __first2, min(__len1, __len2));
    return __result != 0 ? __result < 0 : __len1 < __len2;
}

inline bool lexicographical_compare(const char* __first1, const char* __last1,
                                    const char* __first2, const char* __last2)
{
    return lexicographical_compare((const unsigned char*) __first1,
                                   (const unsigned char*) __last1,
                                   (const unsigned char*) __first2,
                                   (const unsigned char*) __last2);
}