c++ - 比较 2 个 c++ std::lists 的最快方法，在每次迭代中改变

Question

假设我有 2 个 std::lists，每个包含不同数量的元素。每个元素(在每个列表上)都有 UNIQUE int id 值。在每次迭代中，我需要从第一个列表中删除未出现在第二个列表中的元素，并从第二个列表中添加不属于第一个列表的元素。例如(数字=唯一 ID):

1. iteration: first[3,2,1], second[4,3,5,7,6], result: [3,4,5,6,7]
2. iteration: first[3,4,5,6,7], second[4,10,9], result: [4,10,9]

等等... 我不能简单地将第二个交换到第一个(让我们认识到这是不可能的，阅读时间太长)。我的问题是: 我可以执行更新第一个列表的最佳搜索算法是什么？我的意思是，我应该在两个排序列表上使用嵌套循环并比较 id 吗？从第一个中连续删除第二个中缺少的元素，但也删除第一个中重复的元素。然后合并呢？或者制作其中一个 unordered_map(哈希表)？

编辑:

本想把问题简单化，其实现在还不清楚。我无法更改容器，有 2 个未排序的列表，每个列表包含 2 个不同的结构。两种结构之间的唯一联系是 id 参数。在每次迭代中，我都必须检查第一个列表是否与第二个列表一样。 ID 是唯一的，不允许重复。因此，如果 ids 匹配列表将是相同的。我不能交换它们，因为第一个列表有例如 30 个值，第二个列表有 10 个(未完成)。还有另一个特殊函数可以为包含许多不同结构(包括列表 2 中的结构)的第一个列表准备结构。仅当第二个列表中的 ID 未出现在第一个列表中时，才会启动这些函数。我不能操纵第一个列表，但我可以修改第二个列表。

我试过这种方法。在每次迭代中:

1. Create a std::unordered_set with hashed ids from second list. Then compare it to first list and remove outdated ids from first list. Remove also repeating ids from unordered_set. We'll end up with the set of new structures from list 2. We can run another functions and then add suitable ones to first list.

2. Sort list2 by ids. Then do binary search.

3. Linear search. 2 loops. Id that appears in first list and doesn't in the second one is removed from first list. Id that appears in both lists is removed from the second list. And finally we got ids that appear in second list and don't in the second one. We can process them and merge with list 1.

最重要的是:会有很多比较，但大多数时候列表是一样的!

Answer 1

最有效的方法可能是简单地将第二个列表分配给第一个列表:

first = second;

这将复制第二个的所有元素并将它们放在第一个。

如果出于某种原因您需要将元素保留在原位，您可以对每个列表进行排序并使用 set_difference查找一个列表中不在另一个列表中的所有元素的算法。