stl_algo.h

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

  _ForwardIter1 __current = __first1;

  while (__first1 != __last1) {
    while (__first1 != __last1) {
      if (__predicate(*__first1, *__first2))
        break;
      ++__first1;
    }
    while (__first1 != __last1 && !__predicate(*__first1, *__first2))
      ++__first1;
    if (__first1 == __last1)
      return __last1;

    __p = __p1;
    __current = __first1; 
    if (++__current == __last1) return __last1;

    while (__predicate(*__current, *__p)) {
      if (++__p == __last2)
        return __first1;
      if (++__current == __last1)
        return __last1;
    }

    ++__first1;
  }
  return __first1;
}

// search_n.  Search for __count consecutive copies of __val.

template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
                      _Integer __count, const _Tp& __val)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_EqualityComparableConcept<
        typename iterator_traits<_ForwardIter>::value_type>);
  __glibcpp_function_requires(_EqualityComparableConcept<_Tp>);

  if (__count <= 0)
    return __first;
  else {
    __first = find(__first, __last, __val);
    while (__first != __last) {
      _Integer __n = __count - 1;
      _ForwardIter __i = __first;
      ++__i;
      while (__i != __last && __n != 0 && *__i == __val) {
        ++__i;
        --__n;
      }
      if (__n == 0)
        return __first;
      else
        __first = find(__i, __last, __val);
    }
    return __last;
  }
}

template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
                      _Integer __count, const _Tp& __val,
                      _BinaryPred __binary_pred)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
        typename iterator_traits<_ForwardIter>::value_type, _Tp>);

  if (__count <= 0)
    return __first;
  else {
    while (__first != __last) {
      if (__binary_pred(*__first, __val))
        break;
      ++__first;
    }
    while (__first != __last) {
      _Integer __n = __count - 1;
      _ForwardIter __i = __first;
      ++__i;
      while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
        ++__i;
        --__n;
      }
      if (__n == 0)
        return __first;
      else {
        while (__i != __last) {
          if (__binary_pred(*__i, __val))
            break;
          ++__i;
        }
        __first = __i;
      }
    }
    return __last;
  }
} 

// swap_ranges

template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
                          _ForwardIter2 __first2)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>);
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>);
  __glibcpp_function_requires(_ConvertibleConcept<
        typename iterator_traits<_ForwardIter1>::value_type,
        typename iterator_traits<_ForwardIter2>::value_type>);
  __glibcpp_function_requires(_ConvertibleConcept<
        typename iterator_traits<_ForwardIter2>::value_type,
        typename iterator_traits<_ForwardIter1>::value_type>);

  for ( ; __first1 != __last1; ++__first1, ++__first2)
    iter_swap(__first1, __first2);
  return __first2;
}

// transform

template <class _InputIter, class _OutputIter, class _UnaryOperation>
_OutputIter transform(_InputIter __first, _InputIter __last,
                      _OutputIter __result, _UnaryOperation __unary_op)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
/* XXX
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        // should be "the type returned by _UnaryOperation"
        typename iterator_traits<_InputIter>::value_type>);
*/

  for ( ; __first != __last; ++__first, ++__result)
    *__result = __unary_op(*__first);
  return __result;
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _BinaryOperation>
_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _OutputIter __result,
                      _BinaryOperation __binary_op)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
/* XXX
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        // should be "the type returned by _BinaryOperation"
        typename iterator_traits<_InputIter1>::value_type>);
*/

  for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
    *__result = __binary_op(*__first1, *__first2);
  return __result;
}

// replace, replace_if, replace_copy, replace_copy_if

template <class _ForwardIter, class _Tp>
void replace(_ForwardIter __first, _ForwardIter __last,
             const _Tp& __old_value, const _Tp& __new_value)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_EqualOpConcept<
        typename iterator_traits<_ForwardIter>::value_type, _Tp>);
  __glibcpp_function_requires(_ConvertibleConcept<_Tp,
        typename iterator_traits<_ForwardIter>::value_type>);

  for ( ; __first != __last; ++__first)
    if (*__first == __old_value)
      *__first = __new_value;
}

template <class _ForwardIter, class _Predicate, class _Tp>
void replace_if(_ForwardIter __first, _ForwardIter __last,
                _Predicate __pred, const _Tp& __new_value)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_ConvertibleConcept<_Tp,
        typename iterator_traits<_ForwardIter>::value_type>);
  __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
        typename iterator_traits<_ForwardIter>::value_type>);

  for ( ; __first != __last; ++__first)
    if (__pred(*__first))
      *__first = __new_value;
}

