保持顺序的向量差异
Vector difference while preserving order
我有两个 char
向量说 {'G', 'K', 'A', 'L', 'P'}
和 {'K', 'P', 'T', 'M'}
。我必须在保留顺序的同时获得这两个向量之间的差异,即 {'G', 'A', 'L'}
.
我知道 std::set_difference
函数,但无法使用,因为这需要对向量进行排序。在 C++ 中是否有任何优化的方法来执行此操作?
您可以仅从第二个向量创建一个 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
元素在集合中如果找到:
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(), ...
会做相反的事情,但它也会给你反向输出。
手动解决方案:
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)
}
}
我有两个 char
向量说 {'G', 'K', 'A', 'L', 'P'}
和 {'K', 'P', 'T', 'M'}
。我必须在保留顺序的同时获得这两个向量之间的差异,即 {'G', 'A', 'L'}
.
我知道 std::set_difference
函数,但无法使用,因为这需要对向量进行排序。在 C++ 中是否有任何优化的方法来执行此操作?
您可以仅从第二个向量创建一个 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
元素在集合中如果找到:
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(), ...
会做相反的事情,但它也会给你反向输出。
手动解决方案:
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)
}
}