C++使用终止符的位置作为交换空间来反转空终止字符串

Question

我正在研究经典的“反转字符串”问题。

将空终止符的位置用于交换空间是个好主意吗？想法是保存一个变量的声明。

具体来说，从 Kernighan 和 Ritchie 的算法开始:

void reverse(char s[])
{
    int length = strlen(s);
    int c, i, j;

    for (i = 0, j = length - 1; i < j; i++, j--) 
    {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

...我们可以改为执行以下操作吗？

void reverseUsingNullPosition(char s[]) {
    int length = strlen(s);
    int i, j;

    for (i = 0, j = length - 1; i < j; i++, j--) {
        s[length] = s[i]; // Use last position instead of a new var
        s[i] = s[j];
        s[j] = s[length];
    }
    s[length] = 0; // Replace null character
}

注意不再需要“c”变量。我们简单地使用数组中的最后一个位置——空终止符所在的位置——作为我们的交换空间。完成后，我们只需替换 0。

这是主要例程(Xcode):

#include <stdio.h>
#include <string>

int main(int argc, const char * argv[]) {
    char cheese[] = { 'c' , 'h' , 'e' , 'd' , 'd' , 'a' , 'r' , 0 };
    printf("Cheese is: %s\n", cheese); //-> Cheese is: cheddar

    reverse(cheese);
    printf("Cheese is: %s\n", cheese); //-> Cheese is: raddehc

    reverseUsingNullPosition(cheese);
    printf("Cheese is: %s\n", cheese); //-> Cheese is: cheddar
}

Answer 1

是的，这是可以做到的。不，这不是一个好主意，因为它会使您的程序更难优化。

当您在局部范围内声明 char c 时，优化器可以确定该值未在 s[j] = c; 赋值之外使用，并且可以将临时文件放在寄存器中。除了有效地为您消除变量外，优化器甚至可以确定您正在执行交换，并发出特定于硬件的指令。所有这些都将为您节省每个字符的内存访问。

当你使用 s[length] 作为你的临时变量时，优化器没有那么大的自由度。它被迫将写入发送到内存中。由于缓存，这可能同样快，但在嵌入式平台上，这可能会产生重大影响。