• // <algorithm> 
    template <class BidirectionalIterator,
        class UnaryPredicate>
        BidirectionalIterator partition (
            BidirectionalIterator first,
            BidirectionalIterator last,
            UnaryPredicate pred);
    
  • // <algorithm> 
    template <class ForwardIterator,
        class UnaryPredicate>
        ForwardIterator partition (
            ForwardIterator first,
            ForwardIterator last,
            UnaryPredicate pred);
    

将某个范围划分为两组。

该函数等价于:

template<class _BidIt,
    class _Pr> inline
    _BidIt _Partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
        bidirectional_iterator_tag)
    {    // move elements satisfying _Pred to front, bidirectional iterators
        for (; ; ++_First)
        {    // find any out-of-order pair
            for (; _First != _Last && _Pred(*_First); ++_First)
                ;    // skip in-place elements at beginning
            if (_First == _Last)
                break;    // done

            for (; _First != --_Last && !_Pred(*_Last); )
                ;    // skip in-place elements at end
            if (_First == _Last)
                break;    // done

            _STD iter_swap(_First, _Last);    // out of place, swap and loop
        }
        return (_First);
    }
  • firstlast

    C++98

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

    C++11

    分别指向一个序列中初始及末尾位置的正向迭代器(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 Partition_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::Partition_1();
        return 0;
    }

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

  • 复杂度

    O(n)n 为 last first.

    数据争用相关

    范围 [first,last) 中的所有元素都被修改过。

    异常安全性相关

    如果元素交换(Swap)、操作某个迭代器抛异常,该函数才会抛异常。

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