C++ get the difference between two vectors

Question

imagine you got 2 vectors:

vector<int> ar1, a2;

ar1 = {1,1,2,3,3,4,5,5,6};
ar2 = {1,2,3,4,5,6};

how to do something like this in a good way (using C++) ?

b = ar1 - ar2
// b = {1,3,5}

Georginageorgine

Did you try anything yet? – Blisse

What do you mean "like this"? What is that supposed to mean? – Gumm

std::set_difference – Persevering

@RichardWieditz set_difference has not the behavior described in your post! – Mike

@RichardWieditz But if you needed std::set_difference then what is "vector without other vector" supposed to mean? – Caspar

@Columbo: Are you sure it's wrong? Demo at ideone.com – Persevering

@Persevering I didn't read the reference properly, i.e. "Equivalent elements are treated individually", pardon me. – Mike

If the second vector has a 7 in it what is supposed to happen? – Repurchase

i don't see why set_difference is wrong – Arnica

what is the unclear part of the question ? I got a vector {1,2,3} and another vector {1,2}. I want to do {1,2,3} - {1,2} giving me a {3} as result. – Georginageorgine

@RichardWieditz, Probably the fact that the first one has duplicates. – Hugibert

duplicates means in this case ... ? – Georginageorgine

Answer 1

//from cppreference
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
 
int main() {
 
    std::vector<int> v1 {1,1,2,3,3,4,5,5,6};
    std::vector<int> v2 {1,2,3,4,5,6};
    std::vector<int> diff;
    //no need to sort since it's already sorted
    //but you can sort with:
    //std::sort(std::begin(v1), std::end(v1))

    std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
        std::inserter(diff, diff.begin()));
 
    for (auto i : v1) std::cout << i << ' ';
    std::cout << "minus ";
    for (auto i : v2) std::cout << i << ' ';
    std::cout << "is: ";
 
    for (auto i : diff) std::cout << i << ' ';
    std::cout << '\n';
}

Arnica

I want to up-vote this post, but i cant ! This is exactly what i wanted to do ! – Georginageorgine

Meh - it's an example from cppreference, so not really worth upvoting! – Arnica

cppreference is the reference I want to use ? – Georginageorgine

if i google a std::anything.. always seems to be cppreference that comes up first. I've found them pretty useful – Arnica

@RichardWieditz: cppreference.com and cplusplus.com are the two most common non-official references. Many of us prefer cppreference.com. cplusplus.com used to have a less than stellar reputation but has gotten better over time. – Persevering

Absolutely right - set_difference requires sorted vectors. Most of the related std algo's require just that. Performing the same operation on unsorted vectors you could populate a std::set with the contents of both vectors and then do a size comparison to verify if they are indeed the same. – Arnica

As a side note - Richard presents an example with sorted vectors - so the answer is perfectly reasonable for the question. Not sure why that deserves a downvote.. – Arnica

@GeorgeNewton you could also use std::multiset which allows multiple keys with equivalent values. – Acadian

Would not std::back_inserter be more appropriate for this example? – Siddon

this answer will not work in the case of an unsorted array. What to do in that situation?? – Wolfish

std::sort(std::begin(v1), std::end(v1)) – Arnica

This doesn't work if the vectors contain a type for which the < operator isn't overloaded. – Lordling

Answer 2

The accepted answer only works if you have sorted vectors of a type for which the < operator is overloaded.

If you have a type for which the < operator is overloaded but the vectors aren't sorted, you need to sort them first:

#include <algorithm>
#include <vector>

std::vector<int> v1 {3,1,3,2,4,1,5,5,6};
std::vector<int> v2 {6,1,4,5,2,3};
std::vector<int> diff;
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::inserter(diff, diff.begin()));

If the < operator isn't overloaded, you can write your own comparator:

#include <algorithm>
#include <vector>

std::vector<SomeType> v1 {...};
std::vector<SomeType> v2 {...};
std::vector<SomeType> diff;
const auto cmp = [](const SomeType &a, const SomeType &b){
    //Should return true if a is considered strictly less than b
};
std::sort(v1.begin(), v1.end(), cmp);
std::sort(v2.begin(), v2.end(), cmp);
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::inserter(diff, diff.begin()), cmp);

However, if writing your own comparator is not trivial, it might be easier to simply write your own function to find the difference between the vectors:

#include <algorithm>
#include <vector>

template<typename T>
std::vector<T> vectorDifference(const std::vector<T> &v1, const std::vector<T> &v2){
    //Make the result initially equal to v1
    std::vector<T> result = v1;

    //Remove the elements in v2 from the result
    for(const T &element: v2){
        const auto it = std::find(result.begin(), result.end(), element);
        if(it != result.end()){
            result.erase(it);
        }
    }
    return result;
}

Lordling