3

在 Python 中,set 对于比较 2 个字符串列表非常方便(请参阅此链接)。我想知道 C++ 在性能方面是否有一个好的解决方案。因为每个列表中都有超过 100 万个字符串。

这是区分大小写的匹配。

4

3 回答 3

9

数据类型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 循环遍历较小集合并在较大集合中查找元素以确定交集的常用技术。然而,对于大量元素(尤其是字符串),基于散列的std::unordered_set<>可能更快。还有与 STL 兼容的实现,例如 Boost ( boost::unordered_set) 中的实现和 Google 创建的 (sparse_hash_setdense_hash_set)。对于各种其他实现和基准(包括一个用于字符串的),请参见此处

于 2012-09-12T07:09:24.950 回答
0

如果您不需要太多性能,我建议使用 STL 中的 map/set:

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-12T07:07:11.313 回答
0

如果它确实是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-12T13:42:28.190 回答