c++ - 协调两个列表

Question

所以我有两个不同的列表，它们具有不同的格式和结构，需要进行协调。本质上，集合 B 需要与集合 A 中的内容相匹配，但我想保留集合 B 中现有项目的状态，而不是用集合 A 中的内容覆盖它们。

供引用，列表实际上并不意味着列表。 “列表”有几种不同的形式，从直接数组到映射。全部使用标准迭代器来访问元素。

我一般的处理方式是这样的...

for item in listA
  if listB contains item
     mark item in list B as visited
  else 
     add item to list b

 for item in listB
   if visited is true
      continue
   else
       add item to removeList

 for item in removeList
    remove item from list B

这行得通，而且是我能想到的唯一可行的方法。我不喜欢我必须做多少次迭代，让三个 for 循环背靠背感觉不对。但是，由于我使用的是迭代器，因此在检查列表时无法从列表中删除任何内容，而是必须将它们添加到第三个删除列表中。

在可能的答案中，请记住速度和内存占用对我来说比编写代码的难易程度更重要。

我的问题实际上归结为这个——是否有我没有想到的更好的方法来做到这一点？

我在 C++/C FWIW，尽管我认为任何解决方案都可能与语言无关。

谢谢!

Answer 1

这是另一种可能更有效的方法:

removeList = listB

for item in listA
  if listB contains item
    remove item from removeList
  else
    add item to listB

for item in removeList
  remove item from listB

因此，它不是从无到有地构建 removeList，而是从所有内容开始，然后从中删除项目。

您还可以通过让 removeList 存储索引而不是实际项目来提高效率。只要在初始循环中将项目添加到 listB 的末尾，并以相反的顺序删除项目，索引应该仍然有效。

事实上，如果您将 removeList 替换为要保留的项目的 bool 数组，它甚至会更简单。所以算法变成了这样:

initialise all itemsToKeep to false
savedListLength = length of listB

for item in listA
  offset = find item in listB
  if found
    mark itemsToKeep[offset] as true
  else
    add item to listB

for offset from savedListLength-1 down to 0
  if itemsToKeep[offset] is false
    remove the offset from listB

这避免了最初将任何内容复制到 removeList 中的需要。 itemsToKeep 数组的开销肯定不会比您用来跟踪算法中已访问项的任何内容差。

在某种程度上，最合适的算法可能取决于列表的形式(即 vector 或链表等)，但我确实认为我的方法有可能在任何一种方式中都更加有效。