C++比较2个字符串列表

Question

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

这是区分大小写的匹配.

Answer 1

可以使用数据类型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_set和dense_hash_set)创建的实现.对于各种其他实现和基准(包括一个用于字符串),请参见此处.