c++ - 带有大列表的 STL set_union

Question

有两个

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

我将它们用作集合，因此是经过排序和唯一的:

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());

不工作机器人我实际上希望结果在没有计算大拷贝的情况下做

a = c;

之后。另一个问题是如果 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 列表留空。