保留顺序的向量差异

Question

我有两个字符向量，例如{'G', 'K', 'A', 'L', 'P'}和{'K', 'P', 'T', 'M'}。我需要在保留顺序的情况下获取这两个向量之间的差异，即{'G', 'A', 'L'}。

我知道std::set_difference函数，但不能使用它，因为它要求向量已排序。是否有优化的方法在C++中执行此操作？

- Oliver Blue

---

{A, B, C, A, B, C} 和 {B, A} 的结果会是什么？ - Jarod42

我两个列表中没有重复元素，并且顺序应与第一个列表保持一致。 - Oliver Blue

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

如果你想要“仅减去第二个向量中找到的值的数量”，请使用 std::multiset 重新制作，并在其中使用erase删除找到的元素：

在Coliru上查看实时效果

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

反转函数会使输出结果倒置，但它同时也会给你一个反转后的输出。

- LogicStuff

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

- Humam Helfawi

---

这是O(n^2)。我认为这是最不优化的方法。 - NathanOliver

是的，这只是一种明确（可能不太干净）的方法。我知道这根本不会被接受。但我认为对于以后来到这个问题的任何初学者都应该提到它。 - Humam Helfawi