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

I want to be able to check if the string std::string x is equal to any value in string array std::string y[N]. I know how to do this by using a for loop and using an if statement, but is there an even faster way that I could do this? Is there a built in function in c++ that can do this?

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

2 个解决方案

#1

Presuming you use STL classes, there's a few mechanisms you can use, depending on the domain of your problem.

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

For example, if the array is unsorted, then it doesn't really matter: there are StdLib algorithms which will better convey intent and shrink the code, but they'll be performance-wise equivalent to a simple for-loop. This code is identical, performance-wise, to a simple for-loop.

例如,如果数组未排序,那么它并不重要:有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;

If the collection is sorted, you can use a Binary Search, which dramatically improves performance:

如果对集合进行了排序,则可以使用二进制搜索,从而显着提高性能:

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;

If you don't need duplicate strings in your collection, you can use a set or unordered_set to collect the strings, which will guarantee at least the performance of a binary-search, and if you use unordered_set instead, could be faster.

如果您的集合中不需要重复的字符串,则可以使用set或unordered_set来收集字符串,这至少可以保证二进制搜索的性能,如果使用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;

#2

The built-in container for that is std::unordered_set<std::string>

用于它的内置容器是std :: unordered_set

Replace your string array with that unordered_set, and the checks will become much faster:

用unordered_set替换你的字符串数组,检查会变得更快:

bool contains( const std::unordered_set<std::string>& set, const std::string& s )
{
    return set.find( s ) != set.end();
}

#1