C++比較2個字符串列表

在Python中，對比較2個字符串列表非常方便（請參閱link）。我想知道在性能方面是否有一個好的C++解決方案。每個列表中都有超過一百萬個字符串。C++比較2個字符串列表

區分大小寫的匹配。

來源

2012-09-12 Stan

使用的Python的C++模擬設置：性病::設置 – Yuushi

是列表排序？ –

該列表未被排序。目標是在兩個列表（交集）中找到匹配的字符串。 – Stan

數據類型std::set<>（通常實現爲平衡樹）和std::unordered_set<>（來自C++ 11，實現爲散列）可用。還有一種稱爲std::set_intersection的便利算法，用於計算實際交叉點。

這裏是一個例子。

#include <iostream> 
#include <vector> 
#include <string> 
#include <set>    // for std::set 
#include <algorithm>  // for std::set_intersection 

int main() 
{ 
    std::set<std::string> s1 { "red", "green", "blue" }; 
    std::set<std::string> s2 { "black", "blue", "white", "green" }; 

    /* Collecting the results in a vector. The vector may grow quite 
    large -- it may be more efficient to print the elements directly. */  
    std::vector<std::string> s_both {}; 

    std::set_intersection(s1.begin(),s1.end(), 
         s2.begin(),s2.end(), 
         std::back_inserter(s_both)); 

    /* Printing the elements collected by the vector, just to show that 
    the result is correct. */ 
    for (const std::string &s : s_both) 
    std::cout << s << ' '; 
    std::cout << std::endl; 

    return 0; 
}

注意。如果您想使用std::unordered_set<>，則不能像這樣使用std::set_intersection，因爲它需要對輸入集進行排序。你必須使用通常的for-loop技術迭代遍歷較小的集合，並找到較大集合中的元素來確定交集。儘管如此，對於大量元素（特別是字符串），基於散列的std::unordered_set<>可能會更快。也有STL兼容的實現，如Boost（boost::unordered_set）和Google創建的（sparse_hash_set and dense_hash_set）。對於各種其他實現和基準（包括一個字符串），請參閱here。

來源

2012-09-12 07:09:24 jogojapan

「一個for-loop遍歷較小的集合並在較大的集合中查找元素」 - 假設一個集合包含另一個集合中的所有元素......更典型的是，您希望/需要標記/記錄那些看到的元素通過另一組的第二個循環。另外值得注意的是，如果目標是將結果寫出來，那麼創建一個臨時's_both'集合會浪費內存，但這是一個很好的例子。 –

@TonyDelroy是的，將結果放入向量中可能會浪費。我會在帖子中添加一條評論，這是爲了說明目的。請注意，我瞭解其他評論。我認爲目標是找到交集（即元素兩個集合有共同點），因爲這是OP鏈接到的Python腳本的作用。對於集合交集，遍歷一個列表並搜索另一個列表就足夠了，即使其他列表不是第一個列表的超集。（當然這假設搜索另一個列表是有效的，如果列表是散列集則是這樣。 – jogojapan

@jogojapan：對不起夥伴 - 我只是閱讀「比較」，並沒有按照鏈接看到Python只是一個交集（誰想讀Python？; -P）。公平點然後，從我的+1。 –

如果您並不需要太多的表現，我建議用圖/來自STL設置：

list<string> list, list2; 
... 
set<string> sndList; 
list<string> result; 

for(list<string>::iterator it = list2.begin(); it != list2.end(); ++it) 
    sndList.insert(*it); 

for(list<string>::iteratir it = list.begin(); it != list.end(); ++it) 
    if(sndList.count(*it) > 0) 
     result.push_back(*it);

否則我建議一些散列函數進行比較。

來源

2012-09-12 07:07:11 Ari

如果它確實是一個std::list你，對它們進行排序，並使用set_intersection：

list<string> words1; 
list<string> words2; 
list<string> common_words; 

words1.sort(); 
words2.sort(); 

set_intersection(words1.begin(), words1.end(), 
       words2.begin(), words2.end(), 
       back_inserter(common_words));

來源

2012-09-12 13:42:28

C++比較2個字符串列表

回答

相關問題