c++ - 将一组字符串与一个字符串进行比较的最快方法是什么？

Question

我有一组字符串，我需要查找其中是否有一个特定的字符串。我只需要执行一次(下次字符串不同)。

我正在考虑使用桶排序对字符串进行排序，然后进行二分搜索。

时间复杂度:O(n+k)+O(log n)

有没有更快/更好的解决方案？

对于 set，我的意思是更多的字符串，而不是 std::set。

Answer 1

在答案中总结上述评论。如果您正在加载要即时比较的字符串并且不需要它们按特定顺序排列，那么 std::unordered_set 是迄今为止最快的。

unordered_set 是一个哈希集，它将通过哈希函数对字符串进行打洞，并在恒定时间 O(1) 内查找它是否已在集合中。

如果您需要保留元素的顺序，那么问题就变成了保留 vector 并对其进行线性搜索哪个更快，或者是否仍然值得构建哈希集。

代码:

std::unordered_set<std::string> theSet;

// Insert a few elements.
theSet.insert("Mango");
theSet.insert("Grapes");
theSet.insert("Bananas");

if ( theSet.find("Hobgoblins") == theSet.end() ) {
    cout << "Could not find any hobgoblins in the set." << endl;
} 

if ( theSet.find("Bananas") != theSet.end() ) {
    cout << "But we did find bananas!!! YAY!" << endl;
}

比较:

如果您使用std::vector，您将需要 O(n) 时间构建 vector ，然后需要 O(n) 时间查找元素。

如果你使用std::unordered_set，你仍然需要 O(n) 时间来构建 vector ，但之后你可以在常数时间 O(1) 内找到一个元素。