__random_number 返回 0 到 __n(不包括 __n) 之间的一个随机数。
template <class _Distance>
inline _Distance __random_number(_Distance __n) {
#ifdef __STL_NO_DRAND48
return rand() % __n;
#else
return lrand48() % __n;
#endif
}
random_shuffle 用来将 __first 到 __last 之间的内容随机的混淆和置乱。每次将位置 __i 上的元素和 __first 到 __i(包括 __i) 上的一个随机位置的元素进行对换。
template <class _RandomAccessIter>
inline void random_shuffle(_RandomAccessIter __first,
_RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + __random_number((__i - __first) + 1));
}
random_shuffle 将 __first 到 __last 的元素进行随机置乱，并且用自定义的随机数生成器。
template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
_RandomNumberGenerator& __rand) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + __rand((__i - __first) + 1));
}
函数 random_sampel_n 在 __first 到 __last 中随机挑选 __n 个元素。如果 __n 大于 __first 到 __last 中的所有元素的个数，则选择所有元素，否则只选择 __n 个元素。如果 __random_number 是随机的，__first 到 __last 中的元素个数为 __remaining，则每个元素被选择的概率为 __n / remaining 。
template <class _ForwardIter, class _OutputIter, class _Distance>
template <class _ForwardIter, class _OutputIter, class _Distance>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
_OutputIter __out, const _Distance __n)
{
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
_Distance __remaining = 0;
distance(__first, __last, __remaining);
_Distance __m = min(__n, __remaining);
while (__m > 0) {
if (__random_number(__remaining) < __m) {
*__out = *__first;
++__out;
--__m;
}
--__remaining;
++__first;
}
return __out;
}
函数 __random_sample 也是从 __first 到 __last 中随机选择 __n 个元素，存放在 以 __out 开始的位置。如果 __random_number 是随机的，且 __first 到 __last 之间的元素个数为 __remaining。那么根据概率论的知识，每个元素被选择的概率是 __n / remaining 。
template <class _InputIter, class _RandomAccessIter, class _Distance>
_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
_RandomAccessIter __out,
const _Distance __n)
{
_Distance __m = 0;
_Distance __t = __n;
for ( ; __first != __last && __m < __n; ++__m, ++__first)
__out[__m] = *__first;
while (__first != __last) {
++__t;
_Distance __M = __random_number(__t);
if (__M < __n)
__out[__M] = *__first;
++__first;
}
return __out + __m;
}
函数 __partition 将 __first 到 __last 的元素分为两个部分，第一部分为满足一元判断条件 __pred 的元素，第二部分为不满足一元判断条件的元素。返回值为分割这两部分的分割位置。函数中至始至终 __first(不包括 __first) 之前的元素都是满足判断条件的。
template <class _ForwardIter, class _Predicate>
_ForwardIter __partition(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred,
forward_iterator_tag) {
if (__first == __last) return __first;
while (__pred(*__first))
if (++__first == __last) return __first;
_ForwardIter __next = __first;
while (++__next != __last)
if (__pred(*__next)) {
swap(*__first, *__next);
++__first;
}
return __first;
}
函数 __partition 将 __first 到 __last 之间的内容分割为两部分，前一部分为满足判断条件 __pred 的元素，第二部分为不满足判断条件 __pred 的元素，返回值为分割这两部分的分割值。函数至始至终保证 __first(不包括 __first) 之前的元素都是满足条件的，__last(包括 __last) 之后的元素都是不满足条件的，当 __first == __last，则 __first 被作为分割值返回。
template <class _BidirectionalIter, class _Predicate>
_BidirectionalIter __partition(_BidirectionalIter __first,
_BidirectionalIter __last,
_Predicate __pred,
bidirectional_iterator_tag) {
while (true) {
while (true)
if (__first == __last)
return __first;
else if (__pred(*__first))
++__first;
else
break;
--__last;
while (true)
if (__first == __last)
return __first;
else if (!__pred(*__last))
--__last;
else
break;
iter_swap(__first, __last);
++__first;
}
}
函数 partition 将 __first 到 __last 之间的内容分割为两部分，第一部分为满足判断条件 __pred 的元素，第二部分为不满足判断条件的元素。函数根据迭代器类型的不同调用之前定义的不同的 __partition 函数实现想要的功能。
template <class _ForwardIter, class _Predicate>
inline _ForwardIter partition(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_ForwardIter>::value_type);
return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
}
__inplace_stable_partition 用来将 __first 到 __last 之间长度从 __first 开始为 __len 的部分分割成两部分，第一部分为满足一元判断条件的部分，第二部分为不满足条件的部分，函数递归的进行，先对前半部分和后半部分分别调用 __inplace_stable_partition 函数使得这两部分都被各自被分割为两块，然后将前半部分的后一块和后半部分的前一块进行交换。假设递归函数中得到的分割序列是稳定的，则当前函数得到的序列也是稳定的，又因为初始条件是稳定的，所以函数最终得到的序列是稳定的。
template <class _ForwardIter, class _Predicate, class _Distance>
_ForwardIter __inplace_stable_partition(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred, _Distance __len) {
if (__len == 1)
return __pred(*__first) ? __last : __first;
_ForwardIter __middle = __first;
advance(__middle, __len / 2);
return rotate(__inplace_stable_partition(__first, __middle, __pred,
__len / 2),
__middle,
__inplace_stable_partition(__middle, __last, __pred,
__len - __len / 2));
}
函数 __stable_partition_adaptive 也是将 __first 到 __last 之间的内容分割为两部分，第一部分为满足判断条件的元素组成，第二部分为不满足判断条件的元素组成，并且函数是稳定的。函数中根据 __buffer_size 的大小分两种情况，但需要分割的元素个数小于 __buffer_size 时，则将 __buffer 作为辅助空间，先将满足条件的元素放在以 __first 为首地址的空间内，而将不满足条件的元素放在以 __buffer 为首地址的空间，最后将 __buffer 中暂存的元素复制到 __first 到 __last 之间满足条件的元素后面。
如果 __buffer_size 的大小小于需要分割的元素个数 __len ，则直接使用上面定义的方法实现稳定的分割。
template <class _ForwardIter, class _Pointer, class _Predicate,
class _Distance>
_ForwardIter __stable_partition_adaptive(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred, _Distance __len,
_Pointer __buffer,
_Distance __buffer_size)
{
if (__len <= __buffer_size) {
_ForwardIter __result1 = __first;
_Pointer __result2 = __buffer;
for ( ; __first != __last ; ++__first)
if (__pred(*__first)) {
*__result1 = *__first;
++__result1;
}
else {
*__result2 = *__first;
++__result2;
}
copy(__buffer, __result2, __result1);
return __result1;
}
else {
_ForwardIter __middle = __first;
advance(__middle, __len / 2);
return rotate(__stable_partition_adaptive(
__first, __middle, __pred,
__len / 2, __buffer, __buffer_size),
__middle,
__stable_partition_adaptive(
__middle, __last, __pred,
__len - __len / 2, __buffer, __buffer_size));
}
}
函数 __stable_partition_aux 将 __first 到 __last 之间的内容分割为两部分，第一部分由满足条件 __pred 的元素组成，第二部分有不满足条件的元素组成。函数首先申请一个足够容纳 __first 到 __last 之间的所有元素的临时缓冲区，如果申请成功，则调用 __stable_partition_adaptive 函数实现分割，否则调用 __inplace_stable_partition 实现分割。
template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
inline _ForwardIter
__stable_partition_aux(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred, _Tp*, _Distance*)
{
_Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
if (__buf.size() > 0)
return __stable_partition_adaptive(__first, __last, __pred,
_Distance(__buf.requested_size()),
__buf.begin(), __buf.size());
else
return __inplace_stable_partition(__first, __last, __pred,
_Distance(__buf.requested_size()));
}
函数 stable_partition 将 __first 到 __last 之间的内容分割为上面定义的两部分，具体的功能实现通过调用 __stable_partition_aux 函数来完成。
template <class _ForwardIter, class _Predicate>
inline _ForwardIter stable_partition(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_ForwardIter>::value_type);
if (__first == __last)
return __first;
else
return __stable_partition_aux(__first, __last, __pred,
__VALUE_TYPE(__first),
__DISTANCE_TYPE(__first));
}
函数 __unguarded_partition 将 __first 到 __last 之间的内容分割为两部分，前一部分由小于 __pivot 的元素组成，后一部分由大于或者等于 __pivot 的元素组成。在 while 循环中至始至终保持一个循环不变式，那就是 __first(不包括 __first) 之前的元素都是小于 __pivot 的元素，而 __last(包括 __last 所在的位置) 之后的元素都是大于或者等于 __pivot 的元素。退出循环之后不变式仍然保持
template <class _RandomAccessIter, class _Tp>
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp __pivot)
{
while (true) {
while (*__first < __pivot)
++__first;
--__last;
while (__pivot < *__last)
--__last;
if (!(__first < __last))
return __first;
iter_swap(__first, __last);
++__first;
}
}
函数 unguarded_partition 也是将 __first 到 __last 之间的内容分割为两部分，并且函数根据自定义的比较函数来比较 __first 到 __last 之间的元素的大小。实现的策略和上面定义的函数是一致的。
template <class _RandomAccessIter, class _Tp, class _Compare>
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp __pivot, _Compare __comp)
{
while (true) {
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
iter_swap(__first, __last);
++__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>