Borland的string::find错误问题

Question

Borland的string::find错误问题

4

我在支持一个使用Borland C++ Builder 5.02编写（来自1997年）的C++应用程序。Borland字符串类上的find()方法并不像我期望的那样运行：

#include <cstring>
#include <iostream>

int main (int argc, char *argv[])
{
   string needle = "length == eighteen";
   string haystack = "<" + needle + ">";
   if (haystack.find(needle) != NPOS)
      cout << "Found it!" << endl;
   else
      cout << "Not found" << endl;

   return 0;
}

该程序输出“未找到”。如果我将针更改为较短的内容，则输出“找到了！”。如果我将尖括号换成其他字符，则可以找到。空格可以，但括号不行。

请注意，我在这里使用的是Borland字符串库：如果我包含< string >并使用std :: string，那么它的工作方式与我期望的完全相同。不幸的是，更改整个应用程序以使用STL字符串并不是可行的答案！

从文档中可以看出，Borland使用基于哈希的算法进行字符串搜索。我找不到更多关于此的详细信息，并且我已经步入了反汇编，但并没有更明智的想法。

我很难相信这真的是字符串库中的错误，特别是因为如果是这样的话，我希望能够找到一篇文章或类似的东西。我找不到这样的信息。

然而，我已经没有更多的想法了！这是一个已知的错误吗？有解决方法吗？

编辑：再次查看反汇编后，我认为它试图执行类似于Rabin-Karp算法的操作，其中哈希函数计算模33554393（小于2 ^ 25的最大质数）。它可能是以32为基数的多项式哈希函数（即a_0 + 32 a_1 + 32 ^ 2 a_2 +..+ 32 ^ n a_n），但这只是一种预感。听起来像是Daniel Fischer建议的可能溢出。

- Dave Turner

2

"基于哈希的算法", "如果我把针改成更短的东西" <- 这似乎有整数溢出的味道。 - Daniel Fischer

1

当你依赖于15年前的编译器时，就会发生这种情况。是时候向前迈进了。 - David Heffernan

1

@PeterWood 当没有预算时，保持不动可能会很困难。 - David Heffernan

1

@DavidHeffernan 这个问题是作为一个项目的一部分而出现的，该项目旨在将这个（完全工作且非常有利可图的）系统迁移到更现代的编译器上。我们正在“前进”。但它必须像当前版本一样正常工作，http://pragmatictips.com/26 告诉我要怀疑自己的错误而不是库错误，因为前者更有可能出现。因此提出了这个问题。 - Dave Turner

1

@DavidHeffernan 我不在乎修复库的问题。如果这是一个已知的库错误，那么我们可以通过改变应用程序来解决它（例如使用strstr()）并迁移更改后的代码。令我惊讶的是，我找不到任何证据表明这是一个已知的库错误。 - Dave Turner

显示剩余4条评论

3个回答

2

我发现1998年的一个参考资料表明Borland的字符串搜索实现存在一个bug:

https://groups.google.com/forum/?fromgroups=#!searchin/borland.public.cpp.language/cstring$20bug/borland.public.cpp.language/XBzjaJmCYpk/gtMPm-j8jugJ

此外，似乎在某个时期C++委员会决定将字符串类作为标准C++的一部分，而cstring的字符串类是这一决定的遗留物:

https://groups.google.com/forum/?fromgroups=#!searchin/borland.public.cpp.language/borland$20cstring/borland.public.cpp.language/2psY2seRmS4/ywVrqwU1C2wJ

- junichiro

1

你没有使用Borland字符串库。String (大写S)是 Borland 字符串类。string (小写s)，与 std::string 完全相同，是 STL 字符串类，而不是 Borland 实现（BCB5 中的 STL 是 RogueWave STL）。你使用 #include 很可能将 std::string 引入了全局命名空间，这就是为什么你的代码编译通过的原因。但你真正应该使用 #include 和 std::string。至于 NPOS，你应该使用 string::npos，因为这才是 string::find() 实际返回的东西。

#include <cstring>
#include <iostream>

int main (int argc, char *argv[])
{
   string needle = "length == eighteen";
   string haystack = "<" + needle + ">";
   if (haystack.find(needle) != string::npos)
      cout << "Found it!" << endl;
   else
      cout << "Not found" << endl;

   return 0;
}

或者：

#include <string>
#include <iostream>

int main (int argc, char *argv[])
{
   std::string needle = "length == eighteen";
   std::string haystack = "<" + needle + ">";
   if (haystack.find(needle) != std::string::npos)
      std::cout << "Found it!" << std::endl;
   else
      std::cout << "Not found" << std::endl;

   return 0;
}

- Remy Lebeau

我不确定我们谈论的是否是同一个类库版本。我在我的系统中找不到 String 类，而我正在使用的 string 明显不是 std::string - 例如它有一个 contains() 方法，而我的 std::string 却没有。类库文档确实是关于一个 string 类的。你的两个程序都无法编译通过：第一个说 undefined symbol 'npos'，而第二个则说 'cout' is not a member of 'std'。[... TBC] - Dave Turner

你说你安装了BCB5 - 这是5.02还是免费提供的5.5版本？你能编译和运行我提供的程序吗？如果可以，你是否看到相同的输出？那将非常有帮助。 - Dave Turner

@DaveTurner：我认为我们甚至没有在谈论同一个产品。你说你正在使用Borland C++ Builder（这也是我安装的），但我认为你实际上是在使用**Borland C++。它们不是同一个产品。在Borland C++**中，cstring.h定义了一个非标准的string类，它不是STL的std::string类。 - Remy Lebeau

@DaveTurner: Borland C++ Builder 使用STL的std::string类，它的VCL框架还定义了一个单独的System::String类，与Delphi二进制兼容。 - Remy Lebeau

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jogy · Accepted Answer

如果您有原始的BC++ 5.02安装光盘，则可以在BC5\SOURCE\RTL\SOURCE\STRING下找到字符串类源代码。

以下是string::find_case_index()函数的代码摘录（由string::find()调用）：

const long q = 33554393L;
const long q32 = q<<5;

size_t testlength = length() - startindex;
size_t patternlength = patl = strlen(cp);
if( testlength < patternlength )
    return NPOS;
if( patternlength == 0 )
    return 0;

long patternHash = 0;
long testHash = 0;

const char _FAR *testP = c_str()+startindex;
const char _FAR *patP = cp;
long x = 1;
size_t i = patternlength-1;

while( i-- )
    x = (x<<5)%q;

for( i=0; i<patternlength; i++ )
    {
    patternHash = ( (patternHash<<5) + *patP++  ) % q;
    testHash    = ( (testHash   <<5) + *testP++ ) % q;
    }

testP = c_str()+startindex;
const char _FAR *end = testP + testlength - patternlength;

while (1)
    {

    if(testHash == patternHash)
        if( !get_paranoid_check_flag() ||
            !strncmp( testP, cp, patternlength) )
          return (size_t)(testP-c_str());

    if( testP >= end )
        break;

    // Advance & calculate the new hash value:
    testHash = ( testHash + q32 - *testP * x                 ) % q;
    testHash = ( (testHash<<5)  + *(patternlength + testP++) ) % q;
    }
return NPOS;          // Not found.