使用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>
        }
    }

我已经编写了上面的代码来查看字符串向量并返回另一个带有任何"命中"位置的向量.

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

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

Answer 1

排序向量后使用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)

Answer 2

基本上,你会问是否可以检查匹配的所有元素,而不检查所有元素.如果存在某种外部元信息(例如,数据被排序),则可能(例如使用二分搜索).否则,就其本质而言,要检查所有元素,您必须检查所有元素.

如果您要在列表上执行许多此类搜索,并且列表不会发生变化,您可以考虑使用条目的良好哈希码计算第二个表; 再次根据被查找的数据类型,计算索引的哈希码可能更有效,并首先比较哈希码,只有在哈希码相等时才比较字符串.这是否有所改进在很大程度上取决于表的大小及其中的数据类型.您也可以利用关于字符串中数据的知识; 如果它们都是URL,例如,主要是以"http://www."第十个字符开始比较,并且只返回比较前10个,如果所有其余的相等,则可能最终获得大奖.

关于查找子字符串,您可以使用std::search每个元素:

for ( std::vector<std::string::const_iterator iter = serverList.begin();
        iter != serverList.end();
        ++ iter ) {
    if ( std::search( iter->begin(), iter->end(),
                      index.begin(), index.end() ) != iter->end() ) {
        indexResult.push_back( iter - serverList.begin() );
    }
}

根据所搜索的元素的数量和所涉及的字符串的长度,使用诸如BM搜索之类的东西可能更有效,但是,在进入循环之前将搜索字符串预编译到必要的表.