C++ STL: set_difference()

Usage:

set_difference(minuend.begin(), minuend.end(),
               subtracter.begin(), subtracter.end(), difference.begin());

The source code of set_difference() from <stl_algo.h>:

/**
*  @brief Return the difference of two sorted ranges.
*  @ingroup set_algorithms
*  @param  __first1  Start of first range.
*  @param  __last1   End of first range.
*  @param  __first2  Start of second range.
*  @param  __last2   End of second range.
*  @return  End of the output range.
*  @ingroup set_algorithms
*
*  This operation iterates over both ranges, copying elements present in
*  the first range but not the second in order to the output range.
*  Iterators increment for each range.  When the current element of the
*  first range is less than the second, that element is copied and the
*  iterator advances.  If the current element of the second range is less,
*  the iterator advances, but no element is copied.  If an element is
*  contained in both ranges, no elements are copied and both ranges
*  advance.  The output range may not overlap either input range.
*/
template<typename _InputIterator1, typename _InputIterator2,
        typename _OutputIterator>
inline _OutputIterator
set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
               _InputIterator2 __first2, _InputIterator2 __last2,
               _OutputIterator __result) {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept < _InputIterator1 >)
    __glibcxx_function_requires(_InputIteratorConcept < _InputIterator2 >)
    __glibcxx_function_requires(_OutputIteratorConcept < _OutputIterator,
                                typename iterator_traits<_InputIterator1>::value_type >)
    __glibcxx_function_requires(_LessThanOpConcept <
                                typename iterator_traits<_InputIterator1>::value_type,
                                typename iterator_traits<_InputIterator2>::value_type >)
    __glibcxx_function_requires(_LessThanOpConcept <
                                typename iterator_traits<_InputIterator2>::value_type,
                                typename iterator_traits<_InputIterator1>::value_type >)
    __glibcxx_requires_sorted_set(__first1, __last1, __first2);
    __glibcxx_requires_sorted_set(__first2, __last2, __first1);

    return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
                                            __first2, __last2, __result,
                                            __gnu_cxx::__ops::__iter_less_iter());
}

The source code of __set_difference() from <stl_algo.h>:

template<typename _InputIterator1, typename _InputIterator2,
        typename _OutputIterator,
        typename _Compare>
_OutputIterator
__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
                 _InputIterator2 __first2, _InputIterator2 __last2,
                 _OutputIterator __result, _Compare __comp) {
    while (__first1 != __last1 && __first2 != __last2)
        if (__comp(__first1, __first2)) {
            *__result = *__first1;
            ++__first1;
            ++__result;
        }
        else if (__comp(__first2, __first1))
            ++__first2;
        else {
            ++__first1;
            ++__first2;
        }
    return std::copy(__first1, __last1, __result);
}

留下评论