string :: find（）使用的字符串搜索算法C++

它比cstring函數更快嗎？ C是否有類似的可用來源？string :: find（）使用的字符串搜索算法C++

2010-04-02 Elorfin

爲什麼你認爲它更快？ – 2010-04-02 23:13:14

你可以發佈你用來計算相對速度的代碼嗎？實際上，您可能會在您的測試框架中看到不同，而不是底層代碼。 – 2010-04-02 23:15:30

如果沒有分別討論C和C++庫（分別）和C++和C編譯器（分別）的實現，則無法討論速度。 C89，C99，C++ 0x等是定義語言應該如何實現的標準。當談論「C」或「C++」時，他一般指的是語言，而沒有具體的實現。鑑於沒有參考您的_platform_我們甚至不能回答你的問題？ – 2010-04-02 23:32:39

沒有C++標準庫的標準實現，但您應該能夠看看編譯器附帶的實現，並瞭解它是如何工作的。

一般來說，大多數STL函數並不比其C語言函數快。它們通常更安全，更通用，並且與狹義用途的C等價物相比，可以適應更廣泛的環境。

來源

2010-04-02 23:30:21

任何需要函子的STL函數通常比函數指針的C函數要快。例如，'std :: sort'和'std :: binary_search'比C標準庫中的'qsort'和'bsearch'快得多。 – 2010-04-02 23:43:40

STL的「close-source binary」版本沒有這種東西。沒有人實現可導出的模板，每個人都必須爲其STL實現提供源代碼。包括Dinkumware。 – 2010-04-03 08:59:54

很高興知道。我已經編輯了相應的答案，謝謝。不過科莫C++有可導出的模板嗎？我認爲這是唯一真正實現它的編譯器。 – 2010-04-03 10:13:04

任何字符串類的標準優化都是將字符串長度與字符串一起存儲。這將使任何需要字符串長度的字符串操作被認爲是O（1）而不是O（n），strlen（）是顯而易見的。

或者複製一個字符串，實際拷貝沒有任何好處，但是在複製爲O（1）之前計算出要分配多少內存。整體算法仍然是O（n）。基本操作仍然是一樣的，剷除字節在任何語言中都會持續很長時間。

字符串類是有用的，因爲它們更安全（難以拍攝腳）並且更易於使用（需要更少的顯式代碼）。他們變得流行和廣泛使用，因爲他們不慢。

來源

2010-04-03 09:14:12

字符串類幾乎可以肯定存儲關於字符串的數據遠遠超過您在C字符串中找到的數據。長度就是一個很好的例子。在額外的內存使用權衡中，您將獲得一些閒置的CPU週期。

編輯：但是，它不太可能比另一個慢得多，因爲它們將執行基本相同的操作。 MSDN建議string :: find（）不使用基於仿函數的系統，所以它們不會有這種優化。

來源

2010-04-03 11:03:18 Puppy

如何實現查找字符串技術有許多可能性。最簡單的方法是檢查目標字符串的每個位置，如果有搜索字符串。你可以很快編寫代碼，但它是最慢的可能性。（O（m * n），m =長度搜索字符串，n =長度目標字符串）

看看維基百科頁面http://en.wikipedia.org/wiki/String_searching_algorithm，提供了不同的選項。最快的方法是創建一個有限狀態機，然後插入字符串而不會倒退。那就是O（n）。

STL實際使用哪種算法，我不知道。但是您可以搜索源代碼並將其與算法進行比較。

來源

2010-04-03 11:31:10 user287107

string :: find（）使用的字符串搜索算法C++

回答

相關問題