C++11

// <algorithm> 
template <class InputIterator, class UnaryPredicate>
    bool is_partitioned (
        InputIterator first,
        InputIterator last,
        ​UnaryPredicate pred);

检测某个范围是否按指定谓词(Predicate)划分过。

该函数等价于:

template<class _InIt,
    class _Pr> inline
    bool _Is_partitioned(_InIt _First, _InIt _Last, _Pr _Pred)
    {    // test if [_First, _Last) partitioned by _Pred
        for (; _First != _Last; ++_First)
            if (!_Pred(*_First))
                break;    // skip true partition
        for (; _First != _Last; ++_First)
            if (_Pred(*_First))
                return (false);    // found out of place element
        return (true);
    }
  • firstlast

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

    pred

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

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

    该函数不能修改其参数。

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

  • 如果范围  [first,last) 中的所有元素分为两部分,前半部分使 pred 返回 true,后半部分使 pred 返回 false,则当前函数返回 true,否则返回  false

    如果当前范围为空,则返回 true

  • 例 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 IsPartitioned_1() {
            CLASSFOO_VECTOR(int, BigVector1, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
            // 等价比较
            bool b = std::is_partitioned(
                std::begin(BigVector1),
                std::end(BigVector1),
                IsNegative
                );
            std::cout << std::boolalpha << b << std::endl;
    
            std::partition(
                std::begin(BigVector1),
                std::end(BigVector1),
                IsNegative
                );
    
            b = std::is_partitioned(
                std::begin(BigVector1),
                std::end(BigVector1),
                IsNegative
                );
            std::cout << std::boolalpha << b << std::endl;
            // 输出反转结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::IsPartitioned_1();
        return 0;
    }

    false
    true
    -1 -7 -5 7 29 0 7 7 23 1 8 

  • 复杂度

    最多执行 last first 次 pred,一旦发现未匹配就返回。

    数据争用相关

    访问在范围 [first,last) 中的部份(或所有)元素,但最多访问一次。

    异常安全性相关

    如果 pred 或操作某个迭代器抛异常,该函数才会抛异常。

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