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

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这样的东西).手动执行此操作的代码并不是特别复杂,但我不想重新发明这个轮子.

我能找到的唯一其他相关操作是合并.它也不合并元素,并涉及另一个组合传递.

Answer 1

我认为使用std::mergewith 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

注意.Benjamin Lindley建议使用function_output_iterator.