c++ - 如何使用时间复杂度优于 O(n^2) 的 STL vector 和 STL 算法进行左连接？

Question

我有 2 个 vector ，其中包含 Person(名字、姓氏等)对象。我想取其中一个 vector (我们将其命名为“大”)，然后针对该 vector 中的每个元素在第二个 vector (“小”)中找到相应的元素，并将一些数据从“小” vector 元素合并到“大” vector 元素。此操作与 SQL 术语中的左连接非常相似，但具有额外的数据合并。最简单的方法是进行 2 个循环，但这会导致 O(n^2) 时间复杂度。我可以使用 STL 算法做得更好吗？

Answer 1

如果你sort小 vector ，然后您可以通过扫描大 vector 并使用 binary_search 获得合并部分的 O(n log n)查找小 vector 中的元素。