C/C++ - 比较两个列表并查找缺失元素的有效方法

Question

我有两个列表， L ₁和 L ₂，包含多个元素的数据列表，每个元素都是抽象数据类型（即：）structs。两个列表中的每一个：

• 可能包含零到一百（含）元素。
• 不包含重复元素（每个元素都是唯一的）。
• 可能包含也可能不包含其他列表中的元素（即：L ₁和 L ₂可能相同，或包含完全不同的元素）。
• 没有排序。
• 在最低级别，与std::vector<myStruct>容器一起存储。

我通常期望的是，定期向 L ₂添加一个新元素，或者从中减去/删除一个元素。我试图尽可能有效地检测两个列表中的差异（即：用最少的比较）：

• 如果条目不存在以L ₂和L是本₁，执行一个操作：Handle_Missing_Element()。
• 如果条目存在于 L _{2 中但}不存在于 L _{1 中}，则执行另一个操作：Handle_New_Element()。

一旦执行了上述检查，L _{1 就}被设置为等于L ₂，并且在将来的某个时间再次检查L ₂。

我怎样才能找出两个列表之间的差异？我能想到的有两种方法：

1. 通过每个可能的元素组合比较两个列表。可能是 O(n ² ) 执行复杂度（可怕）。

---

bool found;
for i in 1 .. L2->length()
  found = false;
  for j in 1 .. L1->length()
    if (L1[j] == L2[i]
      // Found duplicate entry
      found = true;
    fi
  endfor
endfor

2. 对列表进行排序，并按元素比较两个列表，直到找到差异为止。这似乎是接近线性的时间。问题是我需要对列表进行排序。在每次添加/删除列表后手动对底层向量进行排序是不切实际的。如果有可能以某种方式强制vector::push_back()自动插入元素，这样插入就会阻止列表的排序，那么这样做才是合理的。

有没有一种直接的方法可以在 C++ 中有效地完成这个任务？我发现了类似的问题，但我需要做的不仅仅是找到两个集合的交集，或者只用一组整数进行这样的测试，其中可以使用与总和相关的技巧，因为我需要执行“新”与“缺失”元素的不同操作。

谢谢你。

Answer 1

在每次添加/删除列表后手动对基础向量进行排序是不切实际的。只有当能够以某种方式强制vector::push_back()自动插入元素以使插入保留列表的排序时，这样做才是合理的。

您在这里谈论的是有序插入。有一些功能<algorithm>可以让你这样做。std::vector::push_back您可以使用std::vector::insert, 并调用它，而不是使用它，它对不小于给定值的std::lower_bound第一个元素进行二分搜索。

auto insert_pos = std::lower_bound( L2.begin(), L2.end(), value );
if( insert_pos == L2.end() || *insert_pos != value )
{
    L2.insert( insert_pos, value );
}

这使得每次插入的时间复杂度为O(logN)，但如果您在定期检查之间执行的插入次数少于 N，那么这应该是一个改进。

压缩操作可能如下所示：

auto it1 = L1.begin();
auto it2 = L2.begin();

while( it1 != L1.end() && it2 != L2.end() )
{
    if( *it1 < *it2 ) {
        Handle_Missing( *it1++ );
    } else if( *it2 < *it1 ) {
        Handle_New( *it2++ );
    } else {
        it1++;
        it2++;
    }
}

while( it1 != L1.end() ) Handle_Missing( *it1++ );
while( it2 != L2.end() ) Handle_New( *it2++ );