CODEWITHSUNDEEP
c++stl
wrhall
wrhall

Reputation: 1308

Set subtraction given two sorted vectors

If I have two vectors values and bad_values, is there a clean and effective way to efficiently subtract the bad values without writing my own for loop?

I know I could use

void set_subtraction(std::vector<int>* values, std::vector<int>* bad_values) {
    std::remove_if(values->begin(), values->end(), [bad_values](int x) {return std::find(bad_values->begin(), bad_values->end(), x) != bad_values->end()}
}

But that seems less readable than just writing out a loop and doesn't take advantage of both lists being sorted. It's also O(n^2) for what that's worth [although that's easily remedied by using a set for bad_values].

It's safe to assume that both vectors contain only distinct elements.

Upvotes: 0

Views: 183

Answers (1)

Steephen
Steephen

Reputation: 15854

Here you go with an example

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


int main()
{
  std::vector<int> vec1={1,2,3,4};
  std::vector<int> vec2={1,2};
  std::vector<int> result;
  std::set_difference(std::begin(vec1),std::end(vec1), 
                      std::begin(vec2),std::end(vec2), 
                      std::back_inserter(result));


 for (auto &x : result)
    std::cout<< x<<"\n";
}

Upvotes: 1

Related Questions