Geek asks and answers

How is the stable_partition adaptive algorithm?

stable_partition is a function template present in the C ++ STL algorithm header file. I read that this is an adaptive algorithm, and its temporal complexity is O (n * logn) or O (n) depending on some factors. Can someone explain to me what these factors are and how time complexity depends on these factors. Thank!

+3
source share
3 answers

It depends on how much memory is available.

If you have enough memory, one way is to simply create a large enough buffer, insert the appropriate elements in front and back, and put it back in the original. It takes O (n) time.

, O (n log n) ( ) - - + , ++++--- () ---++++ ( 3 - , , ).

, . - new, std::bad_alloc, , , .

+3

2 .

  • "" O(n*logn)
  • "" 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 - .

+5

:

Exactly the last application of the predicate and no more (last-first) * log (last-first) swaps if there is not enough memory or a linear number of swaps if enough memory is available.

+2
source

More articles:


All Articles