如何合并两个已排序向量并组合重叠元素？

Question

让

typedef pair<int, double> Element;

然后我有两个向量：

vector<Element> A, B;

这些向量按Element.first中的整数排序。我想获得第三个向量C，它是A和B的并集。这听起来像set_union，但当A[i].first == B[j].first时，我需要不同的行为。 set_union将简单地选择要在C中包含的源元素之一，但我需要结果将两个元素“组合”起来。换句话说，就像这样：

C[k].first = A[i].first; // == B[j].first.  set_union does this
C[k].second = A[i].second + B[j].second; // set_union does NOT do this.

我想知道是否可以使用标准库（或类似Boost的东西）来实现这一点。手动执行此操作的代码并不特别复杂，但我不想重复发明轮子。

我能找到的唯一其他相关操作是merge。它也不会合并元素，并且需要进行另一个合并步骤。

- Adam

---

std::merge可以使用非常聪明的输出迭代器来完成，但 - Mooing Duck

我不同意...这里的目标是误导的，任何对标准算法和花哨的迭代器的“聪明”应用都会比Alex答案中明显的循环方法更慢、更冗长、更复杂。 - Tony Delroy

@Praetorian：如果你创建一个迭代器来持有容器的引用，它可以查看该容器的最后一个元素并将其与传递的元素进行比较，然后决定是将新元素推入容器的末尾还是与前一个元素合并。 - Benjamin Lindley

@Benjamin 那样做是可行的，我也在考虑让迭代器以某种方式跟踪先前插入的元素，但错过了您只需要访问最后一个元素的事实。但是，如果您必须跳过很多障碍才能使 std::merge 做您想要的事情，我会支持 TonyD 的观点，即编写自定义算法是正确的方法。 - Praetorian

好的 - 我之前没有意识到 boost::function_output_iterator 很适合这个问题...同意在使用 boost 的情况下，这是一个很好的解决方案。(如果没有 boost，编写一个返回代理以捕获赋值的迭代器就不值得麻烦了...) - Tony Delroy

Answer 1

我认为使用std::merge和boost::function_output_iterator的方法非常清晰。

#include <algorithm>
#include <iostream>
#include <vector>

#include <boost/function_output_iterator.hpp>

/* Convenience type alias for our element. */
using Elem = std::pair<int, double>;

/* Convenience type alias for the container of our elements. */
using Elems = std::vector<Elem>;

/* Our appender that will be created with boost::function_output_iterator. */
class Appender {
  public:

  /* Cache the reference to our container. */
  Appender(Elems &elems) : elems_(elems) {}

  /* Conditionally modify or append elements. */
  void operator()(const Elem &elem) const {
    if (!elems_.empty() && elems_.back().first == elem.first) {
      elems_.back().second += elem.second;
      return;
    }  // if
    elems_.push_back(elem);
  }

  private:

  /* Reference to our container. */      
  Elems &elems_;

};  // Appender

int main() {
  // Sample data.
  Elems lhs {{1, 2.3}, {2, 3}, {5, 3.4}};
  Elems rhs {{1, 1.3}, {3, 5.5}, {4, 2.2}};
  Elems result;
  // Merge and use appender to append elements.
  std::merge(std::begin(lhs),
             std::end(lhs),
             std::begin(rhs),
             std::end(rhs),
             boost::make_function_output_iterator(Appender(result)));
  // Print result.
  for (const auto &elem : result) {
    std::cout << elem.first << ' ' << elem.second << std::endl;
  }  // for
}

打印:

1 3.6
2 3
3 5.5
4 2.2
5 3.4

注意。使用function_output_iterator是由Benjamin Lindley建议的。

- mpark

Answer 2

下面是使用独立的通用算法merge_elements实现的示例：

#include <algorithm>
#include <utility>

template <typename LInput, typename RInput, typename Output>
Output merge_elements(LInput lbegin, LInput lend,
                      RInput rbegin, RInput rend,
                      Output out) {
    while(true) {
        if (lbegin == lend) {
            return std::copy(rbegin, rend, out);
        }

        if (rbegin == rend) {
            return std::copy(lbegin, lend, out);
        }

        if (lbegin->first < rbegin->first) {
            *out++ = *lbegin++;
        } else if (rbegin->first < lbegin->first) {
            *out++ = *rbegin++;
        } else {
            *out++ = std::make_pair(lbegin->first, lbegin->second + rbegin->second);
            ++lbegin;
            ++rbegin;
        }
    }
}

#include <iostream>
#include <iterator>
#include <vector>

/* Convenience type alias for our element. */
using Elem = std::pair<int, double>;

/* Convenience type alias for the container of our elements. */
using Elems = std::vector<Elem>;

int main() {
  // Sample data.
  Elems lhs {{1, 2.3}, {2, 3}, {5, 3.4}};
  Elems rhs {{1, 1.3}, {3, 5.5}, {4, 2.2}};
  Elems result;
  // Merge and use appender to append elements.
  merge_elements(std::begin(lhs),
                 std::end(lhs),
                 std::begin(rhs),
                 std::end(rhs),
                 std::back_inserter(result));
  // Print result.
  for (const auto &elem : result) {
    std::cout << elem.first << ' ' << elem.second << std::endl;
  }  // for
}

它不需要boost，但与mpark的boost解决方案几乎具有完全相同的总行数。有趣的是，这个算法足够通用，可以不变地与std::map<int,double>以及std::vector<std::pair<int,double>>一起使用：

#include <iostream>
#include <iterator>
#include <map>

/* Convenience type alias for the container of our elements. */
using Elems = std::map<int, double>;

int main() {
  // Sample data.
  Elems lhs {{1, 2.3}, {2, 3}, {5, 3.4}};
  Elems rhs {{1, 1.3}, {3, 5.5}, {4, 2.2}};
  Elems result;
  // Merge and use appender to append elements.
  merge_elements(std::begin(lhs),
                 std::end(lhs),
                 std::begin(rhs),
                 std::end(rhs),
                 std::inserter(result, result.begin()));
  // Print result.
  for (const auto &elem : result) {
    std::cout << elem.first << ' ' << elem.second << std::endl;
  }  // for
}

- Casey