如何修复strcpy以便检测重叠的字符串

在一次采访中，我被要求编写strcpy的实现，然后修复它以便正确处理重叠的字符串。 我的实现在下面，它是非常天真的..我如何修复它，以便a）它检测重叠的字符串和b）检测后..我们如何处理重叠并继续？

char* my_strcpy(char *a, char *b){ if(a == NULL || b == NULL){ return NULL; } if(a > b){ //we have an overlap? return NULL; } char *n = a; while(*b != '\0'){ *a = *b; a++; b++; } *a = '\0'; return n; } int main(int argc, char *argv[]) { char str1[] = "wazzupdude"; char *after_cpy = my_strcpy(str1+2,str1); return 0; } 

编辑：

因此，基于@ Secure的答案的一种可能的实现是：

  char* my_strcpy(char *a, char *b){ if(a == NULL || b == NULL){ return NULL; } memmove(a, b, strlen(b) + 1); return a; } 

如果我们不依赖memmove，那么

  char* my_strcpy(char *a, char *b){ if(a == NULL || b == NULL){ return NULL; } if( a == b) return a; //case1: b is placed further in the memory if((a  b)) { char *n = a; while(*b != '\0'){ *a = *b; a++; b++; } *a = '\0'; return n; } //case 2: a is further in memory else if((b  a)) { char *src = b + strlen(b) -1; //src points to end of b char *dest = a; while( src != b){ *dest = *src; dest--; src--; //not sure about this.. } *a = '\0'; return a; } 

Answer 1

没有可移植的方法来检测这一点。 您必须进行指针比较，并且这些仅在同一对象中定义。 即如果两个字符串不重叠并且实际上是不同的对象，则指针比较会给出未定义的行为。

我会让标准库通过使用memmove(a, b, strlen(b) + 1)来处理这个问题。

编辑：

正如Steve Jessop在评论中指出的那样，在这种情况下实际上存在一种便携但缓慢的方法来检测重叠。 将b中的每个地址与for的第一个和最后一个地址进行比较。 与==的等式比较总是很明确。

所以你有这样的事情：

 l = strlen(b); isoverlap = 0; for (i = 0; i <= l; i++) { if ((b + i == a) || (b + i == a + l)) { isoverlap = 1; break; } } 

编辑2：案例2的可视化

你有类似下面的数组和指针：

 S tring 0 _ _ _ _ _ _ _ ^ ^ | | ba 

注意， b + strlen(b)导致指向终止\ 0的指针。 开始一个，否则你需要额外处理边缘情况。 在那里设置指针是有效的，你不能取消引用它们。

 src = b + strlen(b) + 1; dst = a + strlen(b) + 1; S tring 0 _ _ _ _ _ _ _ ^ ^ ^ ^ | | | | ba src dst 

现在复制循环也复制了\ 0。

 while (src > b) { src--; dst--; *dst = *src; } 

第一步是这样的：

 src--; dst--; S tring 0 _ _ _ _ _ _ _ ^ ^ ^ ^ | | | | ba src dst *dst = *src; S tring 0 _ _ _ 0 _ _ _ ^ ^ ^ ^ | | | | ba src dst 

依此类推，直到src结束等于b ：

 S tri S tring 0 _ _ _ ^ ^ | | ba src dst 

如果你想要它更加hackish，你可以进一步压缩它，但我不建议这样：

 while (src > b) *(--dst) = *(--src); 

Answer 2

注意：这里， b是源字符串的地址， a是目标的地址。

使用a > b您不一定会有重叠。 如果

 (a <= b && a+strlen(a) >= b) || (b <= a && b+strlen(b) >= a) 

然后你有重叠。

但是，除了为了采访而检测重叠之外， a > b应该对strcpy做好。 这个想法是这样的：

如果b进一步放在内存中（ b > a ），那么你通常可以将b复制到a 。 b将被覆盖，但你已经超过了那一部分。

如果a进一步放在内存中（ a > b ），则意味着可能通过写入a的第一个位置，您已经覆盖了b具有更高索引的位置。 在这种情况下，您应该以相反的方向复制。 因此，不应该从索引0复制到strlen(b)-1 ，而应该从strlen(b)-1复制到0 。

如果您对此有何帮助感到困惑，请在纸上绘制两个重叠的数组，并尝试从数组的开头复制一次，然后从结尾复制一次。 在a > b和a < b情况下，尝试使用重叠数组。

注意，如果a == b ，你不需要实际复制任何东西，你可以返回。

编辑：我不确定，但阅读其他解决方案，似乎这个答案可能不完全可移植。 要小心。

Answer 3

如果您希望字符串重叠，则可以使用memmove（）。

 char* my_strcpy(char *a, char *b) { memmove(a, b, strlen(b) + 1); return a; } 

Answer 4

 if a > b; then copy a from the beginning else if a < b; then copy a from the ending else // a == b do nothing 

你可以参考memmove的实现 ，它就像我说的那样。

Answer 5

 if (a>= b && a <= b+strlen(b))) || (b+strlen(b) >= a && b+strlen(b) <= a + strlen(b)) 

（*）你应该缓存strlen（b）来提高性能

它能做什么：
检查a+len [+额外len字节的地址]是否在字符串内，或者[地址]是否在字符串内，这些是字符串重叠的唯一可能性。

Answer 6

如果这两个字符串重叠，那么，在复制时，您将遍历原始的a或b指针。

假设strcpy（a，b）大致意味着< - b，即第一个参数是副本的目的地，那么你只检查复制指针是否到达b的位置。

您只需保存原始位置，并在复制时检查您是否未到达。 此外，如果已达到该位置，请勿写入尾随零。

  char* my_strcpy(char *a, const char *b) { if ( a == NULL || b == NULL ) { return NULL; } char *n = a; const char * oldB = b; while( *b != '\0' && a != oldB ) { *a = *b; a++; b++; } if ( a != oldB ) { *a = '\0'; } return n; } 

该算法只是停止复制。 也许你想做其他的事情，比如标记错误条件，或者将字符串标记的末尾添加到前一个位置（虽然默默地失败（因为算法目前做的）并不是最好的选择）。

希望这可以帮助。

Answer 7

我在最近的一次采访中被问到这个问题。 我们不必’检测’重叠。 我们可以用重叠地址处理的方式编写strcpy 。 关键是从源字符串的末尾而不是从开头复制。

这是一个快速代码。

 void str_copy(const char *src, char *dst) { /* error checks */ int i = strlen(a); /* may have to account for null character */ while(i >= 0) { dst[i] = src[i]; i--; } } 

编辑：这只适用于 b，从头开始复制。

Answer 8

即使不使用关系指针比较， memmove或等效，也可以编写strcpy的版本，它将在非重叠的情况下作为strlen和memcpy执行，并在重叠的情况下作为自上而下的副本执行。 关键是利用如下事实：如果读取目标的第一个字节然后替换为零，则在源上调用strlen并添加到源指针，返回的值将产生一个合法的指针，该指针将等于“麻烦重叠”案件中的目的地。 如果源和目标是不同的对象，则可以安全地计算“source plus strlen”指针并观察其与目的地不相等。

如果将字符串长度添加到源指针产生目标指针，则使用较早读取的值替换零字节并在目标上调用strlen将允许代码确定源字符串和目标字符串的结束地址。 此外，源串的长度将指示指针之间的距离。 如果此值很大（可能大于16左右），则代码可以有效地将“移动”操作细分为自上而下的memcpy操作序列。 否则，可以使用自上而下的单字节复制操作循环复制字符串，或者使用“memcpy to source to buffer”/“memcpy buffer to destination”操作[如果是大字节的每字节成本]复制该字符串不到个别字符复制循环的一半，使用~256字节的缓冲区可能是一个有用的优化]。