Search within a big vector in C++

Question

I have following vectors:

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

vec_pair size is much more than vec size. I would like to find a pair within vec_pair which both members are inside vec.

contents of the vec_pair are constant. However after each iteration the contents of the vec will change and I would like to do the test again.

I know I can do a for loop and do the check. However considering size difference and recurrence of the job, I am looking for a smart and efficient way to do it.

Answer 1

If you are not going to change content of vec, create an std::unordered_set<A*> with the same content and search for occurrences there. Searching in an unordered_set is approximately O(1), so this would be a simple win.

The easiest and the most efficient way to construct an unordered_set from a vector is to use the constructor taking two iterators:

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