stable_partition如何成为一种自适应算法？

Question

stable_partition是c++ STL算法头文件中的一个函数模板。我读到它是一种自适应算法，它的时间复杂度是O(n*logn)或O(n)，取决于某些factors.Can，有人解释了这些因素是什么，时间复杂度如何取决于这些因素。谢谢！

Answer 1

这取决于可用内存的数量。

如果您有足够的内存，一种方法是简单地创建一个足够大的缓冲区，从前面和后面插入相应的元素，并在完成后将其放回原来的位置。这需要O(n)时间。

如果内存不足，此页会提到O(n log )就地方法(可能还有另一种方法)--如果您想要将-重新排列到前面，将+重新排列到后面，您可以反复找到++++---形式的子数组，并(稳定地)将其重新排列到---++++ (这可以通过3次反转完成--反转整个子数组，然后是负部分，然后是正部分)。

物理检查足够的内存可以简单地通过尝试分配内存和检查失败。一种方法是使用new，它可以抛出一个std::bad_alloc，或者返回一个空指针，这取决于所使用的版本，如果它不能分配内存。

Answer 2

有2实现。

1. “慢速”O(n*logn)实现
2. “更快”的O(n)实现

然而，快速实现需要使用大量的内存，这可能是不可用的。因此，stable_partition询问操作系统是否有足够的可用内存，然后在这两种实现之间进行选择。

下面是gcc 4.8.1实现的一个示例，我的一些评论如下：

template<typename _ForwardIterator, typename _Predicate>
    _ForwardIterator
    stable_partition(_ForwardIterator __first, _ForwardIterator __last,
             _Predicate __pred)
    {
       ...
       ...

       /// Try to allocate enough memory for the faster algorithm
      _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);

    if (__buf.size() > 0)  /// If there is enough memory
      return
        std::__stable_partition_adaptive(__first, __last, __pred,
                      _DistanceType(__buf.requested_size()),
                      __buf.begin(),
                      _DistanceType(__buf.size()));
    else  /// If there is not enough memory
      return
        std::__inplace_stable_partition(__first, __pred,
                     _DistanceType(__buf.requested_size()));
    }

这里，std::__stable_partition_adaptive是快速算法，std::__inplace_stable_partition是慢算法。

Answer 3

请参见这里：

这正是谓词的最后一次应用程序，如果内存不足，最多(最后一次)*日志(最后一次)交换，如果有足够的内存，则掉期的线性数。