合并多个 STL 容器、删除重复元素的最佳方法? [英] Best way to merge multiple STL containers, removing duplicate elements?
问题描述
我有两个 STL 容器要合并,删除出现多次的任何元素.例如:
I have two STL containers that I want to merge, removing any elements that appear more than once. For example:
typedef std::list<int> container;
container c1;
container c2;
c1.push_back(1);
c1.push_back(2);
c1.push_back(3);
c2.push_back(2);
c2.push_back(3);
c2.push_back(4);
container c3 = unique_merge(c1, c2);
// c3 now contains the following 4 elements:
// 1, 2, 3, 4
std::unique 似乎仅适用于相邻元素,在我的情况下,容器可以按任何顺序排列.我想我可以做一些 std::set 诡计:
std::unique seems to be for adjacent elements only, and in my case the containers could be in any order. I could do some std::set trickery I guess:
container unique_merge(const container& c1, const container& c2)
{
std::set<container::value_type> s;
BOOST_FOREACH(const container::value_type& val, c1)
s.insert(val);
BOOST_FOREACH(const container::value_type& val, c2)
s.insert(val);
return container(s.begin(), s.end());
}
是否有更好的方法,或者我是否遗漏了一些明显的出血?
Is there a better way or have I missed something bleeding obvious?
推荐答案
对于无序列表,您的设置技巧可能是最好的技巧之一.每个插入应该是 O(log n),需要 N 个插入,遍历将是 O(n),给你 O(N*log n).另一种选择是在每个列表上单独运行 std::sort,然后使用 std::set_union,它会为您删除重复项.这也将是 O(n*log n),因此如果您担心性能,则必须进行分析.如果不是,请选择对您更有意义的方式.
For an unordered lists, your set trick is probably one of the best. It each insert should be O(log n), with N inserts required, and traversing will be O(n), giving you O(N*log n). The other option is to run std::sort on each list individually and then walk through them in parallel using std::set_union, which removes duplicates for you. This will also be O(n*log n), so if you're worried about performance, you'll have to profile. If you're not, do whichever makes more sense to you.
set_union
仅在原始列表中没有重复项时才有效,否则您必须使用 sort
、merge
、unique
和 erase
.大 O 性能仍然相同,但对性能分析的注意事项相同.
set_union
will only work if there are no duplicates in the original lists, otherwise you'll have to go with sort
, merge
, unique
and erase
. The big O performance is still the same, with the same caveats about profiling.
template <typename container>
container unique_merge(container c1, container c2)
{
std::sort(c1.begin(), c1.end());
std::sort(c2.begin(), c2.end());
container mergeTarget;
std::merge(c1.begin(), c1.end(), c2.begin(), c2.end(),
std::insert_iterator(mergeTarget, mergeTarget.end())
);
std::erase(
std::unique(mergeTarget.begin(), mergeTarget.end()),
mergeTarget.end()
);
return mergeTarget;
}
这篇关于合并多个 STL 容器、删除重复元素的最佳方法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!