15

假设我有一个字符串，并且我想查找是否存在特定字符（如“|”），那么最好和最快的技术是什么？我知道字符串查找实现。我要求比这个更快的实现。

4

7 回答 7

35

利用std::string::find

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

不太可能有更有效的方法。O(n) 是你能做的最好的。标准库的实现应该是最佳的。

于 2012-12-25T06:42:46.337 回答
2

从这个使用 Visual Studio 2013 编译器完成的源经验测试表明，strchr例程比std::string::find实现快约2 倍。

于 2014-12-28T18:22:56.033 回答
1

添加汤姆坦纳的答案。如果您不想进行任何先验计算，您将陷入 O(n)，即您正在搜索的字符串的长度与时间消耗之间存在线性相关性。Tom 建议设置一个布尔数组（或向量）来指示某个字符是否出现。它需要 O(n) 一次来索引字符串，但是如果包含它，您可以检查 O(1) （恒定时间）中的任意数量的字符。这种方法的缺点是您将需要大量内存（一旦您决定需要支持 unicode）。

作为妥协，您可以使用 std::set 或类似的，仅存储输入字符串中实际存在的字符。内存消耗将与字符串中不同字符的数量呈线性关系，但查找将是 O(log n)，即时间上的对数。

当然，您应该测量/分析，然后在这里解释您实际优化的用例。在您这样做之前，请坚持使用最容易理解和阅读的内容。

于 2014-12-06T13:07:44.567 回答
1

另一种方法是在对应的 c_str 字符串上使用 strchr 函数：

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

不知道它在速度方面与 std find 相比如何......

找到的字符的位置是

size_t pos = strchr(str.c_str(),'|') - str.c_str();
于 2013-11-26T18:15:59.710 回答
0

只有一种方法可以做到这一点。只需遍历字符串以检查您正在寻找的字符是否存在。您可以通过使用该string::find函数来执行此操作，该函数获取一个字符并返回它在字符串中出现的第一个位置，或者string::npos如果该值不存在。您还可以使用std::find，它获取两个迭代器begin和end一个键值 'k' 并返回一个迭代器，该迭代器指向 k 在 range 中的第一次出现[begin, end]，或者end如果k没有找到。当然，你也可以自己实现 find 函数，像这样：

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::findand std::find：

于 2012-12-25T08:05:56.760 回答
0

鉴于您说您想要比 string::find 更快的东西，我唯一能想到的就是创建一个具有高度自定义赋值运算符的类，该类在每次更新字符串时都会更新一个包含第一个位置的内部表每个可能字符的字符串（char 字符串为 256，宽字符串为 65536(?)）。这具有 O(1) 查找，但代价是非常量操作增加了相当多的复杂性。

于 2012-12-25T09:49:58.253 回答
0

你可以试试这个：

   string s1 = "Hello";
   string s2 = "el";
   if(strstr(s1.c_str(),s2.c_str()))
   {
    cout << " S1 Contains S2";
   }
于 2015-06-02T14:04:24.370 回答