c++ - 保持顺序的 vector 差异

Question

我有两个 char vector {'G', 'K', 'A', 'L', 'P'} 和 {' K'、'P'、'T'、'M'}。我必须在保留顺序的同时获得这两个 vector 之间的差异，即 {'G', 'A', 'L'}。

我知道 std::set_difference 函数，但不能使用它，因为它需要对 vector 进行排序。在 C++ 中是否有任何优化的方法来执行此操作？

Answer 1

您可以仅从第二个 vector 创建一个 std::set 以获得对数查找复杂度，然后遍历第一个 vector ，如果元素未找到则推送到结果 vector 在集合中:

#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

如果你想只减去第二个 vector 中找到的值的数量，用std::multiset重新做这个，你也erase code> 集合中的元素(如果找到):

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

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