c++ - 使用 std::vector<std::string> 的快速搜索算法

Question

    for (std::vector<const std::string>::const_iterator it = serverList.begin(); it != serverList.end(); it++)
    {
        // found a match, store the location
        if (index == *it) // index is a string
        {
            indexResult.push_back(std::distance(serverList.begin(), it)); // std::vector<unsigned int>
        }
    }

我已经编写了上面的代码来查看一个字符串 vector 并返回另一个包含任何“命中”位置的 vector 。

有没有办法做同样的事情，但速度更快？ (如果容器中有 10,000 件元素，则需要一段时间)。 请注意，我必须检查所有项目的匹配项并将其位置存储在容器中。

奖励荣誉:任何人都知道我如何进行搜索的任何方式/链接，以便它找到部分结果(示例:搜索“coolro”并存储变量“coolroomhere”的位置)

Answer 1

对 vector 排序后使用binary_search

1. std::sort( serverList.begin() , serverList.end() )
2. std::lower_bound(serverList.begin() , serverList.end() , valuetoFind) 寻找第一个匹配项
3. 如果您想找到所有匹配的元素，请使用std::equal_range

lower_bound & equal_range 搜索因为它是二进制的，所以与 O(N) 的搜索相比是对数的