c++ - 在两个容器 C++ 中搜索匹配项目

Question

我有一个关于如何有效地搜索两个容器以找到相同项目的问题。

例如，我有两个列表A、B，我想为列表A找出列表B中的所有匹配项目。

在这种情况下，我需要有两个循环，一个在另一个循环中。这不好，因为对于 A 的每个项目，我都在 B 中进行整体搜索。

您是否有一些想法或标准库(boost 可以)来解决它；)？

非常感谢!

Answer 1

你可以 std::sort() 容器然后使用 std::set_intersection() (我不完全确定这个算法的名称) .复杂度为 O(n ln n + m ln m) 而不是 O(n * m) with n 和 m 是序列的大小。