G.5.3  排序和相关操作（3）

（6）is_sorted_until（C++(www.cppentry.com)11）

如果区间[first, last]包含的元素少于两个，函数is_sorted_until将返回last；否则将返回迭代器it，确保区间[first, it]是经过排序的。第一个版本使用<来确定顺序，而第二个版本使用比较对象comp。

（7）nth_element( )

nth_element( )函数找到将[first, last)区间排序后的第n个元素，并将该元素置于第n个位置。第一个版本使用<来确定顺序，而第二个版本使用比较对象comp。

2．二分法搜索

二分法搜索组中的算法假设区间是经过排序的。这些算法只要求正向迭代器，但使用随机迭代器时，效率最高。

（1）lower_bound( )

lower_bound( )函数在排序后的区间[first, last)中找到第一个这样的位置，即将value插入到它前面时不会破坏顺序。它返回一个指向这个位置的迭代器。第一个版本使用<来确定顺序，而第二个版本使用比较对象comp。

（2）upper_bound( )

upper_bound( )函数在排序后的区间[first, last)中找到最后一个这样的位置，即将value插入到它前面时不会破坏顺序。它返回一个指向这个位置的迭代器。第一个版本使用<来确定顺序，而第二个版本使用比较对象comp。

（3）equal_range( )

equal_range( )函数在排序后的区间[first, last)区间中找到这样一个最大的子区间[it1, it2)，即将value插入到该区间的任何位置都不会破坏顺序。该函数返回一个由it1和it2组成的pair。第一个版本使用<来确定顺序，第二个版本使用比较对象comp。

（4）binary_search( )

如果在排序后的区间[first, last]中找到与value等价的值，则binary_search( )函数返回true，否则返回false。第一个版本使用<来确定顺序，而第二个版本使用比较对象comp。

注意：前面说过，使用<进行排序时，如果a<b和b<a都为false，则a和b等价。对于常规数字来说，等价意味着相等；但对于只根据一个成员进行排序的结构来说，情况并非如此。因此，在确保顺序不被破坏的情况下，可插入新值的位置可能不止一个。同样，如果使用比较对象comp进行排序，等价意味着comp(a, b)和comp（b，a）都为false（这是"如果a不小于b，b也不小于a，则a与b等价"的统称）。