编写字符串比较函数

Writing a string compare function

我编写了以下字符串比较函数来评估两个字符串是否相同:

bool s_compare(char* str1, char* str2)
{
    // if its the same pointer can return immediately
    // also covers the case where both are null pointers
    if (str1 == str2) 
        return true;

    // if str1 is empty and str2 is non-empty
    size_t len = strlen(str1);
    if (!len && str2[0] != 0)
        return false;

    // see if for length of str1 > 1, all letters in str2 match
    // we also go up through the nul char to make sure the size
    // of both strings is the same
    for (int i=0; i<=len; i++)
        if (str1[i] != str2[i]) 
            return false;

    return true;
}

有没有可以提高效率的地方?比较两个字符串时还需要考虑哪些其他注意事项,或者这是否涵盖所有情况:

您的 s_compare() 函数具有 undefined behaviour,因为如果用户将有效或空字符串传递给 str1 和 [=15=,它最终会取消引用 NULL 指针] 到 str2 作为 s_compare() 函数的参数,像这样:

s_compare ("abc", NULL);
s_compare ("", NULL);

这两个调用都会导致未定义的行为。

要涵盖这些情况:

  • 第一个字符串较长。
  • 第二个字符串更长。
  • 空字符串。

无需调用strlen()获取字符串长度。要判断字符串是否相同,可以利用以下事实:在 C 中,字符串实际上是由空字符 [=21=] 终止的一维字符数组。只需遍历它们然后它们在特定位置的字符可能不同,或者如果它们的大小不同并且如果长字符串将具有与短字符串相同的初始字符直到短字符串的长度然后短字符串将所在的位置有空字符,在那个位置,长字符串将有一些其他字符。在这两种情况下,字符串都不相同。

由于函数 s_compare() 不应该修改作为参数传递的字符串,因此您应该声明两个指针参数 const。 实施:

bool s_compare (const char* str1, const char* str2) {

    // if its the same pointer can return immediately
    // also covers the case where both are null pointers
    if (str1 == str2) {
        return true;
    }

    // if one of them is null and other is not strings are not same
    if ((str1 == NULL) || (str2 == NULL)) {
        return false;
    }

    size_t i = 0;

    // iterater over each character of string str1
    while (str1[i]) {
        // if any of the character in str1 and str2, at position i,
        // is different that means strings are not same
        if (str1[i] != str2[i]) {
            return false;
        }
        ++i;
    }

    // we reached here that means str1 is iterated till 
    // null character and str1 ith character is null character.
    // So, if the str2 ith character is also null 
    // character than strings are same otherwise not
    return str2[i] == '[=11=]' ? true : false;
}

驱动程序:

int main (void) {
    printf ("Compare NULL and NULL : %d\n", s_compare (NULL, NULL));
    printf ("Compare \"abc\" and NULL : %d\n", s_compare ("abc", NULL));
    printf ("Compare \"\" and NULL : %d\n", s_compare ("", NULL));
    printf ("Compare NULL and \"\" : %d\n", s_compare (NULL, ""));

    char s1[10] = {0};
    char s2[10] = {0};

    printf ("Compare \"%s\" and \"%s\" : %d\n", s1, s2, s_compare (s1, s2));

    strcpy (s1, "ABC");
    strcpy (s2, "ABC");

    printf ("Compare \"%s\" and \"%s\" : %d\n", s1, s2, s_compare (s1, s2));

    strcpy (s1, "ab");
    strcpy (s2, "ayz");

    printf ("Compare \"%s\" and \"%s\" : %d\n", s1, s2, s_compare (s1, s2));

    return 0;
}

输出:

Compare NULL and NULL : 1
Compare "abc" and NULL : 0
Compare "" and NULL : 0
Compare NULL and "" : 0
Compare "" and "" : 1
Compare "ABC" and "ABC" : 1
Compare "ab" and "ayz" : 0

Are there any places where the efficiency can be improved? What other considerations need to be taken into account when comparing two strings, or does this cover all cases:

高效函数 = 尽可能将错误处理留给调用者。编写良好的函数应尽可能专注于指定的目的。字符串比较函数的目的不是清理调用应用程序中的指针,所以为什么要这样做?

忽略上述程序设计方面,编写检查指针参数是否为 NULL 或它们是否指向同一地址等的函数仍然是幼稚的。调用者可能对其数据有完美的控制并知道它是有效的- 在这种情况下,您的错误检查只会以带有分支的开销代码的形式添加很多不必要的膨胀。

您应该做的是添加适当的函数源代码文档,解释它需要两个指向有效数据的指针,并且它不会在内部进行错误处理。然后,怀疑其数据未正确清理的调用者可以在调用代码中添加那些 NULL 检查等。这一直是来电者的工作,而不是你的。


在效率、文档和一般良好实践方面,另一个重要的事情是使用 const 正确性。即:

bool s_compare (const char* str1, const char* str2);

这告诉调用者函数不会修改数据,这是自文档化代码。它还告诉 编译器 数据不会被修改,允许进行各种优化。例如,它可以假设函数不会修改任何外部链接变量。

它还可以防止编写函数的人编写意外错误,尽管我认为这个论点被高估了。


此外,老派的 C 比较函数是用语法

编写的
int func (const void* obj1, const void* obj2);

此表单的好处是您可以将其传递给 bsearchqsort,因此切换到此表单可能是个好主意,以防您需要搜索或排序数据。这里的函数应该 return -1、0 或 1 而不仅仅是 true/false,请参阅 bsearch 等的文档

在解决效率或性能问题之前,您必须确保正确性。您的 s_compare() 函数不检查其参数是否为空指针。是否应该执行此类检查是一个规范问题:标准 strcmp() 函数需要有效指针,但 free() 接受空指针并被指定为空指针。

从评论来看,函数似乎应该接受空指针和 return true 如果两个参数都是空指针。然而,如果只有一个参数是 NULL.

,则它具有未定义的行为

发布的代码中存在一个小问题:变量 i 的类型为 int,这与 size_t 不同,并且很可能具有更小的范围。如果字符串长度为 MAX_INT 或更大,则行为未定义。 i 应该有类型 size_t.

以下是需要改进的地方:

  • 由于该函数不修改字符串,因此参数类型应为 const char * 以允许在没有编译器警告的情况下传递常量字符串。

  • 空字符串的测试是多余的,如果 str1 为空则保存一次比较,而在所有其他情况下添加一个。它应该被删除。

  • 测试相同的字符串指针也是多余的,但确实提高了这种特殊情况的性能,将复杂性从线性时间降低到常数时间。如果经常使用相同的指针调用 s_compare,这可能是值得的,但在一般情况下,没有必要,除非指定了空指针的特殊情况。

  • 两次扫描第一个字符串,一次计算它的长度,第二次将字符与第二个字符串进行比较简化了代码,但适得其反:即使在区别在于前几个字节。比较内容并逐步测试字符串结尾似乎要好得多。请注意,仅当字符相同时才需要与 '[=25=]' 进行比较。

这是修改后的版本:

bool s_compare(const char *str1, const char *str2) {
    // s_compare accepts null pointers and returns true if
    // both arguments are null
    if (!str1 || !str2)
        return str1 == str2;

    // iterate for each byte until a difference is found
    // return true if the identical byte is the null terminator
    for (size_t i = 0; str1[i] == str2[i]; i++) {
        if (str1[i] == '[=10=]') 
            return true;
    }
    return false;
}