c++ - 检查字符串数组中是否存在字符串的最快方法是什么？

Question

我希望能够检查字符串 std::string x 是否等于字符串数组 std::string y[N] 中的任何值。我知道如何通过使用 for 循环和 if 语句来做到这一点，但是有没有更快的方法可以做到这一点？ C++ 中是否有内置函数可以执行此操作？

Answer 1

假设您使用 STL 类，您可以使用一些机制，具体取决于您的问题领域。

例如，如果数组未排序，那么这并不重要:有 StdLib 算法可以更好地传达意图和缩减代码，但它们在性能方面等同于简单的 for 循环。此代码在性能方面与简单的 for 循环相同。

std::vector<std::string> strings = /*...*/;
//This will find the first string that matches the provided value and return its iterator
auto found_string_iterator = std::find(strings.begin(), strings.end(), "Desired String");
if(found_string_iterator != strings.end()) //found it
    std::cout << *found_string_iterator << std::endl;
else //Did not find it
    std::cout << "No such string found." << std::endl;

如果集合已排序，您可以使用二分搜索，这会显着提高性能:

std::vector<std::string> sorted_strings = /*...*/;
//In a sorted collection, this returns iterators to all strings matching the provided value
auto string_range_iterators = std::equal_range(strings.begin(), strings.end(), "Desired String");
if(string_range_iterators.first != strings.end()) {
    for ( auto i = string_range_iterators.first; i != string_range_iterators.second; ++i )
        std::cout << *i << std::endl;
} else {
    std::cout << "No Strings found." << std::endl;

如果你的集合中不需要重复的字符串，你可以使用set或者unordered_set来收集字符串，这样至少可以保证a的性能二进制搜索，如果您改用 unordered_set，可能会更快。

std::set<std::string> collected_strings = /*...*/;
auto found_string_iterator = collected_strings.find("Desired String");
if(found_string_iterator != strings.end()) //found it
    std::cout << *found_string_iterator << std::endl;
else //Did not find it
    std::cout << "No such string found." << std::endl;