Vector difference while keeping order

Question

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

I know about the function std::set_difference, but it is impossible to use, since this will require sorting vectors. Is there an optimized way to do this in C ++?

Answer 1

You can std::setonly do it from the second vector to get the complexity of a logarithmic search, and then iterate over the first vector by clicking on 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 , redo this with std::multiset, where you are also erasean 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 the first occurrences and keep the later ones.

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

will do the opposite, but it will also give you the opposite result.

Answer 2

Manual solution:

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

for(auto const& item:a){
   if(std::find(std::begin(b),end(b),item)==std::end(b)){
       result.push_back(item)
   }
}