在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。

但是，請記住，較低的複雜度並不一定意味着在特定情況下執行速度更快（例如，由於額外分配）。