查找一個字符串是否包含C++中的字符（允許提升）

假設我有一個字符串，並且想要查找是否存在某個特定字符（如'|'），那麼做什麼是最好和最快的技術所以？我知道字符串找到實現。我要求比這更快的實現。查找一個字符串是否包含C++中的字符（允許提升）

2012-12-25 psyche

看，你最終會發現'find'。 – chris

取決於您使用的字符串的「形式」。 –

請避免標題中的「最好」和「最快」;前者應[近]總是避免，因爲它增加了什麼價值（「最好」的方式將在「最佳」答案給出），而後者應該避免，除非有具體的測試用例/場景中常見的接近「不夠快」（這需要有* *的東西首先要進行對比的！） – 2012-12-25 06:45:35

使用std::string::find

if (str.find('|') != std::string::npos) 
{ 
    // ... 
}

有不可能是任何更有效。 O（n）是你能做的最好的。標準的庫實現應該是非常優化的。

來源

2012-12-25 06:42:46

只有一種方法可以做到這一點。只需遍歷字符串來檢查你正在尋找的字符是否存在。您可以使用string::find函數執行此操作，該函數獲取字符並返回字符串中出現的第一個位置，如果該值不存在，則返回string::npos。您還可以使用std::find，它獲取兩個迭代器begin和end以及鍵值「k」，並返回一個迭代器，指示範圍[begin, end]中k的第一個出現次數，如果未找到k，則返回end。當然，你可以自己實現的查找功能，像這樣：

string::size_type pos=string::npos; 
for(string::size_type i=0; i<s.size(); ++i) { 
    if(s[i] == key) { 
    pos=i; 
    break; 
    } 
} 
if(pos != string::npos) { 
    // key was found 
} else { 
    // not found 
}

或本：

string::iterator pos=s.end(); 
for(string::iterator i=s.begin(); i!=s.end(); ++i) { 
    if(*i == key) { 
    pos=i; 
    break; 
    } 
} 
if(pos != s.end()) { 
    // found 
} else { 
    // not found 
}

更多關於std::string::find和std::find：

來源

2012-12-25 08:05:56

考慮到你想要的東西比string :: find更快，我唯一能想到的就是創建一個具有高度自定義賦值運算符的類，它在每次更新字符串時更新一個包含在每個可能字符的字符串中的第一個位置（字符串爲256，寬字符串爲65536（？））。這有O（1）查找的代價，其代價是非常量操作中增加了很多複雜性。

來源

2012-12-25 09:49:58

另一種方法是使用strchr函數上的相應c_str字符串：

if(strchr(str.c_str(), '|')) 
{ 
    \\found 
}

不知道如何比較的std發現，雖然速度方面...

找到的位置字符是

size_t pos = strchr(str.c_str(),'|') - str.c_str();

來源

2013-11-26 18:15:59 afakih

http://www.cplusplus.com/reference/cstring/strchr/需要兩個參數 – Peter

「如果沒有找到的字符，該函數返回一個空指針」。所以在你的例子中，你在這種情況下從NULL指針中減去。指針溢出是UB。 – namezero

@namezero這就是爲什麼我們試圖通過減法來獲取POS之前，if語句開始，所以如果字符沒有找到，我們不嘗試獲得POS。 – afakih

添加湯姆坦納的答案。如果您不想進行任何先驗計算，您將被卡在O（n）處，即您搜索的字符串的長度與時間消耗之間存在線性相關性。湯姆建議設置一個布爾值的數組（或向量）來表示是否發生某個特定字符。它需要O（n）一次索引字符串，但是如果包含O（1）（恆定時間），則可以檢查任意數量的字符。這種方法的缺點是你需要大量的內存（一旦你決定需要支持unicode）。

作爲一種折衷方案，您可以使用std :: set或類似的方法，只存儲輸入字符串中實際存在的字符。然後，內存消耗將圍繞字符串中不同字符的數量呈線性，但查找將爲O（log n），即時間上的對數。

當然，你應該測量/配置文件，然後在這裏說明一下什麼使用情況，你實際上是優化。在你這樣做之前，堅持最容易理解和閱讀的內容。

來源

2014-12-06 13:07:44

從this source與Visual Studio 2013進行實證檢驗編譯器顯示，和strchr常規約爲快兩倍比的std :: string ::找到實施。

來源

2014-12-28 18:22:56 Mouze

確保字符，如果它的工作原理。 –

你可以試試這個：通過'的std :: string`參考

string s1 = "Hello"; 
    string s2 = "el"; 
    if(strstr(s1.c_str(),s2.c_str())) 
    { 
    cout << " S1 Contains S2"; 
    }

來源

2015-06-02 14:04:24 HappyTran

查找一個字符串是否包含C++中的字符（允許提升）

回答

相關問題