stl_algo.h

来自「ARM Linux Tool 各种代码包括MTD」· C头文件 代码 · 共 2,009 行 · 第 1/5 页

  return ++__result;
}

template <class _InputIter, class _OutputIter, class _BinaryPredicate>
inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
                                 _OutputIter __result,
                                 _BinaryPredicate __binary_pred,
                                 output_iterator_tag)
{
  // concept requirements -- taken care of in dispatching function
  return __unique_copy(__first, __last, __result, __binary_pred,
                       __value_type(__first));
}

template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
                           _ForwardIter __result, 
                           _BinaryPredicate __binary_pred,
                           forward_iterator_tag)
{
  // concept requirements -- iterators already checked
  __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
        typename iterator_traits<_ForwardIter>::value_type,
        typename iterator_traits<_InputIter>::value_type>);

  *__result = *__first;
  while (++__first != __last)
    if (!__binary_pred(*__result, *__first)) *++__result = *__first;
  return ++__result;
}

template <class _InputIter, class _OutputIter, class _BinaryPredicate>
inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
                               _OutputIter __result,
                               _BinaryPredicate __binary_pred)
{
  // concept requirements -- predicates checked later
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_InputIter>::value_type>);

  if (__first == __last) return __result;
  return __unique_copy(__first, __last, __result, __binary_pred,
                       __iterator_category(__result));
}

template <class _ForwardIter>
_ForwardIter unique(_ForwardIter __first, _ForwardIter __last)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_EqualityComparableConcept<
        typename iterator_traits<_ForwardIter>::value_type>);

  __first = adjacent_find(__first, __last);
  return unique_copy(__first, __last, __first);
}

template <class _ForwardIter, class _BinaryPredicate>
_ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
                    _BinaryPredicate __binary_pred)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
        typename iterator_traits<_ForwardIter>::value_type,
        typename iterator_traits<_ForwardIter>::value_type>);

  __first = adjacent_find(__first, __last, __binary_pred);
  return unique_copy(__first, __last, __first, __binary_pred);
}

// reverse and reverse_copy, and their auxiliary functions

template <class _BidirectionalIter>
void __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 
               bidirectional_iterator_tag) {
  while (true)
    if (__first == __last || __first == --__last)
      return;
    else
      iter_swap(__first++, __last);
}

template <class _RandomAccessIter>
void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
               random_access_iterator_tag) {
  while (__first < __last)
    iter_swap(__first++, --__last);
}

template <class _BidirectionalIter>
inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
        _BidirectionalIter>);
  __reverse(__first, __last, __iterator_category(__first));
}

template <class _BidirectionalIter, class _OutputIter>
_OutputIter reverse_copy(_BidirectionalIter __first,
                         _BidirectionalIter __last,
                         _OutputIter __result)
{
  // concept requirements
  __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_BidirectionalIter>::value_type>);

  while (__first != __last) {
    --__last;
    *__result = *__last;
    ++__result;
  }
  return __result;
}

// rotate and rotate_copy, and their auxiliary functions

template <class _EuclideanRingElement>
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
                            _EuclideanRingElement __n)
{
  while (__n != 0) {
    _EuclideanRingElement __t = __m % __n;
    __m = __n;
    __n = __t;
  }
  return __m;
}

template <class _ForwardIter, class _Distance>
_ForwardIter __rotate(_ForwardIter __first,
                      _ForwardIter __middle,
                      _ForwardIter __last,
                      _Distance*,
                      forward_iterator_tag)
{
  if (__first == __middle)
    return __last;
  if (__last  == __middle)
    return __first;

  _ForwardIter __first2 = __middle;
  do {
    swap(*__first++, *__first2++);
    if (__first == __middle)
      __middle = __first2;
  } while (__first2 != __last);

  _ForwardIter __new_middle = __first;

  __first2 = __middle;

  while (__first2 != __last) {
    swap (*__first++, *__first2++);
    if (__first == __middle)
      __middle = __first2;
    else if (__first2 == __last)
      __first2 = __middle;
  }

  return __new_middle;
}


template <class _BidirectionalIter, class _Distance>
_BidirectionalIter __rotate(_BidirectionalIter __first,
                            _BidirectionalIter __middle,
                            _BidirectionalIter __last,
                            _Distance*,
                            bidirectional_iterator_tag)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
        _BidirectionalIter>);

  if (__first == __middle)
    return __last;
  if (__last  == __middle)
    return __first;

  __reverse(__first,  __middle, bidirectional_iterator_tag());
  __reverse(__middle, __last,   bidirectional_iterator_tag());

  while (__first != __middle && __middle != __last)
    swap (*__first++, *--__last);

  if (__first == __middle) {
    __reverse(__middle, __last,   bidirectional_iterator_tag());
    return __last;
  }
  else {
    __reverse(__first,  __middle, bidirectional_iterator_tag());
    return __first;
  }
}

