保持顺序时的向量差

Question

我有两个char向量，分别是{'G'、'K'、'A'、'L'、'P'}{'K'，'P'、'T'、'M'}。我必须得到这两个向量之间的差异，同时保持顺序，即{'G'，'A'，'L'}。

我知道std::set_difference函数，但不能使用，因为这需要对向量进行排序。在C中有什么优化的方法吗？

Answer 1

手动解决方案：

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

Answer 2

您可以仅从第二个向量生成一个std:：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;
}

在科利鲁生活

如果您只想减去在第二个向量中找到的值的数量，请使用 std：：multiset 重新制作，如果找到，您还可以擦除集合中的元素：

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

请注意，以上内容将删除第一次出现的内容并保留以后出现的内容。

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

会做相反的事情，但它也会给你反向输出。