// <algorithm> 
// 默认(1)
template <class BidirectionalIterator>
    void inplace_merge (
        BidirectionalIterator first,
        BidirectionalIterator middle,
        BidirectionalIterator last);
// 自定义(2)    
template <class BidirectionalIterator,
    class Compare>
    void inplace_merge (
       BidirectionalIterator first,
       BidirectionalIterator middle,
       BidirectionalIterator last, Compare comp);

合并两个连续的已排过序的子序列。

该函数等价于:

template<class _BidIt,
class _Diff,
class _Ty,
class _Pr> inline
void _Inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred,
    _Diff *, _Ty *)
{    // merge [_First, _Mid) with [_Mid, _Last), using _Pred
    _Diff _Count1 = 0;
    _Distance(_First, _Mid, _Count1);
    _Diff _Count2 = 0;
    _Distance(_Mid, _Last, _Count2);
    _Temp_iterator<_Ty> _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
    _Buffered_merge(_First, _Mid, _Last,
        _Count1, _Count2, _Tempbuf, _Pred);
}
    
template<class _BidIt,
class _Diff,
class _Ty,
class _Pr> inline
void _Buffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
    _Diff _Count1, _Diff _Count2,
        _Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
{    // merge [_First, _Mid) with [_Mid, _Last), using _Pred
    if (_Count1 == 0 || _Count2 == 0)
        ;    // do nothing
    else if (_Count1 + _Count2 == 2)
    {    // order two one-element partitions
        if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
            _STD iter_swap(_First, _Mid);
    }
    else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
    {    // buffer left partition, then merge
        _Move(_First, _Mid, _Tempbuf._Init());
        _Merge(_Tempbuf._First(), _Tempbuf._Last(),
            _Mid, _Last, _First, _Pred);
    }
    else if (_Count2 <= _Tempbuf._Maxlen())
    {    // buffer right partition, then merge
        _Move(_Mid, _Last, _Tempbuf._Init());
        _Merge_backward(_First, _Mid,
            _Tempbuf._First(), _Tempbuf._Last(), _Last, _Pred);
    }
    else
    {    // buffer too small, divide and conquer
        _BidIt _Firstn, _Lastn;
        _Diff _Count1n, _Count2n;
        if (_Count2 < _Count1)
        {    // left larger, cut it in half and partition right to match
            _Count1n = _Count1 / 2, _Count2n = 0;
            _Firstn = _First;
            _STD advance(_Firstn, _Count1n);
            _Lastn = _STD lower_bound(_Mid, _Last, *_Firstn, _Pred);
            _Distance(_Mid, _Lastn, _Count2n);
        }
        else
        {    // right larger, cut it in half and partition left to match
            _Count1n = 0, _Count2n = _Count2 / 2;
            _Lastn = _Mid;
            _STD advance(_Lastn, _Count2n);
            _Firstn = _STD upper_bound(_First, _Mid, *_Lastn, _Pred);
            _Distance(_First, _Firstn, _Count1n);
        }
        _BidIt _Midn = _Buffered_rotate(_Firstn, _Mid, _Lastn,
            _Count1 - _Count1n, _Count2n, _Tempbuf);    // rearrange middle
        _Buffered_merge(_First, _Firstn, _Midn,
            _Count1n, _Count2n, _Tempbuf, _Pred);    // merge each new part
        _Buffered_merge(_Midn, _Lastn, _Last,
            _Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf, _Pred);
    }
}
  • first

    指向第一个已排序子序列中初始位置的双向迭代器(Bidirectional iterators)。它同时也是合并后结果序列的初始位置。

    middle

    指向第二个已排序子序列中初始位置的双向迭代器。

    last

    指向第二个已排序子序列中末尾(End,即最后一个元素之后)位置的双向迭代器。

    comp

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

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

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

  • 无。

  • 如果希望获得与自定义函数谓词、函数对象谓词、对象数组、lambda C++11 表达式、初始化列表 std::initializer_list  C++11 等相关的例子,请同时参照 std::sort

    例 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{
    
        void InplaceMerge_1() {
            // 构造 vector 对象
            CLASSFOO_VECTOR(int, foo, { 1, 3, 5, 7, 9, 10, 0, 2, 4, 6, 8 });
    
            // 注意,由偏移 6 处元素(值为 0)分隔的两个子序列都已经排好序
            // 合并
            std::inplace_merge(
                foo.begin(),
                foo.begin() + 6,
                foo.end()
                );
    
            // 打印 foobar
            std::copy(
                foo.begin(),
                foo.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::InplaceMerge_1();
        return 0;
    }

    0 1 2 3 4 5 6 7 8 9 10 

  • 复杂度

    内存足够大时,时间复杂度为 O(N)N 等值于 std::distance(first1,last1)

    否则,时间复杂度为为 O(N*log(N))

    数据争用相关

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

    异常安全性相关

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

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