1 /*
2 * Copyright 2014-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /*
18 * folly::merge() is an implementation of std::merge with one additonal
19 * guarantee: if the input ranges overlap, the order that values *from the two
20 * different ranges* appear in the output is well defined (std::merge only
21 * guarantees relative ordering is maintained within a single input range).
22 * This semantic is very useful when the output container removes duplicates
23 * (such as std::map) to guarantee that elements from b override elements from
24 * a.
25 *
26 * ex. Let's say we have two vector<pair<int, int>> as input, and we are
27 * merging into a vector<pair<int, int>>. The comparator is returns true if the
28 * first argument has a lesser 'first' value in the pair.
29 *
30 * a = {{1, 1}, {2, 2}, {3, 3}};
31 * b = {{1, 2}, {2, 3}};
32 *
33 * folly::merge<...>(a.begin(), a.end(), b.begin(), b.end(), outputIter) is
34 * guaranteed to produce {{1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}}. That is,
35 * if comp(it_a, it_b) == comp(it_b, it_a) == false, we first insert the element
36 * from a.
37 */
38
39 #pragma once
40
41 #include <algorithm>
42
43 namespace folly {
44
45 template <class InputIt1, class InputIt2, class OutputIt, class Compare>
merge(InputIt1 first1,InputIt1 last1,InputIt2 first2,InputIt2 last2,OutputIt d_first,Compare comp)46 OutputIt merge(
47 InputIt1 first1,
48 InputIt1 last1,
49 InputIt2 first2,
50 InputIt2 last2,
51 OutputIt d_first,
52 Compare comp) {
53 for (; first1 != last1; ++d_first) {
54 if (first2 == last2) {
55 return std::copy(first1, last1, d_first);
56 }
57 if (comp(*first2, *first1)) {
58 *d_first = *first2;
59 ++first2;
60 } else {
61 *d_first = *first1;
62 ++first1;
63 }
64 }
65 return std::copy(first2, last2, d_first);
66 }
67
68 template <class InputIt1, class InputIt2, class OutputIt>
merge(InputIt1 first1,InputIt1 last1,InputIt2 first2,InputIt2 last2,OutputIt d_first)69 OutputIt merge(
70 InputIt1 first1,
71 InputIt1 last1,
72 InputIt2 first2,
73 InputIt2 last2,
74 OutputIt d_first) {
75 for (; first1 != last1; ++d_first) {
76 if (first2 == last2) {
77 return std::copy(first1, last1, d_first);
78 }
79 if (*first2 < *first1) {
80 *d_first = *first2;
81 ++first2;
82 } else {
83 *d_first = *first1;
84 ++first1;
85 }
86 }
87 return std::copy(first2, last2, d_first);
88 }
89
90 } // namespace folly
91