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++：高效地在子字符串數組中找到一個字符串

回答

相關問題