STL set_union大名单

Question

有两个

list<int> a (4,100); 
list<int> b (4,200); 

我使用它们作为一组这样的排序和uniqued：

a.sort(); 
a.unique(); 
b.sort(); 
b.unique(); 

现在，这两个名单是这样的：

a: 100 
b: 200 

现在我计算工会：

list <int> c(a.size() + b.size()); 
set_union(a.begin(), a.end(), b.begin(), b.end(), c.begin()); 

结果很好，但我想要的不是将两个列表复制到另一个列表中。因为这个列表非常大，并且不包含实际的整数。

set_union(a.begin(), a.end(), b.begin(), b.end(), a.begin()); 

不行的机器人其实我想要的结果是在一个没有calulating一大抄，做

a = c; 

aftterwards。另一个问题是，如果a = b = {100}，那么结果c是 {100，0}！

任何想法？

Answer 1

您可以最小化复制std::set_difference后跟list::merge。两者都是线性操作。

std::list<int> a, b, c; 

std::set_difference(b.begin(), b.end(), a.begin(), a.end(), back_inserter(c)); 
a.merge(c); 

的b列表不修改，并且临时c列表为空。

Answer 2

我觉得你只是想list::merge

std::list<int> a, b; 

a.sort(); 
a.unique(); 
b.sort(); 
b.unique(); 

a.merge(b); 
a.unique(); 

根据您的实际数据可能更快变成这样

a.sort(); 
b.sort(); 
a.merge(b); 
a.unique();