使用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”的位置）

- maffo

---

不要使用 i，而是使用 std::distance(serverList.begin(), it)；或者直接通过索引访问向量。 - Kerrek SB

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)搜索更加高效。请注意，保留HTML标记。

- parapura rajkumar

---

如果数据结构本身适合重新设计的话，unordered_multiset<string> 可能更为适当。 - Kerrek SB

我对需要排序的事情的倾向是一开始就将它们按顺序添加。 - T.E.D.

当然，只有当他需要经常这样做时才值得这样做，因为它是O（nlogn）而他现在的方法只有O（n）。 - Christian Rau

@ChristianRau - 如果你倾向于以启动时间为代价来换取运行时间。 - T.E.D.

Answer 2

基本上，您是在询问是否可能检查所有元素以获取匹配项，而无需检查所有元素。如果存在某种外部元信息（例如数据已排序），则可能是可能的（例如使用二进制搜索）。否则，根据其本质，要检查所有元素，您必须检查所有元素。

如果您将在列表上执行许多此类搜索，并且列表不变，则可以考虑计算具有条目很好的哈希代码的第二个表格；再次取决于正在查找的数据类型，根据索引计算哈希代码并首先比较哈希代码可能更有效，仅在哈希代码相等时才比较字符串。这是否是一种改进在很大程度上取决于表的大小和其中的数据类型。您还可以利用关于字符串中数据的知识；例如，如果它们都是URL，大多数以“http://www。”开头，从第十个字符开始进行比较，仅在所有其余内容相等时才返回比较第一个10，可能会产生巨大的胜利。

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

for ( auto 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搜索的方法可能更有效，但是需要在进入循环之前将搜索字符串预编译为必要的表格。

- James Kanze

Answer 3

如果您将容器更改为std::map而不是std::vector，则使用的底层数据结构将被优化以执行此类关键字搜索。

如果您改用std::multimap，则成员函数equal_range()将返回覆盖映射中每个匹配项的迭代器对。这听起来像是您想要的。

下面的聪明评论者指出，如果您实际上没有存储除名称（搜索关键字）之外的任何其他信息，则应该改用std::multiset。

- T.E.D.

---

既然他在那里没有存储其他任何东西，使用std::multiset会更好。 - Christian Rau