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> |
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> |
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 | |