在std :: set中查找std :: vector的元素

Question

我有两个容器std::set和std::vector，我的任务是返回中存在的std::vector中的元素。什么是最有效的方法来实现它？ 简单解决方案： 遍历矢量元素，并在每个元素上调用set.find，然后vector.erase，如果未找到。

Answer 1

你可以使用更多的STL :)

#include <algorithm> 
#include <set> 
#include <vector> 
#include <iostream> 
#include <iterator> 

int main() { 
    std::vector<int> v {5, 4, 3, 2, 1}; 
    std::set<int> s {1, 3, 5}; 

    v.erase(std::remove_if(v.begin(), v.end(), 
          [&s](int a) { return s.find(a) == s.end(); }), 
      v.end()); 

    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); 
} 

Answer 2

如何寻找每一个元素？如果您的载体没有排序，再有就是围绕n log(n)

#include <algorithm> 

std::vector<int> result; 
for(auto&& el: myvector) { 
    auto it_found = myset.find(el); 
    if(it != myset.end()) 
     result.push_back(*it_found); 
} 

没有办法现在result拥有所有那些在这两个元素。

PS：没有编译代码，可能会有轻微的错误。

Answer 3

您应该对矢量进行排序（如有必要，请保留原始索引，制作pair），然后使用binary search搜索矢量。这会更快。

或者您可以使用std::find方法，该方法可能会很慢。

Answer 4

最短路可能是用std::set_intersection。但是，你应该排序向量，使其工作：

int main() 
{ 
    std::set<int> s{1,2,3,4,5,6,7,8}; 
    std::vector<int> v{7,5,10,9}; 
    std::sort(v.begin(), v.end()); // should not bother you if vector is small 

    std::vector<int> intersection; 
    std::set_intersection(s.begin(), s.end(), v.begin(), v.end(), std::back_inserter(intersection)); 

    for(int n : intersection) 
     std::cout << n << ' '; 
} 

打印：5 7

Answer 5

根据集和载体的相对大小，可能的remove_if是正确的事情...

#include <set> 
#include <vector> 
#include <iostream> 
#include <algorithm> 

int main() 
{ 
    std::set<int> s{1,2,3,4,5,6,7,8}; 
    std::vector<int> v{7,5,10,9}; 

    v.erase(std::remove_if(v.begin(), v.end(), [&](int e){return s.count(e) == 0;}), v.end()); 


    for(int n : v) 
     std::cout << n << ' '; 
} 

Answer 6

如果你找最多CPU在复杂方面这样做的 - 有效方式，具有额外的内存和一个好的哈希函数，你能做到在O（N + M）：

std::vector<int> v; 
std::set<int> s; 
std::unordered_set<int> us{s.cbegin(), s.cend(), s.size()}; 

v.erase(
    std::remove_if(v.begin(), v.end(), 
     [&us] (const int entry) { return us.find(entry) == us.cend(); }), 
    v.end()); 

说明：您遍历您（O（m））准备unordered_set。然后你遍历你的vector一次（O（n）），每步执行unordered_set::find（0（1））。它给你O（n + m）的复杂性。

另外，unordered_set的大小等于set的大小，并且良好的散列函数有助于减少std::unordered_set::find的复杂性中的不变部分。

请参阅live example。

但是，请记住，较低的复杂度并不一定意味着在特定情况下执行速度更快（例如，由于额外分配）。