C++11

// <algorithm> 
template <class InputIterator,
    class OutputIterator1,
    class OutputIterator2,
    class UnaryPredicate pred>
    pair<OutputIterator1,OutputIterator2>
    partition_copy (
        InputIterator first,
        InputIterator last,
        OutputIterator1 result_true,
        OutputIterator2 result_false,
        UnaryPredicate pred);

拷贝指定范围的划分结果。

该函数等价于:

template<class _InIt,
class _OutIt1,
class _OutIt2,
class _Pr> inline
pair<_OutIt1, _OutIt2>
    _Partition_copy(_InIt _First, _InIt _Last,
        _OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred)
{    // copy true partition *_Dest1++, false to *_Dest2++
    for (; _First != _Last; ++_First)
        if (_Pred(*_First))
            *_Dest1++ = *_First;
        else
            *_Dest2++ = *_First;
    return (pair<_OutIt1, _OutIt2>( _Dest1, _Dest2));
}
  • firstlast

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

    result_true

    指向第一个结果序列初始位置的输出迭代器(Output iterators),该序列中的所有元素使 pred 返回 true

    该序列与源序列及另一个结果序列不能有重合。

    result_false

    指向第二个结果序列初始位置的输出迭代器(Output iterators),该序列中的所有元素使 pred 返回 false

    该序列与源序列及另一个结果序列不能有重合。

    pred

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

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

    该函数不能修改其参数。

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

  • 返回一个 std::pair 对象,该对象的成员分别为指向所生成序列 result_trueresult_false 末尾位置的迭代器。

  • 例 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 PartitionCopy_1() {
            CLASSFOO_VECTOR(int, BigVector1, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
            std::vector<int> Part1(BigVector1.size());
            std::vector<int> Part2(BigVector1.size());
    
            std::pair<
                std::vector<int>::iterator,
                std::vector<int>::iterator
            > p = std::partition_copy(
                std::begin(BigVector1),
                std::end(BigVector1),
                Part1.begin(),
                Part2.begin(),
                IsNegative
                );
    
            // 输出两个分组
            std::copy(
                Part1.begin(),
                p.first,
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
            std::copy(
                Part2.begin(),
                p.second,
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::PartitionCopy_1();
        return 0;
    }

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

  • 复杂度

    O(n)n 为 last first.

    数据争用相关

    访问在范围 [first,last) 中的所有元素,且每个元素确定只被访问一次。

    修改在 result_true 及返回值中 first 成员所共同表示的范围中的所有元素,且每个元素确定只被修改一次。

    修改在 result_false 及返回值second 成员所共同表示的范围中的所有元素,且每个元素确定只被修改一次。

    异常安全性相关

    如果谓词 pred、元素赋值、操作某个迭代器抛异常,该函数才会抛异常。

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