template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter replace_copy(_InputIter __first, _InputIter __last,
                         _OutputIter __result,
                         const _Tp& __old_value, const _Tp& __new_value)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_InputIter>::value_type>);
  __glibcpp_function_requires(_EqualOpConcept<
        typename iterator_traits<_InputIter>::value_type, _Tp>);

  for ( ; __first != __last; ++__first, ++__result)
    *__result = *__first == __old_value ? __new_value : *__first;
  return __result;
}

template <class _InputIter, class _OutputIter, class _Predicate, class _Tp>
_OutputIter replace_copy_if(_InputIter __first, _InputIter __last,
                            _OutputIter __result,
                            _Predicate __pred, const _Tp& __new_value)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_InputIter>::value_type>);
  __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
        typename iterator_traits<_InputIter>::value_type>);

  for ( ; __first != __last; ++__first, ++__result)
    *__result = __pred(*__first) ? __new_value : *__first;
  return __result;
}

// generate and generate_n

template <class _ForwardIter, class _Generator>
void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_GeneratorConcept<_Generator,
        typename iterator_traits<_ForwardIter>::value_type>);

  for ( ; __first != __last; ++__first)
    *__first = __gen();
}

template <class _OutputIter, class _Size, class _Generator>
_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen)
{
/*
  // XXX concept requirements
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        "the return type of _Generator" ??   >);
*/

  for ( ; __n > 0; --__n, ++__first)
    *__first = __gen();
  return __first;
}

// remove, remove_if, remove_copy, remove_copy_if

template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter remove_copy(_InputIter __first, _InputIter __last,
                        _OutputIter __result, const _Tp& __value)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_InputIter>::value_type>);
  __glibcpp_function_requires(_EqualOpConcept<
        typename iterator_traits<_InputIter>::value_type, _Tp>);

  for ( ; __first != __last; ++__first)
    if (!(*__first == __value)) {
      *__result = *__first;
      ++__result;
    }
  return __result;
}

template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
                           _OutputIter __result, _Predicate __pred)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_InputIter>::value_type>);
  __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
        typename iterator_traits<_InputIter>::value_type>);

  for ( ; __first != __last; ++__first)
    if (!__pred(*__first)) {
      *__result = *__first;
      ++__result;
    }
  return __result;
}

template <class _ForwardIter, class _Tp>
_ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
                    const _Tp& __value)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_ConvertibleConcept<_Tp,
        typename iterator_traits<_ForwardIter>::value_type>);
  __glibcpp_function_requires(_EqualOpConcept<
        typename iterator_traits<_ForwardIter>::value_type, _Tp>);

  __first = find(__first, __last, __value);
  _ForwardIter __i = __first;
  return __first == __last ? __first 
                           : remove_copy(++__i, __last, __first, __value);
}

template <class _ForwardIter, class _Predicate>
_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
                       _Predicate __pred)
{
  // concept requirements
  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
        typename iterator_traits<_ForwardIter>::value_type>);

  __first = find_if(__first, __last, __pred);
  _ForwardIter __i = __first;
  return __first == __last ? __first 
                           : remove_copy_if(++__i, __last, __first, __pred);
}

// unique and unique_copy

template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result, _Tp*)
{
  // concept requirements -- taken care of in dispatching function
  _Tp __value = *__first;
  *__result = __value;
  while (++__first != __last)
    if (!(__value == *__first)) {
      __value = *__first;
      *++__result = __value;
    }
  return ++__result;
}

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

template <class _InputIter, class _ForwardIter>
_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
                           _ForwardIter __result, forward_iterator_tag)
{
  // concept requirements -- taken care of in dispatching function
  *__result = *__first;
  while (++__first != __last)
    if (!(*__result == *__first))
      *++__result = *__first;
  return ++__result;
}

template <class _InputIter, class _OutputIter>
inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
                               _OutputIter __result)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
        typename iterator_traits<_InputIter>::value_type>);
  __glibcpp_function_requires(_EqualityComparableConcept<
        typename iterator_traits<_InputIter>::value_type>);

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

template <class _InputIter, class _OutputIter, class _BinaryPredicate,
          class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result,
                          _BinaryPredicate __binary_pred, _Tp*)
{
  // concept requirements -- iterators already checked
  __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, _Tp, _Tp>);

  _Tp __value = *__first;
  *__result = __value;
  while (++__first != __last)
    if (!__binary_pred(__value, *__first)) {
      __value = *__first;
      *++__result = __value;
    }