How to get the difference of two vectors A - B

Question

How would one find the difference between sets in C++ using Vector A and Vector B. I figured out the Union and Intersection but for some reason can not get the difference no matter what I try. Any help would be appreciated (BTW I need it to be done manually not using a built in method.)

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <fstream>
#include <algorithm>

using namespace std;

void Difference();

int main()
{
    Difference();

    return 0;
}


void Difference()
{
    int temp = 0;
    vector<int> D{};
    vector<int> A{3, 4, 9, 12, 13, 15};

    vector<int> B{1, 3, 5, 7, 9};

    for(int i = 0; i < A.size(); i++)
    {
        for (int j = 0; j < B.size(); j++)
        {

            if (A[i] != B[j])
            {
                int temp = A[i];
                D.push_back(temp);
            }


                  //Used To Sort The Vector So There Is No Duplicates And Its In Order!
                  sort( D.begin(), D.end() );
                  D.erase( unique( D.begin(), D.end() ), D.end() );
        }

    }
    cout << "Difference: ";
    for(int z = 0; z < D.size(); z++)
    {
        cout << D[z] << " ";
    }
}

Answer 1

if (A[i] != B[j])
{
    int temp = A[i];
    D.push_back(temp);
}

You should realise that this will add A[i] to the vector D for every single element of B that A[i] is not equal to. So, unless B consists only of identical elements, everything in A will make it across to D. In more detail, the operation {3, 4, 9} - {1, 3} will:

• add 3 once (because it's not equal to 1);
• add 4 twice (because it's equal to neither 1 nor 3); and
• add 9 twice (because it's equal to neither 1 nor 3).

Hence, after duplicate removal, you'll end up with {3, 4, 9} despite the fact the 3 is in both vectors.

---

What you need to do is check if any element matches, not every element as your current code does. That could be done with the following loop:

// For each element in A.

for(size_t i = 0; i < A.size(); i++) {
    // Start by assuming not in B, then check every B.

    bool contains = false;
    for (size_t j = 0; j < B.size(); j++) {
        // If found in B, exit early and save that fact.

        if (A[i] == B[j]) {
            contains = true;
            break;
        }
    }

    // If it was not found in B, add it to D.

    if (! contains) {
        int temp = A[i];
        D.push_back(temp);
    }
}

That way, you also don't have to worry about duplicate removal, unless there are duplicates in the original vectors. If that's the case, you'll probably need some more intelligence in your original algorithm (and this one) to handle the difference between (for example) {1, 2, 3, 3, 3} and {3}. In other words, should that be {1, 2} or {1, 2, 3, 3}?

Answer 2

#include <algorithm>
#include <iostream>
#include <vector>

void sort_and_unique(std::vector<int> &vec) {
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

std::vector<int> difference(std::vector<int> a, std::vector<int> b) {
  sort_and_unique(a);
  sort_and_unique(b);
  std::vector<int> res;
  size_t left = 0, right = 0;
  while (left < a.size() && right < b.size()) {
    if (a[left] < b[right]) {
      res.emplace_back(a[left++]);
    } else if (a[left] == b[right]) {
      left++;
      right++;
    } else {
      right++;
    }
  }
  while (left < a.size()) {
    res.emplace_back(a[left++]);
  }
  return res;
}

int main() {
  std::vector<int> A{3, 4, 9, 12, 13, 15};
  std::vector<int> B{1, 3, 5, 7, 9};
  std::vector<int> res = difference(A, B);
  for (int x : res) {
    std::cout << x << ' ';
  }
  std::cout << std::endl;
  return 0;
}

This is a O(nlogn) method, which also remove duplicate elements. The key point is to take advantage of the ordering. Using two-pointer method can help make it.

If the input is reliable(every element is unique in its own vector), you can omit the vec.erase line.