How to do a left join with STL vector and STL algorithms with time complexity better than O(n^2)?

Question

I have 2 vectors, which contain, let's say Person (name, surname, etc) objects. I want to take one of the vectors (let's name it "large") then for each element in this vector find corresponding element in second one ("small") and merge some data from "small" vector element to the "large" vector element. This operation is very similar to left join in SQL terms, but with additional merge of the data. The easiest way is to make 2 cycles, but that will lead to O(n^2) time complexity. Can I do better with STL algorithms?

Answer 1

If you sort the small vector, you can then get O(n log n) for the merge portion by scanning the large vector and use binary_search to find elements in the small vector.