How to get the difference of two vectors A - B

#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.

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}?