- 1 相关头文件
- 2 find
- 3 find_if
- 4 power
- 5 swap
- 6 rotate
- 6.1 正向迭代器版本
- 6.2 双向迭代器版本
- 6.3 随机迭代器版本
- 7 for_each
STL中实现了一些跟容器相关的一些算法。这里介绍algorithm头文件中一些有意思的算法实现。
1 相关头文件
stl_algo.h stl_algobase.h stl_numeric.h
2 find
algorithm头文件中定义的find函数可适用于所有定义了迭代器的STL容器。但是一些常用的容器如map/unordered_map/set/unordered_set也定义了类内方法find。当需要搜索元素时，我们应当选择类内find方法还是类外find函数呢？
当需要搜索容器内某个元素时，应当优先使用类内find方法, 因为其性能不低于类外函数find。举例来在unordered_map中类内find的时间复杂度为O(1)，而类外函数find的时间复杂度为O(n)。
以下为类外find的实现。首先通过iterator_traits获取迭代器的类型(可参考STL源码分析--iterator)。判断其为一般的input iterator还是random access iterator。然后针对这两种情况对find进行了重载。
- 如果是一般的input iterator：顺序遍历迭代器的区间，返回与目标值相等的第一个迭代器.
- 如果是random access iterator：首先计算区间长度，然后在遍历时对for循环做展开，展开系数为4。这样做的目的有二，一是为了减少循环次数，减少CPU分支预测的开销；二是提高循环内代码并行化执行的可能性，充分利用现代CPU的SIMD提高吞吐量。
template <class _InputIter, class _Tp> inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, typename iterator_traits<_InputIter>::value_type, _Tp); return find(__first, __last, __val, __ITERATOR_CATEGORY(__first)); } template <class _InputIter, class _Tp> inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val, input_iterator_tag) { while (__first != __last && !(*__first == __val)) ++__first; return __first; } template <class _RandomAccessIter, class _Tp> _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last, const _Tp& __val, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIter>::difference_type __trip_count = (__last - __first) >> 2; for ( ; __trip_count > 0 ; --__trip_count) { if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; } switch(__last - __first) { case 3: if (*__first == __val) return __first; ++__first; case 2: if (*__first == __val) return __first; ++__first; case 1: if (*__first == __val) return __first; ++__first; case 0: default: return __last; } }
3 find_if
find_if与find相似，只不过遍历区间时，判断条件变了，判断元素值与目标值相等 --> 判断元素值满足给定的判断条件
template <class _InputIter, class _Predicate> inline _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred, input_iterator_tag) { while (__first != __last && !__pred(*__first)) ++__first; return __first; }
4 power
power用于计算一个数的指数，在实现中使用了快速幂算法，时间复杂度为O(log n)，其中n为power的幂次。
举例说明快速幂算法：
计算: 3^7 = 3^(1+2+4) = (3^1) * (3^2) * (3*4) = 3 * (3^2) * (3^2)^2
很容易看出规律，用伪代码表示：
result = 1 curr = x while (x) { if (x%2) { result *= curr } curr *= curr x >>= 1 } return result
在STL中实现：__opr为函数对象，用它可定义两个_Tp对象的乘法操作，缺省为multiplies<_Tp>，对应的identity_element结果为1，因为任何数字乘1都等于其本身。
template <class _Tp, class _Integer> inline _Tp __power(_Tp __x, _Integer __n) { return __power(__x, __n, multiplies<_Tp>()); } template <class _Tp> inline _Tp identity_element(multiplies<_Tp>) { return _Tp(1); } template <class _Tp, class _Integer, class _MonoidOperation> _Tp __power(_Tp __x, _Integer __n, _MonoidOperation __opr) { if (__n == 0) return identity_element(__opr); else { while ((__n & 1) == 0) { __n >>= 1; __x = __opr(__x, __x); } _Tp __result = __x; __n >>= 1; while (__n != 0) { __x = __opr(__x, __x); if ((__n & 1) != 0) __result = __opr(__result, __x); __n >>= 1; } return __result; } }
5 swap
交换两个同类型对象的值。
注意，当对两个容器进行交换时，应当尽量使用容器类内swap方法，因为algorithm中的swap函数会生成临时变量，执行额外的复制构造函数和析构函数，开销较大。而类内swap方法会尽量避免这些开销。二者之所以会有这种差别是因为类外swap函数无法访问容器的private/protect成员，无法以最小代价实现交换。
template <class _Tp> inline void swap(_Tp& __a, _Tp& __b) { __STL_REQUIRES(_Tp, _Assignable); _Tp __tmp = __a; __a = __b; __b = __tmp; }
以vector为例，其类内swap如下：
void swap(vector<_Tp, _Alloc>& __x) { __STD::swap(_M_start, __x._M_start); __STD::swap(_M_finish, __x._M_finish); __STD::swap(_M_end_of_storage, __x._M_end_of_storage); }
如果想交换两个vector的值，使用algorithm中的swap函数意味着生成一个临时vector，以及由此带来的内存分配释放、容器内元素构造/析构的开销。而使用vector类内swap方法只需要交换三个指针即可，开销相比类外swap可忽略不计。
6 rotate
rotate操作：对于容器区间[first, last), 给定旋转点mid, rotate之后，区间将会变成[mid, last)+[first, mid)。
相信刷过leetcode这道题的同学对roate一定不会陌生：
STL中针对正向迭代器(forward iterator)，双向迭代器(bidirectional iterator)和随机迭代器(random access iterator)的特性重载了rotate算法。虽然实现不同，但是对用户暴露了同样的接口，用户不用care迭代器类型，因为STL中会通过萃取技术做类型推导。因此在性能和通用性得到了很好的均衡。
6.1 正向迭代器版本
假设容器区间左右两个部分为A B, 且len(A) < len(B)。又假设B可拆分成B1 B2 B3 B4, 且len(B1) = len(B2) = len(B3) = len(A), len(B4) < len(A)因此A B = A B1 B2 B3 B4, rotate之后的结果：B A = B1 B2 B3 B4 A
算法描述：第一步：从做到右不断交换相邻的相同长度区间的值A B1 B2 B3 B4 -->
B1 A B2 B3 B4 -->
B1 B2 A B3 B4 -->
B1 B2 B3 A B4
第二步：注意，第一步的最终结果只需要对A B4 进行roate操作, 即可变成B1 B2 B3 B4 A，也就是rotate最终要达到的效果。
- 因为
len(A) > len(B4), 设A = A1 A2, len(A1) = len(B4), 因此A B4 = A1 A2 B4,B4 A = B4 A1 A2。交换A1和B4, 得到B4 A2 A1, 此时问题转化为交换A1和A2
- 不断重复1.中的过程，直到参与交换的两个区间分界线处于右边界位置
算法时间复杂度：n次swap操作，也就是3n次赋值操作
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; }
6.2 双向迭代器版本
原理：因为双向迭代器既可前进，有可后退，因此rotate的实现比正向迭代器简单的多。设A B, roate之后为B A
第一轮：翻转A => reverse(A) B
第二轮 翻转B => reverse(A) reverse(B)
第三轮 翻转整个区间 => reverse(reverse(A) reverse(B)) => B A
时间复杂度：交换n次，也就是赋值3n次
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; } }
6.3 随机迭代器版本
这个实现其实涉及到一个群论中定理：设区间由A B 组成，len(A) = m, len(B) = n, gcd(m, m+n)= s(gcd表示两个整数的最大公约数)
那么分别以0, 1, 2, ..., s-1位置为初始点，通过x(n) = [x(n-1) + m] % (m+n)的规则迭代（终止条件：再次回到初始点），正好可以唯一遍历区间上的所有位置
证明:
- 首先证明以不同初始点迭代时，遍历的点中没有交集，使用反证法：
假设0<= a < s, 0<= b < s, a < b, 以a, b为初始点迭代时，遍历的点中有交集。
=> 存在k1, k2, 使得(a + k1 * m) % (m+n) = (b + k2 * m) % (m+n)
=>(b - a) % (m+n) = [(k2 - k1) * m] % (m+n)
=>b-a = (m * k3) % (m+n)
因为s = gcd(m, m+n)=>b-a = k4 * s, k4 * s < m + n
因为0 < b-a < s=>k4 = 0 => b = a
得到矛盾，因此得证。
- 再证明以
a, 0 <= a <s为起始点迭代，能够恰好遍历(m+n)/s个点 => 如果不考虑终止条件，迭代必然陷入死循环，死循环的周期（单位：迭代次数）为(m+n)/s
=> 对于任意a, 存在0 <= k1 < k2, 使得(a + k1 * m) % (m+n) = (a + k2 * m) % (m+n)
=>(k2 - k1)m = k3 * (m+n)
=>k2 - k1 = k3 * (m+n) / m
=>k2 - k1 = k3 * x / y, 其中x与y互质
=> 为使k2-k1最小，k3 = y = m/s
=>k2 - k1 = m/s * (m+n)/m = (m+n)/s
=> 迭代周期为(m+n)/s
=> 得证 综合第一和第二结论，上述定理得证。
在证明了上述结论之后，再回到rotate话题:
- 首先计算
s = gcd(m, m+n)
- 以[0, s)区间内的元素为起始点，以
x(n) = [x(n-1) + m] % (m+n)的规则计算下一个点，直到回到起始点，这些点组成一个环，对这个环内所有位置的元素逆时针移动
- 最终得到rotate之后的容器区间。因为第2步中所有元素都向逆时针方向移动了m个位置(把区间想象成顺时针方向索引递增的环形)，这正好符合rotate的定义。
时间复杂度：赋值n次，说明在容器可随机访问的情况下，时间复杂度是其他情况的1/3
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; }
7 for_each
对于区间内每个元素执行__f。注意，这里__f既可以是函数对象，也可以是函数指针或std::function类型，__first和__last指定了执行__f的容器区间。
// for_each. Apply a function to every element of a range. template <class _InputIter, class _Function> _Function for_each(_InputIter __first, _InputIter __last, _Function __f) { __STL_REQUIRES(_InputIter, _InputIterator); for ( ; __first != __last; ++__first) __f(*__first); return __f; }
