Si tes vecteurs sont triés, il suffit de faire un parcours simultané.

Regarde les exemples de std::merge sur cppreference.com pour avoir des idées.