3
votes

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

4
You could sort both lists first, which would make the removal process much faster. Do you care about the ordering of items in the returned list?Gordon Gustafson
The standard algorithms provide set_difference...K-ballo
@ CrazyJugglerDrummer: I dont care about the orderזאבי כהן

4 Answers

4
votes

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.

3
votes

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.

1
votes

The naive approach takes O(n^2), because you have to compare each element form the first list with each element form the second list.

A slightly better approach is to sort the lists (O(n*log(n))) and then iterate through them. If they are sorted, you only need one pass, so time is O(n*log(n)).

An even better approach is to insert all elements of the second list in a std::unordered_set (O(n)), iterate through each of the elements of the first list (O(n)) and check if it's contained in the set (O(1) amortized time). This should do it. - This works only if you have no duplicates.

0
votes

If you want to do it the O(n^2) naive way for the unsorted case you can do that with a little bit of <algorithm> and std::bind (or boost if that's not an option) trickery:

#include <list>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>

int main() {
  std::list<std::string> a = {"foo", "bar", "baz", "woof"},
                         b = {"baz", "bar", "random other thing"};

  a.erase(std::remove_if(a.begin(), a.end(), std::bind(std::equal_to<std::list<std::string>::iterator>(), b.end(), std::bind(std::find<std::list<std::string>::iterator, std::string>, b.begin(), b.end(), std::placeholders::_1))), a.end());

  std::copy(a.begin(), a.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}