令人惊讶的简单/愚蠢/基本问题,但我不知道:假设我想给函数的用户返回一个C字符串,在函数开头我不知道它的长度.我只能在一开始就给长度设定一个上限,而且,根据处理的不同,大小可能会缩小.

问题是,在处理过程中分配足够的堆空间(上限),然后在远远低于上限的范围内终止字符串,这有什么不对吗?即,如果我在分配的内存中间插入‘\0’,(a.)free()是否仍然正常工作,以及(b.)‘\0’之后的空格是否变得无关紧要?一旦添加了‘\0’,内存是直接返回,还是一直坐在那里占用空间直到调用free()?为了节省一些前期编程时间,在调用malloc之前计算必要的空间,将这个挂起空间留在那里通常是不好的编程风格吗?

为了给它一些上下文,假设我想删除连续的重复项,如下所示:

input "Hello oOOOo !!" --> output "Helo oOo !"

... 下面的一些代码显示了我如何预计算操作产生的大小,有效地执行两次处理以获得正确的堆大小.

char* RemoveChains(const char* str)
{
    if (str == NULL) {
        return NULL;
    }
    if (strlen(str) == 0) {
        char* outstr = (char*)malloc(1);
        *outstr = '\0';
        return outstr;
    }
    const char* original = str; // for reuse
    char prev = *str++;       // [prev][str][str+1]...
    unsigned int outlen = 1;  // first char auto-counted

    // Determine length necessary by mimicking processing
    while (*str) {
        if (*str != prev) { // new char encountered
            ++outlen;
            prev = *str; // restart chain
        }
        ++str; // step pointer along input
    }

    // Declare new string to be perfect size
    char* outstr = (char*)malloc(outlen + 1);
    outstr[outlen] = '\0';
    outstr[0] = original[0];
    outlen = 1;

    // Construct output
    prev = *original++;
    while (*original) {
        if (*original != prev) {
            outstr[outlen++] = *original;
            prev = *original;
        }
        ++original;
    }
    return outstr;
}

推荐答案

如果我在分配的内存中间插入一个"\0",会吗

(A)free()仍然正常工作,并且

(b."\0"后面的空格是否变得无关紧要?添加"\0"后,内存是否会被返回,或者在调用free()之前它是否会一直占用空间?

视情况而定.通常,当您分配大量堆空间时,系统首先分配虚拟地址空间——当您写入页面时,会分配一些实际的物理内存来支持它(当您的操作系统支持虚拟内存时,这些内存可能会被交换到磁盘).著名的是,虚拟地址空间和实际物理/交换内存的浪费分配之间的这种区别使得稀疏数组在这样的操作系统上具有合理的内存效率.

现在,这种虚拟寻址和分页的粒度取决于内存页大小——可能是4k、8k、16k...?大多数操作系统都有一个函数,你可以调用它来确定页面大小.因此,如果你正在进行大量的小规模分配,那么四舍五入到页面大小是浪费的,如果你的地址空间相对于你真正需要使用的内存量是有限的,那么以上述方式依赖虚拟寻址将无法扩展(例如,带有32位寻址的4GB RAM).另一方面,如果您有一个64位的进程,使用32GB的RAM运行,并且执行的此类字符串分配相对较少,那么您就有大量的虚拟地址空间可供使用,而页面大小的四舍五入也不会太大.

但是——请注意,在整个缓冲区中写入数据,然后在某个较早的点终止它(在这种情况下,一旦写入内存,就会有备份内存,并可能以交换结束),与在大缓冲区中只写入第一位,然后终止之间的区别(在这种情况下,备份内存只分配给向上舍入到页面大小的已用空间).

还值得指出的是,在许多操作系统上,堆内存可能在进程终止之前不会返回到操作系统:相反,malloc/free库会在需要增加堆时通知操作系统(例如,在UNIX上使用sbrk(),在Windows上使用VirtualAlloc()).从这个意义上说,free()内存对于您的进程来说是可以重用的,但是对于其他进程来说不是可以重用的.一些操作系统确实对此进行了优化——例如,使用一个独特的、可独立释放的内存区域来进行非常大的分配.

为了节省一些前期编程时间,在调用malloc之前计算必要的空间,将这个挂起空间留在那里通常是不好的编程风格吗?

同样,这取决于你处理了多少这样的分配.如果虚拟地址空间/RAM中存在大量内存,那么您需要明确地让内存库知道,使用realloc(),并非所有最初请求的内存都是实际需要的,或者,您甚至可以使用strdup()根据实际需要(然后是原始的free())更紧密地分配一个新块,这取决于您的malloc/free库实现,它的效果可能更好或更差,但很少有应用程序会受到任何差异的显著影响.

有时,您的代码可能位于一个库中,您无法猜测调用应用程序将管理多少个字符串实例——在这种情况下,最好提供更慢的行为,而不要太糟糕...因此,倾向于缩小内存块以适应字符串数据(一组额外的操作,因此不会影响big-O效率),而不是浪费未知比例的原始字符串缓冲区(在病态情况下,在任意大的分配后使用零或一个字符).作为性能优化,只有在未使用的空间为>;=使用的空间-根据口味调整,或使其可配置.

你对另一个答案发表了 comments :

所以归根结底是判断realloc是否需要更长的时间,还是预处理大小的确定?

如果性能是你的首要任务,那么是的——你会想要配置文件.如果你没有CPU限制,那么一般来说,采取"预处理"措施,并进行适当大小的分配——只会减少碎片和混乱.与此相反,如果你必须为某个函数编写一个特殊的预处理模式——这是一个额外的"表面",让错误和代码得以维护.(在从snprintf()实现自己的asprintf()时,通常需要这个权衡决定,但至少你可以相信snprintf()会按照文件规定行事,而不必亲自维护它).

C++相关问答推荐

如何从C中的公钥字符串创建EVP_PKEY

为什么海湾合作委员会在共享对象中的. init_data的虚拟内存地址之前留出一个空白

GCC:try 使用—WError或—pedantic using pragmas

当多个线程在C中写入相同的文件描述符时,如何防止争用情况?

如何在C宏中确定 struct 中元素的类型?

在C语言中,在数学运算过程中,为什么浮点数在变量中的行为不同

二进制计算器与gmp

fwrite无法写入满(非常大)缓冲区

判断X宏的空性

如何在CANbus RX/TX FIFO起始地址寄存器(ATSAME 51)的特定地址初始化数组?

为什么用非常数指针变量改变常量静态变量时会出现分段错误?

C代码在字符串中删除不区分大小写的子字符串的问题

如何对现有的双向循环链表进行排序?

我正在try 将QSORT算法实现为C++中的泛型函数

UpDown控制与预期相反

C语言中的指针和多维数组

将char*铸造为空**

子进程不会修改父进程中的统计信息

为什么需要struct in_addr

在 C 中的 scanf() 格式说明符中使用宏获取字符串长度