template <class _RandomAccessIter, class _Distance, class _Tp>
_RandomAccessIter __rotate(_RandomAccessIter __first,
                           _RandomAccessIter __middle,
                           _RandomAccessIter __last,
                           _Distance *, _Tp *)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIter>);

  _Distance __n = __last   - __first;
  _Distance __k = __middle - __first;
  _Distance __l = __n - __k;
  _RandomAccessIter __result = __first + (__last - __middle);

  if (__k == 0)
    return __last;

  else if (__k == __l) {
    swap_ranges(__first, __middle, __middle);
    return __result;
  }

  _Distance __d = __gcd(__n, __k);

  for (_Distance __i = 0; __i < __d; __i++) {
    _Tp __tmp = *__first;
    _RandomAccessIter __p = __first;

    if (__k < __l) {
      for (_Distance __j = 0; __j < __l/__d; __j++) {
        if (__p > __first + __l) {
          *__p = *(__p - __l);
          __p -= __l;
        }

        *__p = *(__p + __k);
        __p += __k;
      }
    }

    else {
      for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
        if (__p < __last - __k) {
          *__p = *(__p + __k);
          __p += __k;
        }

        *__p = * (__p - __l);
        __p -= __l;
      }
    }

    *__p = __tmp;
    ++__first;
  }

  return __result;
}

template <class _ForwardIter>
inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
                           _ForwardIter __last)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);

  return __rotate(__first, __middle, __last,
                  __distance_type(__first),
                  __iterator_category(__first));
}

template <class _ForwardIter, class _OutputIter>
_OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
                        _ForwardIter __last, _OutputIter __result)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_ForwardIter>::value_type>);

  return copy(__first, __middle, copy(__middle, __last, __result));
}

// Return a random number in the range [0, __n).  This function encapsulates
// whether we're using rand (part of the standard C library) or lrand48
// (not standard, but a much better choice whenever it's available).
template <class _Distance>
inline _Distance __random_number(_Distance __n) {
#ifdef _GLIBCPP_HAVE_DRAND48
  return lrand48() % __n;
#else
  return rand() % __n;
#endif
}

// random_shuffle

template <class _RandomAccessIter>
inline void random_shuffle(_RandomAccessIter __first,
                           _RandomAccessIter __last)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIter>);

  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __random_number((__i - __first) + 1));
}

template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
                    _RandomNumberGenerator& __rand)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIter>);

  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __rand((__i - __first) + 1));
}

// random_sample and random_sample_n (extensions, not part of the standard).

template <class _ForwardIter, class _OutputIter, class _Distance>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
                            _OutputIter __out, const _Distance __n)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_ForwardIter>::value_type>);

  _Distance __remaining = 0;
  distance(__first, __last, __remaining);
  _Distance __m = min(__n, __remaining);

  while (__m > 0) {
    if (__random_number(__remaining) < __m) {
      *__out = *__first;
      ++__out;
      --__m;
    }

    --__remaining;
    ++__first;
  }
  return __out;
}

template <class _ForwardIter, class _OutputIter, class _Distance,
          class _RandomNumberGenerator>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
                            _OutputIter __out, const _Distance __n,
                            _RandomNumberGenerator& __rand)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_ForwardIter>::value_type>);
  __glibcpp_function_requires(_UnaryFunctionConcept<
        _RandomNumberGenerator, _Distance, _Distance>);

  _Distance __remaining = 0;
  distance(__first, __last, __remaining);
  _Distance __m = min(__n, __remaining);

  while (__m > 0) {
    if (__rand(__remaining) < __m) {
      *__out = *__first;
      ++__out;
      --__m;
    }

    --__remaining;
    ++__first;
  }
  return __out;
}

template <class _InputIter, class _RandomAccessIter, class _Distance>
_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
                                  _RandomAccessIter __out,
                                  const _Distance __n)
{
  _Distance __m = 0;
  _Distance __t = __n;
  for ( ; __first != __last && __m < __n; ++__m, ++__first) 
    __out[__m] = *__first;

  while (__first != __last) {
    ++__t;
    _Distance __M = __random_number(__t);
    if (__M < __n)
      __out[__M] = *__first;
    ++__first;
  }

  return __out + __m;
}