C++中的partition_point()函数是如何实现长尾排序的？

本文共计978个文字，预计阅读时间需要4分钟。

在先前章节中，我们学习了 partition、stable_partition 和 partition_copy 这三个函数。它们的基本功能是依据特定规则对数据进行分组，即将数据分为满足条件的和不满足条件的两组。

在前面章节中，我们系统学习了 partition()、stable_partition() 和 partition_copy() 这 3 个函数，它们的功能本质上都是根据某个筛选规则对指定范围内的数据进行分组（即符合条件的为一组，不符合条件的为另一组），并且反馈给我们两组数据之间的分界位置。

事实上，有些数据本身就已经是按照某个筛选规则分好组的，例如：

1,2,3,4,5,6,7 <-- 根据规则 i<4，{1,2,3} 为一组，{4,5,6,7} 为另一组 2,4,6,8,1,3,5,7,9 <-- 根据规则 i%2=0，{2,4,6,8} 为一组，{1,3,5,7,9} 为另一组 类似上面这样已经“分好组”的数据，在使用时会有一个问题，即不知道两组数据之间的分界在什么位置。有读者可能想到，再调用一次 partition()、stale_partition() 或者 partition_copy() 不就可以了吗？这种方法确实可行，但对已经分好组的数据再进行一次分组，是没有任何必要的。

实际上，对于如何在已分好组的数据中找到分界位置，C++ 11标准库提供了专门解决此问题的函数，即 partition_point() 函数。