C++11

// <algorithm> 
template <class ForwardIterator,
    class UnaryPredicate>
    ForwardIterator partition_point (
        ForwardIterator first,
        ForwardIterator last,
        ​UnaryPredicate pred);

返回被划分范围的划分点。

该函数等价于:

template<class _FwdIt,
class _Diff,
class _Pr> inline
_FwdIt _Partition_point(_FwdIt _First, _FwdIt _Last, _Pr _Pred, _Diff *)
{    // find beginning of false partition in [_First, _Last)
    _Diff _Count = 0;
    _Distance(_First, _Last, _Count);
    while (0 < _Count)
    {    // divide and conquer, find half that contains answer
        _Diff _Count2 = _Count / 2;
        _FwdIt _Mid = _First;
        _STD advance(_Mid, _Count2);

        if (_Pred(*_Mid))
            {    // try top half
            _First = ++_Mid;
            _Count -= _Count2 + 1;
            }
        else
            _Count = _Count2;
    }
    return (_First);
}
  • firstlast

    分别指向一个已划分(Partitioned)序列中初始及末尾位置的正向迭代器(Forward iterator)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    pred

    一元谓词(Unary)函数,以范围中的一个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明指定元素是否满足当前函数所检测的条件。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 返回指向第二组(所有使 pred 返回 false 的元素)中第一个元素的迭代器。

    如果该组为空,则返回 last

  • 例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
        bool IsNegative(int n) {
            return n < 0;
        }
        void PartitionPoint_1() {
            CLASSFOO_VECTOR(int, BigVector1, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
    
            std::partition(
                std::begin(BigVector1),
                std::end(BigVector1),
                IsNegative
                );
    
            std::vector<int>::iterator p = std::partition_point(
                std::begin(BigVector1),
                std::end(BigVector1),
                IsNegative
                );
    
            // 使用划分点输出第一组
            std::copy(
                BigVector1.begin(),
                p,
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::PartitionPoint_1();
        return 0;
    }

    -1 -7 -5 

  • 复杂度

    如果迭代器可随机访问,时间复杂度为 O(log2(n))n 为 last first.

    否则,时间复杂度为 O(n)n 为 last first.

    数据争用相关

    访问范围 [first,last) 中的部分元素。

    异常安全性相关

    如果元素比较(Compare)或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)