What is the correct std::set_union code?

Question

This site claims that set_union is equivalent to the following code:

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_union ( InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             OutputIterator result )
{
  while (true)
  {
    if (*first1<*first2) *result++ = *first1++;
    else if (*first2<*first1) *result++ = *first2++;
    else { *result++ = *first1++; first2++; }

    if (first1==last1) return copy(first2,last2,result);
    if (first2==last2) return copy(first1,last1,result);
  }
}

But that seems strange: Won't that crash (or result in other undefined behavior) if one of the ranges is empty? Shouldn't the two if clauses be at the beginning of the while loop, instead of the end?

Answer 1

I agree that it looks totally broken. For comparison, here is the STLport code:

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));
}