Remove all the elements that occur in 1 list from another c++

Question

Let's say I have two lists, l1 and l2. I want to perform l1 - l2, which returns l1 with any elements that are also elements of l2 removed.

I can think of a naive loop approach to doing this, but that is going to be really inefficient. What is an efficient way of doing this in c++?

As an example, if I have l1 = [1,2,6,8] and l2 = [2,8], l1 - l2 should return [1,6]

thanks you guys

Answer 1

Does the order matter? Will the list contain duplicates?

If not I'd recommend doing a set_difference

Just a heads up though, if you do have duplicates, I think set_difference only removes the first occurrence of the duplicated elements you want to remove.

Answer 2

You can do this in amortized linear time with a hash set.

First, create an empty set, H. Loop over L1 and insert each element into H.

Then, loop over L2. For each element of L2, append to a vector if and only if that element is not in H.

If H provides constant-time insertion and access, and you use a constant-time-append structure to store your temporary result, the overall algorithm is linear in the sum of the lists' sizes.