_algo.c

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

    _STLP_STD::advance(__middle, __half);
    if (__comp1(*__middle, __val)) {
      _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
    else if (__comp2(__val, *__middle)) {
      _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __len = __half;
    }
    else {
      _ForwardIter __left = _STLP_PRIV __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
      //Small optim: If lower_bound haven't found an equivalent value
      //there is no need to call upper_bound.
      if (__comp1(*__left, __val)) {
        _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
        return pair<_ForwardIter, _ForwardIter>(__left, __left);
      }
      _STLP_STD::advance(__first, __len);
      _ForwardIter __right = _STLP_PRIV __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
      return pair<_ForwardIter, _ForwardIter>(__left, __right);
    }
  }
  return pair<_ForwardIter, _ForwardIter>(__first, __first);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
                  _InputIter2 __first2, _InputIter2 __last2,
                  _OutputIter __result) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2) {
    if (*__first2 < *__first1) {
      *__result = *__first2;
      ++__first2;
    }
    else {
      *__result = *__first1;
      ++__first1;
    }
    ++__result;
  }
  return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
                  _InputIter2 __first2, _InputIter2 __last2,
                  _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2) {
    if (__comp(*__first2, *__first1)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      *__result = *__first2;
      ++__first2;
    }
    else {
      *__result = *__first1;
      ++__first1;
    }
    ++__result;
  }
  return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _BidirectionalIter, class _Distance, class _Compare>
void __merge_without_buffer(_BidirectionalIter __first,
                            _BidirectionalIter __middle,
                            _BidirectionalIter __last,
                            _Distance __len1, _Distance __len2,
                            _Compare __comp) {
  if (__len1 == 0 || __len2 == 0)
    return;
  if (__len1 + __len2 == 2) {
    if (__comp(*__middle, *__first)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      iter_swap(__first, __middle);
    }
    return;
  }
  _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
    = _STLP_PRIV __rotate(__first_cut, __middle, __second_cut);
  __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
                         __comp);
  __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
                         __len2 - __len22, __comp);
}

template <class _BidirectionalIter1, class _BidirectionalIter2,
          class _BidirectionalIter3, class _Compare>
_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
                                     _BidirectionalIter1 __last1,
                                     _BidirectionalIter2 __first2,
                                     _BidirectionalIter2 __last2,
                                     _BidirectionalIter3 __result,
                                     _Compare __comp) {
  if (__first1 == __last1)
    return copy_backward(__first2, __last2, __result);
  if (__first2 == __last2)
    return copy_backward(__first1, __last1, __result);
  --__last1;
  --__last2;
  for (;;) {
    if (__comp(*__last2, *__last1)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      *--__result = *__last1;
      if (__first1 == __last1)
        return copy_backward(__first2, ++__last2, __result);
      --__last1;
    }
    else {
      *--__result = *__last2;
      if (__first2 == __last2)
        return copy_backward(__first1, ++__last1, __result);
      --__last2;
    }
  }
}

template <class _BidirectionalIter, class _Tp,
          class _Distance, class _Compare>
inline void __inplace_merge_aux(_BidirectionalIter __first,
                                _BidirectionalIter __middle,
                                _BidirectionalIter __last, _Tp*, _Distance*,
                                _Compare __comp) {
  _Distance __len1 = _STLP_STD::distance(__first, __middle);
  _Distance __len2 = _STLP_STD::distance(__middle, __last);

  _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  if (__buf.begin() == 0)
    __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  else
    __merge_adaptive(__first, __middle, __last, __len1, __len2,
                     __buf.begin(), _Distance(__buf.size()),
                     __comp);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _BidirectionalIter>
void inplace_merge(_BidirectionalIter __first,
                   _BidirectionalIter __middle,
                   _BidirectionalIter __last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  if (__first == __middle || __middle == __last)
    return;
  _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
                                 _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
}

template <class _BidirectionalIter, class _Compare>
void inplace_merge(_BidirectionalIter __first,
                   _BidirectionalIter __middle,
                   _BidirectionalIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
  if (__first == __middle || __middle == __last)
    return;
  _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
                                 _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
                                 __comp);
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter1, class _InputIter2, class _Compare>
bool __includes(_InputIter1 __first1, _InputIter1 __last1,
                _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first2, *__first1)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      return false;
    }
    else if (__comp(*__first1, *__first2))
      ++__first1;
    else
      ++__first1, ++__first2;

  return __first2 == __last2;
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter1, class _InputIter2, class _Compare>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
              _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);
}

template <class _InputIter1, class _InputIter2>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
              _InputIter2 __first2, _InputIter2 __last2) {
  return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,
                               _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
                        _InputIter2 __first2, _InputIter2 __last2,
                        _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2) {
    if (__comp(*__first1, *__first2)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      *__result = *__first1;
      ++__first1;
    }
    else if (__comp(*__first2, *__first1)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      *__result = *__first2;
      ++__first2;
    }
    else {
      *__result = *__first1;
      ++__first1;
      ++__first2;
    }
    ++__result;
  }
  return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _InputIter2 __last2,
                      _OutputIter __result) {
  return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,
                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _InputIter2 __last2,
                      _OutputIter __result, _Compare __comp) {
  return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
                               _InputIter2 __first2, _InputIter2 __last2,
                               _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first1, *__first2)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      ++__first1;
    }
    else if (__comp(*__first2, *__first1))
      ++__first2;
    else {
      *__result = *__first1;
      ++__first1;
      ++__first2;
      ++__result;
    }
  return __result;
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _OutputIter __result) {
  return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,
                                       _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _OutputIter __result, _Compare __comp) {
  return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first1, *__first2)) {
      _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      *__result = *__first1;
      ++__first1;
      ++__result;
    }
    else if (__comp(*__first2, *__first1))
      ++__first2;
    else {
      ++__first1;
      ++__first2;
    }
  return _STLP_STD::copy(__first1, __last1, __result);
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
                           _InputIter2 __first2, _InputIter2 __last2,
                           _OutputIter __result) {
  return _STLP_PRIV __set_