105 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_SET_UNION_H10#define _LIBCPP___ALGORITHM_SET_UNION_H11 12#include <__algorithm/comp.h>13#include <__algorithm/comp_ref_type.h>14#include <__algorithm/copy.h>15#include <__config>16#include <__iterator/iterator_traits.h>17#include <__utility/move.h>18#include <__utility/pair.h>19 20#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)21# pragma GCC system_header22#endif23 24_LIBCPP_PUSH_MACROS25#include <__undef_macros>26 27_LIBCPP_BEGIN_NAMESPACE_STD28 29template <class _InIter1, class _InIter2, class _OutIter>30struct __set_union_result {31 _InIter1 __in1_;32 _InIter2 __in2_;33 _OutIter __out_;34 35 // need a constructor as C++03 aggregate init is hard36 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX2037 __set_union_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)38 : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {}39};40 41template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>42_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_union_result<_InIter1, _InIter2, _OutIter> __set_union(43 _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) {44 for (; __first1 != __last1; ++__result) {45 if (__first2 == __last2) {46 auto __ret1 = std::__copy(std::move(__first1), std::move(__last1), std::move(__result));47 return __set_union_result<_InIter1, _InIter2, _OutIter>(48 std::move(__ret1.first), std::move(__first2), std::move((__ret1.second)));49 }50 if (__comp(*__first2, *__first1)) {51 *__result = *__first2;52 ++__first2;53 } else {54 if (!__comp(*__first1, *__first2)) {55 ++__first2;56 }57 *__result = *__first1;58 ++__first1;59 }60 }61 auto __ret2 = std::__copy(std::move(__first2), std::move(__last2), std::move(__result));62 return __set_union_result<_InIter1, _InIter2, _OutIter>(63 std::move(__first1), std::move(__ret2.first), std::move((__ret2.second)));64}65 66template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>67_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_union(68 _InputIterator1 __first1,69 _InputIterator1 __last1,70 _InputIterator2 __first2,71 _InputIterator2 __last2,72 _OutputIterator __result,73 _Compare __comp) {74 return std::__set_union<__comp_ref_type<_Compare> >(75 std::move(__first1),76 std::move(__last1),77 std::move(__first2),78 std::move(__last2),79 std::move(__result),80 __comp)81 .__out_;82}83 84template <class _InputIterator1, class _InputIterator2, class _OutputIterator>85_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_union(86 _InputIterator1 __first1,87 _InputIterator1 __last1,88 _InputIterator2 __first2,89 _InputIterator2 __last2,90 _OutputIterator __result) {91 return std::set_union(92 std::move(__first1),93 std::move(__last1),94 std::move(__first2),95 std::move(__last2),96 std::move(__result),97 __less<>());98}99 100_LIBCPP_END_NAMESPACE_STD101 102_LIBCPP_POP_MACROS103 104#endif // _LIBCPP___ALGORITHM_SET_UNION_H105