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

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?

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.

Yes! You can do it in O(nlogn) time complexity. Sort the second vector, which takes O(nlogn) time. for each element in first vector, find corresponding element in second one using binary search (STL has binary_search algorithm) and merge data to the element in first vector. for each element in first vector, we are spending O(logn) time. So the running time complexity of this approach is O(nlogn).

If your lists don't change often, you can sort both lists and then do the merge in linear time by simply walking both lists.

If your lists are changing all the time, you're probably better off making the "small" container sorted, such as map or set. In that case just use find on the set for each item in the big list you want to join.