查找一个字符串是否包含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++中的字符（允许提升）

回答

相关问题