函数 remove_copy 将 __first 到 __last 之间与给定值 __value 不相等的元素移动到 __result 开始的位置上。
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter remove_copy(_InputIter __first, _InputIter __last,
_OutputIter __result, const _Tp& __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)
if (!(*__first == __value)) {
*__result = *__first;
++__result;
}
return __result;
}
函数 remove_copy_if 将 __first 到 __last 之间不满足一元判断条件的元素移动到 __result 开始的位置上。
template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
_OutputIter __result, _Predicate __pred) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
for ( ; __first != __last; ++__first)
if (!__pred(*__first)) {
*__result = *__first;
++__result;
}
return __result;
}
函数 remove 用来将 __first 到 __last 之间为 __value 的元素移除，得以保留的元素都被移动到了函数的返回值所在的位置之前。
template <class _ForwardIter, class _Tp>
_ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
const _Tp& __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);
__first = find(__first, __last, __value);
_ForwardIter __i = __first;
return __first == __last ? __first
: remove_copy(++__i, __last, __first, __value);
}
函数 remove_if 用来将 __first 到 __last 之间满足一元条件的元素移除，使得得以保留的元素都移到函数的返回值所在的位置之前。
template <class _ForwardIter, class _Predicate>
_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_ForwardIter>::value_type);
__first = find_if(__first, __last, __pred);
_ForwardIter __i = __first;
return __first == __last ? __first
: remove_copy_if(++__i, __last, __first, __pred);
}
函数 __unique_copy 将 __first 到 __last 之间的元素复制到 __result 开始的位置上，但如果连续的多个元素相同，则只会复制其中的一个元素。所以只有相同的元素被放置在一起才能保证多个相同的元素只有一个被复制到 __result 开始的位置上。
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result, _Tp*) {
_Tp __value = *__first;
*__result = __value;
while (++__first != __last)
if (!(__value == *__first)) {
__value = *__first;
*++__result = __value;
}
return ++__result;
}
函数 __unique_copy 也是将 __first 到 __last 之间的元素复制到 __result 开始的位置上，但连续的多个相同元素只会复制其中一个。通过调用上面定义的 unique_copy 函数来实现。
template <class _InputIter, class _OutputIter>
inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
output_iterator_tag) {
return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
}
实现的功能和上面定义的 __unique_copy 函数完全一样，和之前的 unique_copy 的函数定义也十分相似，只是这里没有使用中间值 __value。
template <class _InputIter, class _ForwardIter>
_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result, forward_iterator_tag) {
*__result = *__first;
while (++__first != __last)
if (!(*__result == *__first))
*++__result = *__first;
return ++__result;
}
函数 unique_copy 将 __first 到 __last 之间的元素复制到 __result 开始的位置上，函数通过迭代器类型的不同分别调用上面定义的不同 __unique_copy 函数实现想要的唯一复制的功能。
template <class _InputIter, class _OutputIter>
inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
_EqualityComparable);
if (__first == __last) return __result;
return __unique_copy(__first, __last, __result,
__ITERATOR_CATEGORY(__result));
}
函数 unique 剔除 __first 到 __last 之间的重复元素，得以保留的元素都在函数返回值所在位置之前，但程序同样要求 __first 到 __last 之间的重复元素是连续存储的。
template <class _ForwardIter>
_ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
__first = adjacent_find(__first, __last);
return unique_copy(__first, __last, __first);
}
__reverse 函数将 __first 到 __last 中的元素前后对调(第一个和倒数第一个对调，第二个和倒数第二个对调，…依次进行)。因为 __last 是结束标记，函数每次拿 __first 所在位置的元素和 __last - 1 位置的元素对调，然后 __first 向后移动一个位置，__last 向前移动一个位置。如果 __first == __last 说明所有元素对调完毕了，如果 __first == –__last 说明只剩一个元素(__first 所在位置的元素)没有参与对调。这两种情况都没有对调的必要了，所以程序退出。这要求迭代器类型为 bidirectional_iterator，因为要求迭代器内部有自增和自减运算符函数的重载。
template <class _BidirectionalIter>
void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
bidirectional_iterator_tag) {
while (true)
if (__first == __last || __first == --__last)
return;
else
iter_swap(__first++, __last);
}
函数 __reverse 将 __first 到 __last 之间前后位置的元素进行对调。函数限定迭代器类型 random_access_iterator 时才会使用本定义。如果 __first 和 __last 之间元素个数为奇数时，会有一次多余的交换操作(__first == __last - 1时)。
template <class _RandomAccessIter>
void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
random_access_iterator_tag) {
while (__first < __last)
iter_swap(__first++, --__last);
}
//以上 while 循环改成如下形式可以避免那次多余的交换
/* while(__first < --__last)
iter_swap(__first++, __last);*/
函数 reverse 将 __first 到 __last 之间的元素进行前后对调，不同的迭代器类型调用上面不同的 __reverse 函数。
template <class _BidirectionalIter>
inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
__STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
__reverse(__first, __last, __ITERATOR_CATEGORY(__first));
}
reverse_copy 将 __first 到 __last 之间的元素，逆序的拷贝到 __result 开始的区域。
template <class _BidirectionalIter, class _OutputIter>
_OutputIter reverse_copy(_BidirectionalIter __first,
_BidirectionalIter __last,
_OutputIter __result) {
__STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
while (__first != __last) {
--__last;
*__result = *__last;
++__result;
}
return __result;
}
__gcd 函数求 __m 和 __n 的最大公约数。
template <class _EuclideanRingElement>
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
_EuclideanRingElement __n)
{
while (__n != 0) {
_EuclideanRingElement __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
函数 __rotate 将 __middle 到 __last 之间的元素移动到 __first 到 __middle 之间的元素之前，将原来 __first 到 __middle 之间的元素移动到后面去。
函数第一个 while 循环用来获取新的中间位置作为返回值，并将原来 __middle 到 __last 之间的内容移动到最前面，这部分内容移动之后不需要再作更改，此时 __first 正好处在这部分内容的结束位置，因此将 __first 赋值给 __new_middle 作为返回值。
具体分析需要分两种情况进行考虑。第一种是 __first 到 __middle 之间的内容长于 __middle 到 __last 之间的内容，这种情况下 __middle 的值不会改变，第一个 while 循环之后，还是需要将 __first 到 __middle 之间的内容移动到 __middle 到 __last 后面，将 __middle 之后的内容移动到 __first 到 __middle 前面。相当于将原问题又变成了一个规模更小的子问题。
第二种是原问题中 __first 到 __middle 的内容要短于 __middle 到 __last 之间的内容，此时在第一个 while 循环中 middle 的值会被改变，而且可能发生多次改变。此时可以将 __middle 到 __last 之间的内容分成很多段，除最后一段之外，每一段的的长度都和 __first 到 __middle 之间的长度相同(最后一段可能会小于 __first 到 middle 之间的长度，因为不一定 __middle 到 __last 之间的长度刚好就是 __first 到 middle 的长度的整数倍)。
每复制 __middle 到 __last 之间的一段，条件 __first == __middle 就会被满足，此时就需要更改 __middle 的值。如果 __middle 到 __last 中所有和 __first 到 __middle 长度相等的段都被复制到了 __first 到 __middle 的前面，此时 __first 到 __middle 之间包含的就是原问题中 __first 到 __middle 之间的内容，而 __middle 到 __last 之间的内容就是原问题中 __middle 到 __last 之间的内容被分段后的最后一段，而最后一段的长度小于 __first 到 __middle 之间的长度。此时需要将最后一段移到 __first 到 __middle 前面，则又进入了第一种情况。
当找到 __new_middle 之后，原问题只是将 __middle 到 __last 之间的内容移动到了最前面。由于上面的两种情况中最终都会归结到第一种情况，留下一个和原问题相同的规模更小的子问题。仍是要将 __first 到 __middle 之间的内容和 __middle 到 __last 之间的内容进行交换。只是现在子问题中 __first 到 __last 的长度是原问题中 __first 到 __middle 的长度。
对于第二个 while 循环也是采用同样的策略，不断的将当前问题变成规模更小的子问题，每次遇到 __first == __middle 或者 __first2 == __last 都能将原问题的规模缩减到一个长度为 __first 到 __middle 的子问题。将 while 循环的判断条件改成 while (__middle != __last) 或许更形象，虽然 while (__first2 != __last) 效果也是一样的。
template <class _ForwardIter, class _Distance>
_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;
do {
swap(*__first++, *__first2++);
if (__first == __middle)
__middle = __first2;
} while (__first2 != __last);
_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;
}
函数 __rotate 是将 __middle 到 __last 的部分和 __first 到 __middle 的部分进行对换。函数首先将 __first 到 __middle 和 __middle 到 __last 之间的元素倒序。然后将从 __first 开始向后移动和从 __last 开始向前移动，将对应位置的元素进行对调，直到 __first == __middle 或者 __last == __middle 。如果 __first == __middle ，则将 __middle 到 __last 之间的元素再逆序，否则将 __first 到 __middle 之间的元素逆序。
template <class _BidirectionalIter, class _Distance>
_BidirectionalIter __rotate(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last,
_Distance*,
bidirectional_iterator_tag) {
__STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
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) {
__reverse(__middle, __last, bidirectional_iterator_tag());
return __last;
}
else {
__reverse(__first, __middle, bidirectional_iterator_tag());
return __first;
}
}
函数 __rotate 也是将 __first 到 __middle 的部分和 __middle 到 __last 的部分进行对换。函数首先计算出 __first 到 __last 之间的元素个数 __n ，然后计算出 __first 到 __middle 之间的元素个数 __k 和 __middle 到 __last 之间的元素个数 __l。如果 __k == l ，则直接调用 swap_range 将从 __first 开始和从 __middle 开始的对应位置的元素进行交换。否则计算 __n 和 __k 的最大公约数 __d( __d 也是 __n, __k, __l 的最大公约数)。
则 __first 到 __middle 和 __middle 到 __last 之间的内容都可以划分为长度为 __d 的若干段。如果将 __first 到 __last 看成是首尾相连的段，则交换 __first 到 __middle 和 __middle 到 __last 之间的内容可以看成是将 __first 到 __last 的内容整体向前移动 __k 个位置或者是整体向后移动 __l 个位置(类似于位运算中的循环移位)。
如果 __k < __l ，则将交换 __first 到 __middle 和 __middle 到 __last 之间的内容看成是将 __first 到 __last 中的内容整体的循环左移 __k 个位置。如果将 __first 所在的位置看成是位置 0，将 __last 所在的位置看成是位置 __n。函数分两个循环来完成内容的交换，外层循环每循环一次会对模 __d 余 i 的位置上的元素进行交换，内层循环每次移动 __k 个位置，移动 __l / __d 次，则总共移动了 __l * __k / __d 个位置。那么从 __first 开始就应该有 __k / __d - 1 次出现 __p > __first + __l 的情况，而每次出现这种情况就会多移动一次，并且移动的位置也是 __k(当 __p > __first + __l 时向后移动 __k 个位置和向前移动 __l 个位置是等价的)。因此总共移动的次数为 __l / __d + __k / __d - 1 即为 __n / __d - 1 。因为 gcd(__n, __k) == __d ，每次移动 __k 个位置，移动 __n / __d 次以内，每次移动的位置都是不同的(反证法)。而外循环的最后面还有一次额外的移动，因此一次外循环可以将 __n / __d 个元素整体循环左移 __k 个位置。内外循环配合在一起可以使全部的 __n 个元素循环的左移 __k 个位置。
如果 __l < __k(等于的情况最前面已经考虑了) 则将交换 __first 到 __middle 和 __middle 到 __last 之间的内容看成是将 __first 到 __last 之间的内容整体的循环右移了 __l 个位置。每次左移 __l 个位置，一共移动 __k / __d - 1 次，那么移动的距离为 __k * __l / __d - __l 个位置，一共有 l / d 次出现 __p < __last - k 的情况，因此移动的总次数为 __k / __d - 1 + __l / __d ，即为 __n / __d - 1。加上最尾部的一次移动，一共循环右移 __n / __d 个元素。内外循环一起使得全部 __n 个元素被循环右移 __l 个单位。
template <class _RandomAccessIter, class _Distance, class _Tp>
_RandomAccessIter __rotate(_RandomAccessIter __first,
_RandomAccessIter __middle,
_RandomAccessIter __last,
_Distance *, _Tp *) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
_Distance __n = __last - __first;
_Distance __k = __middle - __first;
_Distance __l = __n - __k;
_RandomAccessIter __result = __first + (__last - __middle);
if (__k == 0)
return __last;
else if (__k == __l) {
swap_ranges(__first, __middle, __middle);
return __result;
}
_Distance __d = __gcd(__n, __k);
for (_Distance __i = 0; __i < __d; __i++) {
_Tp __tmp = *__first;
_RandomAccessIter __p = __first;
if (__k < __l) {
for (_Distance __j = 0; __j < __l/__d; __j++) {
if (__p > __first + __l) {
*__p = *(__p - __l);
__p -= __l;
}
*__p = *(__p + __k);
__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;
}
return __result;
}
函数 rotate 交换 first 到 __middle 和 __middle 到 __last 之间的元素。使得 __middle 到 __last 之间的元素位于 first 到 __middle 之间的元素前面，而 __first 到 __middle 之间的元素接到 __middle 到 __last 之间的元素后面。 根据迭代器类型的不同调用上面定义的不同的 __rotate 函数来实现。
template <class _ForwardIter>
inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
_ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
return __rotate(__first, __middle, __last,
__DISTANCE_TYPE(__first),
__ITERATOR_CATEGORY(__first));
}
rotate_copy 函数将 __first 到 __last 之间的内容复制到 __result 开始的区域，但要先复制 __middle 到 __last 之间的内容，然后再复制 __first 到 __middle 之间的内容。
template <class _ForwardIter, class _OutputIter>
_OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
_ForwardIter __last, _OutputIter __result) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
return copy(__first, __middle, copy(__middle, __last, __result));
}
STL 的 算法 (algo) 分析（一）</br> STL 的 算法 (algo) 分析（二）</br> STL 的 算法 (algo) 分析（三）</br> STL 的 算法 (algo) 分析（四）</br> STL 的 算法 (algo) 分析（五）</br> STL 的 算法 (algo) 分析（六）</br> STL 的 算法 (algo) 分析（七）</br> STL 的 算法 (algo) 分析（八）</br>