2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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
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.
30 * a = {{1, 1}, {2, 2}, {3, 3}};
31 * b = {{1, 2}, {2, 3}};
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
39 #ifndef FOLLY_MERGE_H_
40 #define FOLLY_MERGE_H_
46 template<class InputIt1, class InputIt2, class OutputIt, class Compare>
47 OutputIt merge(InputIt1 first1, InputIt1 last1,
48 InputIt2 first2, InputIt2 last2,
49 OutputIt d_first, Compare comp) {
50 for (; first1 != last1; ++d_first) {
51 if (first2 == last2) {
52 return std::copy(first1, last1, d_first);
54 if (comp(*first2, *first1)) {
62 return std::copy(first2, last2, d_first);
65 template<class InputIt1, class InputIt2, class OutputIt>
66 OutputIt merge(InputIt1 first1, InputIt1 last1,
67 InputIt2 first2, InputIt2 last2,
69 for (; first1 != last1; ++d_first) {
70 if (first2 == last2) {
71 return std::copy(first1, last1, d_first);
73 if (*first2 < *first1) {
81 return std::copy(first2, last2, d_first);