性能的std ::對比的strstr的std :: string ::找到

Question

可能重複：
C++ string::find complexity

最近我發現，該功能std::string::find是一個量級慢比功能std::strstr - 在我的Linux環境中使用GCC 4.7。性能差異取決於字符串的長度和硬件架構。

但是，有一個簡單的原因有所不同：std::string::find基本上在一個循環中調用std::memcmp - 時間複雜度爲O(m * n)。相比之下，std::strstr針對硬件體系結構（例如，使用SSE指令）進行了高度優化，並使用更復雜的字符串匹配算法（顯然是Knuth-Morris-Pratt）。

我也很驚訝沒有在語言文檔（即草稿N3290和N1570）中找到這兩個函數的時間複雜性。我只找到了時間複雜度爲char_traits。但是這並沒有幫助，因爲在char_traits中沒有子字符串搜索的功能。

我認爲，std::strstr和memmem包含類似的優化幾乎相同的性能。直到最近，我還是假定std::string::find在內部使用memmem。

的問題是：有沒有什麼好的理由，爲什麼std::string::find不使用std::memmem？這與其他實現有何不同？

問題不在於：這個函數的最佳實現是什麼？如果它比C慢，那麼爲C++辯論真的很困難。如果兩種實現都很慢，我就不會擔心了。這是真正傷害的性能差異。

Answer 1

首先，什麼是memmem？我無法在C++標準中找到它，也不能在Posix標準中找到它（它包含所有的標準C函數）。

其次，任何測量值將取決於實際數據。例如，使用 在很多情況下，KMP就會成爲一種悲觀主義;大概 使用std::string的成員函數的大多數情況; 設置必要表的時間往往會比直接算法的總時間多 。像O(m*n) 這樣的東西在字符串的典型長度很短時沒有多大意義。