Compare List/set elements

Question

I'm looking to compare two sets and display the missing elements in second set by iterating over the first set.

I've done using lists but it seems like an overhead iterating over the unordered list to find the elements.

#include <iostream>
#include <list>
using std::list;

bool isExist(list <int> &original, int i)
{
 list <int>::iterator iter;

 for (iter = original.begin(); iter != original.end(); iter++)
 {
  if (*iter == i) {
   original.splice(original.end(), original, iter);
   return true; }
 }
 return false;
}

void FindMissing(list <int> &original, list <int> &missing)
{
 int count_exist = 0;

 list <int>::iterator iter;

 for (iter = missing.begin(); iter != missing.end(); iter++)
 {if (isExist(original, *iter))
  count_exist++;}

 int count_missing = original.size() - count_exist;

 iter = original.begin();

 while(count_missing > 0)
 {
  std::cout << *iter++ << std::endl;
  count_missing--;
 }
}

int main()
{
 list <int> list_data_1;
 list <int> list_data_2;

 //Fill the list.
 for (int i = 0; i < 5; i++)
 list_data_1.push_back(i);

 //Fill second list with missing elements.
 list_data_2.push_back(3);
 list_data_2.push_back(1);
 list_data_2.push_back(4);

 FindMissing(list_data_1, list_data_2);
}

How would you do the same with set?

Answer 1

If you have two sets:

std::set<int> s1;
std::set<int> s2;

and you want to get the set of elements that are in one but not the other, you can use std::set_difference:

std::set<int> difference;
std::set_difference(s1.begin(), s1.end(),
                    s2.begin(), s2.end(),
                    std::inserter(difference, difference.begin()));

difference will contain all of the elements that are in s1 but not in s2.

std::set_difference works for any two sorted ranges, so you could use it with other containers as well (e.g., if your std::lists were sorted, you could use std::set_difference on them to find the difference).