让
typedef pair<int, double> Element;
然后我有两个 vector :
vector<Element> A, B;
这些 vector 按 Element.first
中的整数排序。我想得到第三个 vector 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 .它也不合并元素,并且会涉及另一个组合过程。
最佳答案
我认为将 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 建议.
关于c++ - 如何合并两个排序的 vector 并组合重叠元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20694791/