folly/Merge.h

   1 /*
   2  * Copyright 2015 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 #ifndef FOLLY_MERGE_H_
  40 #define FOLLY_MERGE_H_
  41
  42 #include <algorithm>
  43
  44 namespace folly {
  45
  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);
  53     }
  54     if (comp(*first2, *first1)) {
  55       *d_first = *first2;
  56       ++first2;
  57     } else {
  58       *d_first = *first1;
  59       ++first1;
  60     }
  61   }
  62   return std::copy(first2, last2, d_first);
  63 }
  64
  65 template<class InputIt1, class InputIt2, class OutputIt>
  66 OutputIt merge(InputIt1 first1, InputIt1 last1,
  67                InputIt2 first2, InputIt2 last2,
  68                OutputIt d_first) {
  69   for (; first1 != last1; ++d_first) {
  70     if (first2 == last2) {
  71       return std::copy(first1, last1, d_first);
  72     }
  73     if (*first2 < *first1) {
  74       *d_first = *first2;
  75       ++first2;
  76     } else {
  77       *d_first = *first1;
  78       ++first1;
  79     }
  80   }
  81   return std::copy(first2, last2, d_first);
  82 }
  83
  84 }
  85
  86 #endif