search withing a big vector in C++

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.

I know I can do a for loop and do the check. However considering size difference I am looking for a smart and efficient way to do so.