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

Answer 3

Thanks to @WhiZTiM for the great code example.

For my application it had some issues:

• only applicable to vectors
• removes duplicates from a although they are not in b
• does not pay attention to const correctness

This suggested variation deals with those issues.

template <typename ContainerT>
void remove_intersection(ContainerT& a, ContainerT& b)
{
    std::unordered_set<ContainerT::value_type> const uniqueAs { a.cbegin(), a.cend() };
    std::unordered_multiset<ContainerT::value_type> st { uniqueAs.cbegin(), uniqueAs.cend() };

    st.insert(b.begin(), b.end());
    auto const predicate = [&st](ContainerT::value_type const& k) { return st.count(k) > 1; };
    a.erase(std::remove_if(a.begin(), a.end(), predicate), a.cend());
    b.erase(std::remove_if(b.begin(), b.end(), predicate), b.cend());
}

Answer 4

I might try something like the following.

// Create sets from vectors. This eliminates the duplicate elements.
const unordered_set<int> setA{vecA.cbegin(), vecA.cend()};
const unordered_set<int> setB{vecB.cbegin(), vecB.cend()};

PopulateSetDiff(vecA, setA, setB);
PopulateSetDiff(vecB, setB, setA);

// Populate 'vec' with 'set1 - set2'
template <typename T>
void PopulateSetDiff(
  vector<T>& vec,
  unordered_set<T> const& set1,
  unordered_set<T> const& set2) {
  vec.clear();
  for (const auto elem : set1) {
    if (set2.find(elem) == set2.cend()) {
      vec.push_back(elem);
    }
  }
  vec.shrink_to_fit();
}

Answer 5

for (auto& d : deleteCommands) {
    auto it = stackCommands.begin();
    while (it != stackCommands.end()) {

        if (d == *it._Ptr) {

            commands[d]->Exit(this);

            it = stackCommands.erase(it);
        }

        else { it++; }
    }
}