STL算法之其它算法_下

random_shuffle

        这个算法将[first,last)的元素次序随机排列。也就说，在N!中可能的元素排列中随机选出一种，此处N为last-first。

        N个元素的序列，其排列方式为N!中，random_shuffle会产生一个均匀分布，因此任何一个排列被选中的几率为1/N!。这很重要（稍后看源码，事实上依赖于随机数是否真随机），因为有不少算法可能会依赖排列的随机性。

        其算法实现过程，基本也是依次对每个元素进行随机的替换，以实现随机排列的功能。代码如下：

// SGI 版本一
template <class RandomAccessItertor>
inline void random_shuffle(RandomAccessItertor first, RandomAccessItertor last) {__random_shuffle(first, last, distance_type(first));
}template <class RandomAccessItertor, class Distance>
void __random_shuffle(RandomAccessItertor first, RandomAccessItertor last, Distance *) {if (first == last) return ;for (RandomAccessItertor I = first; I != last; ++I) #ifdef __STL_NO_DRAND48iter_swap(i, first + Distance(rand() % ((I - first) + 1)));#elseiter_swap(i, first + Distance(lrand48() % ((I - first) + 1)));#endif
} // SGI 版本二
template <class RandomAccessItertor, class RandomNumberGenerator>
void random_shuffle(RandomAccessItertor first, RandomAccessItertor last, RandomNumberGenerator& rand) {if (first == last) return ;for (RandomAccessItertor I = first; I != last; ++I) iter_swap(i, first + rand((I - first) + 1);
} 

从以上代码不难看出random_shuffle第一个版本会使用到内置的rand()函数，我们不难验证如果我们不调用srand函数指定随机数种子，会导致每次调用的结果是相同的序列依次出现。

测试代码如下：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;template<class T>
struct display
{void operator() (const T &x) {cout << x << " ";}
};int main() {int ia[] = {0, 1, 2,3, 4, 5, 6,7};vector<int> iv(ia , ia+8);srand(time(NULL));for (int i = 0; i < 10; ++i) {random_shuffle(iv.begin(), iv.end());for_each(iv.begin(), iv.end(), display<int>());cout << endl;}return 0;
}

如果将上述代码中的srand(time(NULL))删除，会发现每次运行的结果都是一样的。

partial_sort/partial_sort_copy

        本算法接受一个middle迭代器(位于序列[first,last)之内)，然后重新安排[first, last)，使序列中的middle-first个最小元素以递增顺序排序，置于[first,middle)内。其余last-middle个元素安置于[middle,last)中，不保证有任何特定顺序。

        使用sort算法，同样能够保证较小的N个元素以递增顺序置于[first, first+N)之内。选择partial_sort而非sort的唯一理由是效率。是的，如果只是跳出前N个最小元素排序，当然比对整个序列排序快上很多。

        partial_sort有两个版本；区别在于第二个版本会提供反函数comp替代默认的less-than操作符。算法内部采用heap sort来完成任务，简述如下。

        partial_sort的任务是找出middle-first个最小元素，因此，首先界定出区间[first, middle),并利用STL序列式容器之heap（堆）_heap stl-CSDN博客中的make_heap()将它组织为max-heap，然后将[middle,last)中的元素拿来与max-heap中的最大值比较(max-heap的最大值就在第一个元素上，轻松可获得)；如果小于该最大值，就互换位置并重新保持max-heap状态。如此一来，当我们走遍整个[middle,last)时，较大的元素都已经被剥离出[first,middle),这时候再以sort_heap()将[first,middle)做一次排序，即可完成算法的述求。下图描述详情：

        下面是partial_sort的实现细节。

// 版本一
template <class RandoemAccessIterator>
inline void partial_sort(RandoemAccessIterator first, RandoemAccessIterator middle, RandoemAccessIterator last) {__partial_sort(first, middle, last, value_type(first));
}template <class RandoemAccessIterator, class T>
void __partial_sort(RandoemAccessIterator first, RandoemAccessIterator middle, RandoemAccessIterator last, T*) {make_heap(first, middle);for (RandoemAccessIterator I = middle; I < last; ++I) if (*I < *first) __pop_heap(first, middle, I, T(*I), distance_type(first));sort_heap(first, middle);
}

        partial_sort有一个姊妹，就是partial_sort_copy,partial_sort和partial_sort_copy两者行为逻辑完全相同，只不过后者将(last-first)个最小元素排序后的所得结果至于[result_first, result_last)。

sort

        此节内容可阅读STL算法之sort-CSDN博客

equal_range

        算法equal_range是二分查找法的一个版本，试图在已排序的[first,last)中寻找value。它返回一对迭代器i和j，其中i是在不破坏次序的前提下，value可插入的第一个位置(亦即lower_bound),j则是不破坏次序的前提下，value可插入的最后一个位置(亦即upper_bound)。因此，[i,j)内的每个元素都等同于value，而且[i,j)是[first, last)之中符合此性质的最大子区间。

        如果以稍许不同的角度思考equal_range,我们可以把它想成是[first, last)内“与value等同”之所有元素所形成的区间A。由于[first, last)有序，所以我们知道“与value等同”之所有元素一定相邻。于是，算法lower_bound返回区间A的第一个迭代器，算法upper_bound返回区间A的最后一个元素的下一个位置，算法equal_range则是以pair的形式将两者返回。

        即使[first, last)并未含有“与value等同”之任何元素，以上叙述仍然合理。这种情况下“与value等同”之所有元素所形成的，其实是个空区间。在不破坏次序的前提下，只有一个位置可以插入value，而equal_range所返回的pair，其第一和第二元素皆指向该位置。

        本算法有两个版本一个是使用operator<进行比较，第二版本采用仿函数comp进行比较。代码如下：

// 版本一
template<class ForwardIterator, class T>
inline pair< ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value) {return __equal_range(first, last, value, distance_type(first), iterator_category(first));
}// 版本一的random_access_iterator_tag版本
template<class RandomAccessIterator, class T, class Distance>
pair< RandomAccessIterator, RandomAccessIterator >
__equal_range(RandomAccessIterator first, RandomAccessIterator last, const T& value, Distance*, random_access_iterator_tag) {Distance len = last - first;Distance half;RandomAccessIterator middle, left, right;while (len > 0) {half = len >> 1;middle = first + half;if (*middle < value) {first = middle + 1;len = len - half - 1;} else if (value < *middle) {len = half;} else {left = lower_bound(first, middle, value);right = upper_bound(++middle, first + len, value);return pair< RandomAccessIterator, RandomAccessIterator>(left, right);}}// 未找到相等的元素，返回一对迭代器，指向第一个大于value的元素return pair< RandomAccessIterator, RandomAccessIterator>(first, first);
}// 版本一的forward_iterator_tag版本
template<class ForwardIterator, class T, class Distance>
pair< ForwardIterator, ForwardIterator >
__equal_range(ForwardIterator first, ForwardIterator last, const T& value, Distance*, random_access_iterator_tag) {Distance len = last - first;Distance half;ForwardIterator middle, left, right;while (len > 0) {half = len >> 1;middle = first;advance(middle, half);if (*middle < value) {first = middle;++first;len = len - half - 1;} else if (value < *middle) {len = half;} else {left = lower_bound(first, middle, value);advance(first, len);right = upper_bound(++middle, first , value);return pair< ForwardIterator, ForwardIterator>(left, right);}}return pair< ForwardIterator, ForwardIterator>(first, first);
}

