_algo.c

来自「stl的源码」· C语言 代码 · 共 1,735 行 · 第 1/5 页

  while (__last - __first >= __two_step) {
    __result = merge(__first, __first + __step_size,
                     __first + __step_size, __first + __two_step,
                     __result,
                     __comp);
    __first += __two_step;
  }
  __step_size = (min) (_Distance(__last - __first), __step_size);

  merge(__first, __first + __step_size,
        __first + __step_size, __last,
        __result,
        __comp);
}

const int __stl_chunk_size = 7;

template <class _RandomAccessIter, class _Distance, class _Compare>
void __chunk_insertion_sort(_RandomAccessIter __first,
                            _RandomAccessIter __last,
                            _Distance __chunk_size, _Compare __comp) {
  while (__last - __first >= __chunk_size) {
    __insertion_sort(__first, __first + __chunk_size,
                     _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
    __first += __chunk_size;
  }
  __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
}

template <class _RandomAccessIter, class _Pointer, class _Distance,
          class _Compare>
void __merge_sort_with_buffer(_RandomAccessIter __first,
                              _RandomAccessIter __last, _Pointer __buffer,
                              _Distance*, _Compare __comp) {
  _Distance __len = __last - __first;
  _Pointer __buffer_last = __buffer + __len;

  _Distance __step_size = __stl_chunk_size;
  __chunk_insertion_sort(__first, __last, __step_size, __comp);

  while (__step_size < __len) {
    __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
    __step_size *= 2;
    __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
    __step_size *= 2;
  }
}

template <class _BidirectionalIter1, class _BidirectionalIter2,
          class _Distance>
_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
                                      _BidirectionalIter1 __middle,
                                      _BidirectionalIter1 __last,
                                      _Distance __len1, _Distance __len2,
                                      _BidirectionalIter2 __buffer,
                                      _Distance __buffer_size) {
  if (__len1 > __len2 && __len2 <= __buffer_size) {
    _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__middle, __last, __buffer);
    _STLP_STD::copy_backward(__first, __middle, __last);
    return _STLP_STD::copy(__buffer, __buffer_end, __first);
  }
  else if (__len1 <= __buffer_size) {
    _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__first, __middle, __buffer);
    _STLP_STD::copy(__middle, __last, __first);
    return _STLP_STD::copy_backward(__buffer, __buffer_end, __last);
  }
  else
    return _STLP_PRIV __rotate(__first, __middle, __last);
}

template <class _BidirectionalIter, class _Distance, class _Pointer,
          class _Compare>
void __merge_adaptive(_BidirectionalIter __first,
                      _BidirectionalIter __middle,
                      _BidirectionalIter __last,
                      _Distance __len1, _Distance __len2,
                      _Pointer __buffer, _Distance __buffer_size,
                      _Compare __comp) {
  if (__len1 <= __len2 && __len1 <= __buffer_size) {
    _Pointer __buffer_end = _STLP_STD::copy(__first, __middle, __buffer);
    _STLP_STD::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  }
  else if (__len2 <= __buffer_size) {
    _Pointer __buffer_end = _STLP_STD::copy(__middle, __last, __buffer);
    _STLP_PRIV __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
                                __comp);
  }
  else {
    _BidirectionalIter __first_cut = __first;
    _BidirectionalIter __second_cut = __middle;
    _Distance __len11 = 0;
    _Distance __len22 = 0;
    if (__len1 > __len2) {
      __len11 = __len1 / 2;
      _STLP_STD::advance(__first_cut, __len11);
      __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp);
      __len22 += _STLP_STD::distance(__middle, __second_cut);
    }
    else {
      __len22 = __len2 / 2;
      _STLP_STD::advance(__second_cut, __len22);
      __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp);
      __len11 += _STLP_STD::distance(__first, __first_cut);
    }
    _BidirectionalIter __new_middle =
      __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
                        __len22, __buffer, __buffer_size);
    __merge_adaptive(__first, __first_cut, __new_middle, __len11,
                     __len22, __buffer, __buffer_size, __comp);
    __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
                     __len2 - __len22, __buffer, __buffer_size, __comp);
  }
}

template <class _RandomAccessIter, class _Pointer, class _Distance,
          class _Compare>
