c++: Remove Elements that are in one vector from another

Question

I need to remove the elements that appear in Vector A and Vector B, but keep the elements that are only in Vector A. The vectors can be of any size, but are not necessarily equal to each other.

For example, if: vector A contains the values <1,4,66,22> vector B contains the values <1,22,44,93,102,543>

Then after preforming the operation: vector A should contain <4,66> vector B should contain <44,93,102,543>

Do I need to loop through both with a for loop and strncmp the values or is the a function that I can use to streamline the process? This is what I tried but doesn't seem to work.

string rawInput;
string fileInput;
vector<string> stdInput; //vector to hold standard input values
vector<string> fileList; //vector to hold file values   

sizeIn = stdInput.size();
sizeFile = fileList.size(); 

if (sizeIn >= sizeFile)
    {
        for (count = 0;count <= sizeIn; count++)
        {
            for (count1 = 0; count1 <= sizeFile; count1++)
            {
                if (stdInput[count1] == fileList[count])
                {
                    stdInput.erase(stdInput.begin()+count1-1);
                    fileList.erase(fileList.begin()+count-1);

                }

            }
        }
    }
    else
    {
        for (count = 0; count <= sizeFile; count ++)
        {
            for (count1 = 0; count1 <= sizeIn; count1++)
            {
                if (stdInput[count] == fileList[count1])
                {
                    stdInput.erase(stdInput.begin()+count-1);
                    fileList.erase(fileList.begin()+count1-1);

                }   
            }
        }
    }

Answer 1

That's a lot of work there. I would have suggested std::set_difference, but since you want to do it in place, this code will do it for you with good algorithmic complexity:

template<typename T>
void remove_intersection(std::vector<T>& a, std::vector<T>& b){
    std::unordered_multiset<T> st;
    st.insert(a.begin(), a.end());
    st.insert(b.begin(), b.end());
    auto predicate = [&st](const T& k){ return st.count(k) > 1; };
    a.erase(std::remove_if(a.begin(), a.end(), predicate), a.end());
    b.erase(std::remove_if(b.begin(), b.end(), predicate), b.end());
}

Isn't C++ beautiful? :-)

---

A Demo:

int main(){
    std::vector<int> a = {1,4,66,22};
    std::vector<int> b = {1,22,44,93,102,543};

    remove_intersection(a, b);

    for(auto k : a) std::cout << k << ' ';
    std::cout << std::endl;
    for(auto k : b) std::cout << k << ' ';
}

Outputs:

4 66 
44 93 102 543 

See it Live On Coliru

There are many variations of the above method. For example, if you are worried that count may take too long when such count is really large, you can implement a simple function to find and count up to at most 2 elements; another one: you can simply use two different unordered sets.

Answer 2

No, I will resort them via sort(fileList.begin(), fileList.end() ); after

So asymptotically it's the same to sort before.

Using set_difference, you can do something like:

template<typename T>
void remove_intersection(std::vector<T>* c1, std::vector<T>* c2) {
  assert(c1 != nullptr);
  assert(c2 != nullptr);

  std::sort(std::begin(*c1), std::end(*c1));  // O(n1 logn1)
  std::sort(std::begin(*c2), std::end(*c2));  // O(n2 logn2)

  std::vector<T> difference1, difference2;
  difference1.reserve(c1->size());
  difference2.reserve(c2->size());

  std::set_difference(std::begin(*c1), std::end(*c1),
                      std::begin(*c2), std::end(*c2),
                      std::back_inserter(difference1));
  // O(2*[N1 + N2 - 1])

  std::set_difference(std::begin(*c2), std::end(*c2),
                      std::begin(*c1), std::end(*c1),
                      std::back_inserter(difference2));
  // O(2*[N1 + N2 - 1])

  *c1 = std::move(difference1);  // O(1)
  *c2 = std::move(difference2);  // O(1)
}