在C++中的大向量内搜索

Question

我有以下向量:

std::vector<A*> vec;
std::vector<std::pair<A*, A*>> vec_pair;

vec_pair的大小远远大于vec的大小.我想在vec_pair中找到一对,其中两个成员都在vec内部.

这些内容vec_pair是不变的.然而,在每次迭代之后,内容vec会改变,我想再次进行测试.

我知道我可以做一个for循环并做检查.然而,考虑到工作的大小差异和复发,我正在寻找一种智能而有效的方法来实现它.

Answer 1

如果您不打算更改 的内容vec，请创建std::unordered_set<A*>具有相同内容的 并在其中搜索出现的情况。在 an 中搜索unordered_set大约是 O(1)，所以这将是一个简单的胜利。

unordered_set从 a构造 an 的最简单且最有效的方法vector是使用带有两个迭代器的构造函数：

unordered_set<A*> us(vec.begin(), vec.end());