函数 search 用来查找 __first2 到 __last2 包含的内容是否出现在了 __first1 到 __last1 包含的内容之间，如果在，则返回第一次出现的位置，否则返回 __last1。
函数首先判断是否 __first1 等于 __last1 或者 __first2 等于 __last2。如果 __first1 == __last1 ，则 __first2 到 __last2 之间的内容肯定没有出现在 __first1 到 __last1 之间，返回 __last1(此时 __last1 即为 __first1)，如果 __first2 == __last2 ，则空串肯定是 __first1 到 __last1 的一部分，返回 __first1 即可。所以两种情况都返回 __first1。
如果 __first1 != __last1 且 __first2 != __last2，则令 tmp 指向 __first2 之后的下一个元素。如果 tmp == __last2 则认为 __first2 和 __last2 之间只有一个元素，直接调用前面定义的 find 函数搜索该元素是否在 __first1 到 __last1 之间即可。
如果 __first2 到 __last2 之间的元素个数大于 1(即 tmp != __last2)，则首先查找 __first2 所在位置的元素在 __first1 和 __last1 中出现的位置，如果不存在，则说明 __first2 到 __last2 之间包含的内容不可能出现在 __first1 到 __last1 之间。
否则令 __first1 暂存 __first2 所在位置的元素在 __first1 到 __last1 之间第一次出现的位置。因为 __first2 所在位置的元素已经出现在了 __first1 到 __last1 之间，并且将其第一次出现的位置暂存在了 __first1 中，因此接下来逐个比较 __first2 到 __last2 中剩余的元素是否在 __first1 到 __last1 中的对应位置出现了。
如果 __first2 到 __last2 中的剩余元素都在 __first1 到 __last1 中出现了，则返回 __first1 (已暂存了 __first2 第一次在 __first1 到 __last1 中出现的位置) 。
否则如果遇到 __last1 ，则因为 __first1 到 __last1 中的元素不够匹配了，则返回 __last1 。否则如果在没有碰到 __last1 是匹配出现错误，则从 __first1 的下一个位置重新开始之前的定义的一系列查找和匹配过程，如果 __first1 到 __last1 的位置仍然没找到匹配 __first2 到 __last2 之间的元素的位置，则返回 __last1 。
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2)
{
__STL_REQUIRES(_ForwardIter1, _ForwardIterator);
__STL_REQUIRES(_ForwardIter2, _ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_ForwardIter1>::value_type,
typename iterator_traits<_ForwardIter2>::value_type);
// 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)
return find(__first1, __last1, *__first2);
// General case.
_ForwardIter2 __p1, __p;
__p1 = __first2; ++__p1;
_ForwardIter1 __current = __first1;
while (__first1 != __last1) {
__first1 = find(__first1, __last1, *__first2);
if (__first1 == __last1)
return __last1;
__p = __p1;
__current = __first1;
if (++__current == __last1)
return __last1;
while (*__current == *__p) {
if (++__p == __last2)
return __first1;
if (++__current == __last1)
return __last1;
}
++__first1;
}
return __first1;
}
search 函数查找 __first2 到 __last2 之间包含的内容是否出现在了 __first1 到 __last1 包含的内容之间，这里认为如果 __first2 到 __last2 之间的某个元素和 __first1 到 __last1 之间的某个元素满足二元判断条件 __predicate ，则认为 __first2 到 __last2 之间的该元素出现在了 __first1 到 __last1 之间对应元素所在的位置。函数具体的实现和上面定义的 search 函数十分相似，只是上面调用 find 函数的地方由于当前函数没有合适的可供调用的 find 函数，所以用 while 循环进行改写以替代 find 函数所要实现的功能，其他的定义和上面定义的 search 函数一致，不再赘述。
template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
_BinaryPred __predicate)
{
__STL_REQUIRES(_ForwardIter1, _ForwardIterator);
__STL_REQUIRES(_ForwardIter2, _ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool,
typename iterator_traits<_ForwardIter1>::value_type,
typename iterator_traits<_ForwardIter2>::value_type);
// 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) {
while (__first1 != __last1 && !__predicate(*__first1, *__first2))
++__first1;
return __first1;
}
// General case.
_ForwardIter2 __p1, __p;
__p1 = __first2; ++__p1;
_ForwardIter1 __current = __first1;
while (__first1 != __last1) {
while (__first1 != __last1) {
if (__predicate(*__first1, *__first2))
break;
++__first1;
}
while (__first1 != __last1 && !__predicate(*__first1, *__first2))
++__first1;
if (__first1 == __last1)
return __last1;
__p = __p1;
__current = __first1;
if (++__current == __last1) return __last1;
while (__predicate(*__current, *__p)) {
if (++__p == __last2)
return __first1;
if (++__current == __last1)
return __last1;
}
++__first1;
}
return __first1;
}
函数 search_n 查找是否存在给定值 __val 在 __first 到 __last 之间连续出现了 __count 次。如果存在，则返回第一次出现的位置，否则返回 __last。
template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp, _EqualityComparable);
if (__count <= 0)
return __first;
else {
__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
__first = find(__i, __last, __val);
}
return __last;
}
}
函数 search_n 也是查找给定值 __val 是否在 __first 到 __last 之间连续出现了 __count 次。如果出现了，则返回第一次出现的位置，否则返回 __last 。这里如果 __val 和 __first 到 __last 之间某个位置上的元素满足二元判断条件 __predicate，则认为 __val 出现在了该位置上。
template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val,
_BinaryPred __binary_pred) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool,
typename iterator_traits<_ForwardIter>::value_type, _Tp);
if (__count <= 0)
return __first;
else {
while (__first != __last) {
if (__binary_pred(*__first, __val))
break;
++__first;
}
while (__first != __last) {
_Integer __n = __count - 1;
_ForwardIter __i = __first;
++__i;
while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
++__i;
--__n;
}
if (__n == 0)
return __first;
else {
while (__i != __last) {
if (__binary_pred(*__i, __val))
break;
++__i;
}
__first = __i;
}
}
return __last;
}
}
函数 swap_ranges 将从 __first1开始 到 __last1 结束的元素与将从 __first2 开始的对应位置上的元素相互交换。iter_swap 用来交换对应位置的元素内容。
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2) {
__STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator);
__STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator);
__STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type,
typename iterator_traits<_ForwardIter2>::value_type);
__STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type,
typename iterator_traits<_ForwardIter1>::value_type);
for ( ; __first1 != __last1; ++__first1, ++__first2)
iter_swap(__first1, __first2);
return __first2;
}
函数 transform 用来对 __first 到 __last 之间的元素应用一元操作 __opr 。并将运算结果存储在从 __result 开始的对应位置上。
template <class _InputIter, class _OutputIter, class _UnaryOperation>
_OutputIter transform(_InputIter __first, _InputIter __last,
_OutputIter __result, _UnaryOperation __opr) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __first != __last; ++__first, ++__result)
*__result = __opr(*__first);
return __result;
}
函数 transform 用来将从 __first1 开始到 __last1 结束的元素与从 __first2 开始的对应位置上的元素应用二元操作 __binary_op 。并将运算结果存储在从 __result 开始的位置上。
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _BinaryOperation>
_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _OutputIter __result,
_BinaryOperation __binary_op) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
*__result = __binary_op(*__first1, *__first2);
return __result;
}
函数 replace 将 __first 到 __last 之间的内容中的 __old_value 全部替换成 __new_value 。
template <class _ForwardIter, class _Tp>
void replace(_ForwardIter __first, _ForwardIter __last,
const _Tp& __old_value, const _Tp& __new_value) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_ForwardIter>::value_type, _Tp);
__STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
for ( ; __first != __last; ++__first)
if (*__first == __old_value)
*__first = __new_value;
}
函数 replace 将 __first 到 __last 之间满足一元判断条件 __pred 的元素替换为 __new_value 。
template <class _ForwardIter, class _Predicate, class _Tp>
void replace_if(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred, const _Tp& __new_value) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_ForwardIter>::value_type);
for ( ; __first != __last; ++__first)
if (__pred(*__first))
*__first = __new_value;
}
函数 replace_copy 将 __first 到 __last 之间的内容复制到从 __result 开始的位置上，但将其中为 __old_value 的元素用 __new_value 替换。
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter replace_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
const _Tp& __old_value, const _Tp& __new_value) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_InputIter>::value_type, _Tp);
for ( ; __first != __last; ++__first, ++__result)
*__result = *__first == __old_value ? __new_value : *__first;
return __result;
}
函数 replace_copy_if 将 __first 到 __last 之间的内容复制到 __result 开始的位置上，但将其中满足一元判断条件的元素用 __new_value 代替。
template <class _InputIter, class _OutputIter, class _Predicate, class _Tp>
_OutputIter replace_copy_if(_InputIter __first, _InputIter __last,
_OutputIter __result,
_Predicate __pred, const _Tp& __new_value) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
for ( ; __first != __last; ++__first, ++__result)
*__result = __pred(*__first) ? __new_value : *__first;
return __result;
}
函数 generate 为 __first 到 __last 的位置调用生成函数 gen() 生成元素 。
template <class _ForwardIter, class _Generator>
void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_GENERATOR_CHECK(_Generator,
typename iterator_traits<_ForwardIter>::value_type);
for ( ; __first != __last; ++__first)
*__first = __gen();
}
函数 generate_n 为从 __first 开始的位置上调用生成函数 gen() 生成 __n 个元素。
template <class _OutputIter, class _Size, class _Generator>
_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __n > 0; --__n, ++__first)
*__first = __gen();
return __first;
}
STL 的 算法 (algo) 分析（一）</br> STL 的 算法 (algo) 分析（二）</br> STL 的 算法 (algo) 分析（三）</br> STL 的 算法 (algo) 分析（四）</br> STL 的 算法 (algo) 分析（五）</br> STL 的 算法 (algo) 分析（六）</br> STL 的 算法 (algo) 分析（七）</br> STL 的 算法 (algo) 分析（八）</br>