folly/Merge.h

   1 /*
   2  * Copyright 2017 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(InputIt1 first1, InputIt1 last1,
  47                InputIt2 first2, InputIt2 last2,
  48                OutputIt d_first, Compare comp) {
  49   for (; first1 != last1; ++d_first) {
  50     if (first2 == last2) {
  51       return std::copy(first1, last1, d_first);
  52     }
  53     if (comp(*first2, *first1)) {
  54       *d_first = *first2;
  55       ++first2;
  56     } else {
  57       *d_first = *first1;
  58       ++first1;
  59     }
  60   }
  61   return std::copy(first2, last2, d_first);
  62 }
  63
  64 template<class InputIt1, class InputIt2, class OutputIt>
  65 OutputIt merge(InputIt1 first1, InputIt1 last1,
  66                InputIt2 first2, InputIt2 last2,
  67                OutputIt d_first) {
  68   for (; first1 != last1; ++d_first) {
  69     if (first2 == last2) {
  70       return std::copy(first1, last1, d_first);
  71     }
  72     if (*first2 < *first1) {
  73       *d_first = *first2;
  74       ++first2;
  75     } else {
  76       *d_first = *first1;
  77       ++first1;
  78     }
  79   }
  80   return std::copy(first2, last2, d_first);
  81 }
  82
  83 }