Vector difference while preserving order

Question

I have two char vectors say {'G', 'K', 'A', 'L', 'P'} and {'K', 'P', 'T', 'M'}. I have to get the difference between these two vectors while preserving the order i.e. {'G', 'A', 'L'}.

I am aware of std::set_difference function but that can't be used since that will require the vectors to be sorted. Is there any optimized way to do this in C++?

Answer 1

You can make a std::set only from the second vector to get logarithmic lookup complexity, then iterate through the first vector, pushing to the resulting vector if the element is not found in the set:

#include <iostream>
#include <vector>
#include <set>
#include <iterator>
#include <algorithm>

int main()
{
    std::vector<char> a = {'G', 'K', 'A', 'L', 'P'};
    std::vector<char> b = {'K', 'P', 'T', 'M'};
    std::vector<char> result;

    std::set<char> s(b.begin(), b.end());

    std::copy_if(a.begin(), a.end(), std::back_inserter(result),
                 [&s](char elem) { return s.find(elem) == s.end(); });

    for(auto elem : result)
        std::cout << elem << ", ";

    return 0;
}

Live on Coliru

If you want to subtract only the number of values found in the second vector, remake this with std::multiset, where you also erase the element in the set if found:

std::copy_if(a.begin(), a.end(), std::back_inserter(result), [&s](char elem)
{
    auto it = s.find(elem);

    if(it == s.end())
        return true;

    s.erase(it);
    return false;
});

Note that the above will remove first occurrences and keep later ones.

std::copy_if(a.rbegin(), a.rend(), ...

will do the opposite, but it will also give you reversed output.