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

Question

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

Answer 1

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

Answer 2

Yes! You can do this in O (nlogn) time complexity. Sort the second vector that takes O (nlogn) time. for each element in the first vector, find the corresponding element in the second using binary search (STL has the binary_search algorithm) and combine the data with the element in the first vector. for each element in the first vector we spend time O (logn). Therefore, the runtime complexity of this approach is O (nlogn).

Answer 3

If your lists do not change often, you can sort both lists and then merge in linear time simply by going through both lists.

If your lists change all the time, you probably would be better off sorting a “small” container, like map or set . In this case, just use find in the set for each item in the large list that you want to join.