4

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

3
  • 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? May 29, 2012 at 20:37
  • 7
    The standard algorithms provide set_difference...
    – K-ballo
    May 29, 2012 at 20:38
  • @ CrazyJugglerDrummer: I dont care about the order May 29, 2012 at 20:39

4 Answers 4

5

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.

0
3

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

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.

1
  • 1
    If you have duplicates, use unordered_map to keep a count of occurrences. May 29, 2012 at 20:45
0

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"));
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.