void __stable_sort_adaptive(_RandomAccessIter __first,
                            _RandomAccessIter __last, _Pointer __buffer,
                            _Distance __buffer_size, _Compare __comp) {
  _Distance __len = (__last - __first + 1) / 2;
  _RandomAccessIter __middle = __first + __len;
  if (__len > __buffer_size) {
    __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
                           __comp);
    __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
                           __comp);
  }
  else {
    __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
                               __comp);
    __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
                               __comp);
  }
  __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
                   _Distance(__last - __middle), __buffer, __buffer_size,
                   __comp);
}

template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
void __stable_sort_aux(_RandomAccessIter __first,
                       _RandomAccessIter __last, _Tp*, _Distance*,
                       _Compare __comp) {
  _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
  if (buf.begin() == 0)
    __inplace_stable_sort(__first, __last, __comp);
  else
    __stable_sort_adaptive(__first, __last, buf.begin(),
                           _Distance(buf.size()),
                           __comp);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _RandomAccessIter>
void stable_sort(_RandomAccessIter __first,
                 _RandomAccessIter __last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_PRIV __stable_sort_aux(__first, __last,
                               _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                               _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
                               _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
}

template <class _RandomAccessIter, class _Compare>
void stable_sort(_RandomAccessIter __first,
                 _RandomAccessIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_PRIV __stable_sort_aux(__first, __last,
                               _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                               _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
                               __comp);
}

// partial_sort, partial_sort_copy, and auxiliary functions.
_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _RandomAccessIter, class _Tp, class _Compare>
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
  make_heap(__first, __middle, __comp);
  for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
    if (__comp(*__i, *__first)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
                 _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
    }
  }
  sort_heap(__first, __middle, __comp);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _RandomAccessIter>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
                  _RandomAccessIter __last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                            _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
}

template <class _RandomAccessIter, class _Compare>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
                  _RandomAccessIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter, class _RandomAccessIter, class _Compare,
          class _Distance, class _Tp>
_RandomAccessIter __partial_sort_copy(_InputIter __first,
                                      _InputIter __last,
                                      _RandomAccessIter __result_first,
                                      _RandomAccessIter __result_last,
                                      _Compare __comp, _Distance*, _Tp*) {
  if (__result_first == __result_last) return __result_last;
  _RandomAccessIter __result_real_last = __result_first;
  while(__first != __last && __result_real_last != __result_last) {
    *__result_real_last = *__first;
    ++__result_real_last;
    ++__first;
  }
  make_heap(__result_first, __result_real_last, __comp);
  while (__first != __last) {
    if (__comp(*__first, *__result_first)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __adjust_heap(__result_first, _Distance(0),
                    _Distance(__result_real_last - __result_first),
                    _Tp(*__first),
                    __comp);
    }
    ++__first;
  }
  sort_heap(__result_first, __result_real_last, __comp);
  return __result_real_last;
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
                  _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
                                        _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
                                        _STLP_VALUE_TYPE(__first, _InputIter));
}

template <class _InputIter, class _RandomAccessIter, class _Compare>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
                  _RandomAccessIter __result_first,
                  _RandomAccessIter __result_last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
  return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
                                        __comp,
                                        _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
                                        _STLP_VALUE_TYPE(__first, _InputIter));
}

// nth_element() and its auxiliary functions.
_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _RandomAccessIter, class _Tp, class _Compare>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                   _RandomAccessIter __last, _Tp*, _Compare __comp) {
  while (__last - __first > 3) {
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1),
                                         __comp)),
                            __comp);
    if (__cut <= __nth)
      __first = __cut;
    else
      __last = __cut;
  }
  __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _RandomAccessIter>
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                 _RandomAccessIter __last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
  _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
                           _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
}

template <class _RandomAccessIter, class _Compare>
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                 _RandomAccessIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
  _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
}

// Binary search (lower_bound, upper_bound, equal_range, binary_search).
_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _ForwardIter, class _Tp,
          class _Compare1, class _Compare2, class _Distance>
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
                           _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
  _Distance __len = _STLP_STD::distance(__first, __last);
  _Distance __half;

  while (__len > 0) {
    __half = __len >> 1;
    _ForwardIter __middle = __first;
    _STLP_STD::advance(__middle, __half);
    if (__comp2(__val, *__middle)) {
      _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __len = __half;
    }
    else {
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
  }
  return __first;
}

template <class _ForwardIter, class _Tp,
          class _Compare1, class _Compare2, class _Distance>
pair<_ForwardIter, _ForwardIter>
__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
              _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
  _Distance __len = _STLP_STD::distance(__first, __last);
  _Distance __half;

  while (__len > 0) {
    __half = __len >> 1;
    _ForwardIter __middle = __first;