矢量差异,同时保留顺序

Question

我有两个char载体说{'G', 'K', 'A', 'L', 'P'}和{'K', 'P', 'T', 'M'}.我必须在保留顺序的同时得到这两个向量之间的差异{'G', 'A', 'L'}.

我知道std::set_difference函数但不能使用,因为这将需要对向量进行排序.有没有优化的方法在C++中执行此操作？

Answer 1

您可以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;
}

住在Coliru

如果你只想减去在第二个向量中找到的值的数量,那么重新使用它std::multiset,erase如果找到了该组中的元素:

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(), ...

会做相反的事情,但它也会给你逆转输出.