C++：高效地在子字符串数组中找到一个字符串

我有一个字符串前缀数组：std::vector<std::string> haystack = {"/bin/", "/usr/bin/", "/usr/local/bin/"}。C++：高效地在子字符串数组中找到一个字符串

有没有一种有效的方法来找到std::string needle = "/bin/echo"开头的子字符串从haystack，使用标准的C++库？

如果我需要找到完全匹配，我可以使用std::set<std::string>，这将执行一个有效的二进制搜索，但是我只需要匹配字符串的第一部分，所以目前我正在使用一个简单的循环：

for (auto it = haystack.begin(); it != haystack.end(); it++) { 
    if (needle.compare(0, it->size(), *it) == 0) { 
     return true; // Found it 
    } 
} 
return false;

来源

2016-09-06 pelya

请定义_efficient_。为了缩短代码，有'std :: find_if（）'。 –

比遍历整个'haystack'数组更快，这将是'O（n）'。 'find_if'将执行与'O（n）'速度完全相同的循环。 – pelya

分而治之。但即使这样也不能保证比O（n）更快。 –

排序hasystack由降序字符串长度。
比较前缀不超过needle的顺序;做它的权利离开。例如，如果prefix是5个字符长，则比较prefix[4]到needle[4]，然后prefix[3]到needle[3]等等。

这样你会立即丢弃许多不匹配的东西。作为奖励，你会发现最长的比赛（可能只是你想要的）。

来源

2016-09-06 17:44:36

为什么选择干草堆？这变成了干草堆大小的“O（n log n）”操作。否则就是'O（n）'。 – Richard

@理查德：这不是绝对必要的。假设不需要首先查找最长的匹配项，根据具体情况，排序可能有好处，也可能没有好处。 –

的一个“优化”我想补充的是，如果你使用std::any_of它会在找到第一个字符串匹配

auto found = std::any_of(begin(haystack), 
         end(haystack), 
         [&needle](std::string const& sub) 
         { 
          return needle.compare(0, sub.size(), sub) == 0; 
         });

否则，如果你想找到短路这串匹配，你可以使用std::find_if，这也会在找到第一场比赛后短路。

auto match = std::find_if(begin(haystack), 
          end(haystack), 
          [&needle](std::string const& sub) 
          { 
           return needle.compare(0, sub.size(), sub) == 0; 
          });

来源

2016-09-06 17:44:46 CoryKramer

我只需要在数组中找到第一个匹配，我已经更新了我的代码示例。 – pelya

C++：高效地在子字符串数组中找到一个字符串

回答

相关问题