// <algorithm> 
template <class BidirectionalIterator,
    class UnaryPredicate>
    BidirectionalIterator stable_partition (
        BidirectionalIterator first,
        BidirectionalIterator last,
        ​UnaryPredicate pred);

稳定划分,两组元素各维持相对顺序,即划分后,各组中元素的先后关系保持不变,而 std::partition 不能保证该点。

该函数等价于:

template<class _BidIt,
    class _Pr,
    class _Diff,
    class _Ty> inline
    _BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
        _Diff _Count, _Temp_iterator<_Ty>& _Tempbuf)
    {    // partition preserving order of equivalents, using _Pred
        if (_Count == 0)
            return (_First);
        else if (_Count == 1)
            return (_Pred(*_First) ? _Last : _First);
        else if (_Count <= _Tempbuf._Maxlen())
        {    // temp buffer big enough, copy right partition out and back
            _BidIt _Next = _First;
            for (_Tempbuf._Init(); _First != _Last; ++_First)
                if (_Pred(*_First))
                    *_Next++ = _Move(*_First);
                else
                    *_Tempbuf++ = _Move(*_First);

            _Move(_Tempbuf._First(), _Tempbuf._Last(), _Next);    // copy back
            return (_Next);
        }
        else
        {    // temp buffer not big enough, divide and conquer
            _BidIt _Mid = _First;
            _STD advance(_Mid, _Count / 2);

            _BidIt _Left = _Stable_partition(_First, _Mid, _Pred,
                _Count / 2, _Tempbuf);    // form L1R1 in left half
            _BidIt _Right = _Stable_partition(_Mid, _Last, _Pred,
                _Count - _Count / 2, _Tempbuf);    // form L2R2 in right half

            _Diff _Count1 = 0;
            _Distance(_Left, _Mid, _Count1);
            _Diff _Count2 = 0;
            _Distance(_Mid, _Right, _Count2);

            return (_Buffered_rotate(_Left, _Mid, _Right,
                _Count1, _Count2, _Tempbuf));    // rotate L1R1L2R2 to L1L2R1R2
        }
    }


  • firstlast

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

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

  • 复杂度

    O(n)n 为 last first.

    数据争用相关

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

    异常安全性相关

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

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