矢量差异，同时保持秩序

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

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

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

Answer 2

手册溶液：

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