inplace_merge(应用于有序区间)

        如果两个连接在一起的序列[first, middle)和[middle, last)都以排序，那么inplace_merge可将他们结合成单一一个序列，并仍保有序性。如果原先两个序列式递增排序，执行结果也会是递增排序，如果原先两个时递减排序，执行结果也是递减排序。

        和merge一样，inplace_merge也是一种稳定操作。每个作为数据来源的子序列中的元素先对次序都不会变动；如果两个子序列有等同的元素，第一个序列的元素会排在第二个序列元素之前。

        implace_merge有两个版本，其差别在于使用operator<还是仿函数comp。以下是代码：

template<class BidrectionalIterator>
inline void inplace_merge(BidrectionalIterator first, BidrectionalIterator middle, BidrectionalIterator last) {if (first == middle || middle == last) return ;__inplace_merge_aux(first, middle, last, value_type(first), distance_type(first));
}// 辅助函数
template<class BidrectionalIterator, class T, class Distance>
inline void __inplace_merge_aux(BidrectionalIterator first, BidrectionalIterator middle, BidrectionalIterator last, T*, Distance*) {Distance len1 = 0;distance(first, middle, len1);Distance len2 = 0;distance(middle, last, len2);// 注意，本算法会使用额外的内存空间(暂时缓冲区)temporary_buffer<BidrectionalIterator, T> buf(first, last);if (buf.begin() == 0) __merge_without_buffer(first, middle, last, len1, lend2);else __merge_adaptive(first, middle, last, len1, len2, buf.begin(), Distance(buf.size()));}

        这个算法如果有额外的内存辅助，效率会好许多。鉴于篇幅，我们主要关注有缓冲区的情况。

// 辅助函数
template <class BidirectionalIterator, class Distance, class Pointer>
void __merge_adaptive(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Distance len1, Distance len2, Pointer buffer, Distance buffer_size) {if (len1 <= len2 && len1 <= buffer_size) {// case 1.缓冲区足够安置序列一Pointer end_buffer = copy(first, middle, buffer);merge(buffer, end_buffer, middle, last, first);} else (len2 <= buffer_size) {// case 2.缓冲区足够安装序列二Pointer end_buffer = copy(middle, last buffer);__merge_backward(first, middle, buffer, end_buffer, last);} else { // case 3. 缓冲区空间不足以安置任何一个序列BidirectionalIterator first_cut = first;BidirectionalIterator second_cut = middle;Distance len11 = 0;Distance len22 = 0;if (len1 > len2) {len11 = len1 / 2;advance(first_cut, len11);second_cut = lower_bound(middle, last, *first_cut);distance(middle, second_cut, len22);} else {len22 = len2 / 2;advance(second_cut, len22);first_cut = upper_bound(first, middle, *second_cut);distance(first, first_cut, len11);}BidirectionalIterator new_middle = __rotate_adaptive(first_cut, middle, second_cut, len1 - len11, len22, buffer, buffer_size);//针对左段，递归调用__merge_adaptive(first_cut, middle, second_cut, len1 - len11, len22, buffer, buffer_size);//针对右段，递归调用__merge_adaptive(new_middle, second_cut, last, second_cut, len1 - len11, len2 - len22, buffer, buffer_size);}
}

        上述辅助函数首先判断缓冲区是否足以容纳inplace_merge所接受的两个序列的任何一个。如果空间充裕,工作逻辑很简单：把两个序列中的某个copy到缓冲区，在使用merge完成余下工作。是的，merge足堪胜任，它的功能就是将两个有序但分离的区间合并，形成一个有序区间，依次只需将merge的结果置放处result指定为inplace_merge所接受序列起始点(迭代器first)即可。其余情况使用递归逐渐减少对缓存的使用以达到合并的目的。更详细内容可在STL算法之merge sort-CSDN博客进行查看。

nth_element

        这个算法会重新排列[first, last)，是迭代器nth所指的元素，与“整个[first, last)完整排列后，同一位置的元素”同值。此外并保证[nth, last)内没有任何一个元素小于(更精确地说是不大于)[first, nth）内的元素，但对于[first, nth)和[nth, last)两个子区间内的元素次序则无任何保证--这一点也是它与partial_sort很大的不同之处。以此观之，neth_element比较近似partition而非sort或partial_sort.

        例如，假设序列{22,30,30,17,33,40,17,23,22,12,20},以下操作

neth(iv.begin(), iv.begin() + 5, iv.end());便是将小于*(iv.being()+5)(本例40)的元素置于该元素之左，其余置于该元素之右，并且不保证维持原有的相对位置。获得的结果为{20,12,22,17,17,22,23,30,30,33,40}。执行完毕后的位置上的元素值22，与整个序列完整排序后{12,17,17,20,22,22,23,30,30,33,40}的个位置上的元素值相同。

        如果以上述结果{20,12,22,17,17,22,23,30,30,33,40}为根据，在执行以下操作：

        nth_element(iv.begin(), iv.begin() + 5, iv.end(), greater<int>());那便是将大于*(iv.being()+5)(本例22)的元素置于该元素值左，其余置于该元素之右，并且不保证位置原有的相对位置，获得的结果为{40,33,3030,23,22,17,17,22,12,20}.

        由于nth_element比partial_sort的保证更少，所以它当然比partial_sort较快。

        nth_element只接受RandomAccessIterator。

        nth_element的做法是，不断地以median-of-3 partition(以首、尾、中央三点中值为枢轴之分割法)将整个序列分割为更小的L，R子序列。如果nth迭代器落于左子序列，就再对左子序列进行分割，否则就再对右子序列进行分割。依次类推，直到分割后的子序列不大于3，便对最后这个待分割的子序列左Insertion Sort，大功告成。

代码如下:

template <class RandomAccessIterator>
inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) {__nth_element(first, nth, last, value_type(first));
}template <class RandomAccessIterator, class T>
void __nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, T*) {while (last - first > 3) {RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first)/2), *(last -1));if (cut < nth) first = cut;else last = cut;}__insertion_sort(first, last);
}

操作示例如下：

其中第一步是通过*first，*(last-1)，及*(first+ (last-first)/2)，三个数的中位数作为，partitiion的pivot，第一轮pivot位22。替换后为第二行的结果；此时得到cut为5，指向40，比nth=4来得大，所有在左半段继续进行partition，选择17进行partition，得到3号位，22为新的cut，更新first后，last-first=2，可以对{22,20}进行排序，排序后，4号位为22，即为我们想要的结果。22即为整个序列最终排好序后的第4个数

参考文档《STL源码剖析》---侯捷