66

令人惊讶的简单/愚蠢/基本问题，但我不知道：假设我想向函数的用户返回一个 C 字符串，在函数的开头我不知道它的长度。最初只能对长度设置上限，根据加工，有尺寸缩小的情况。

问题是，分配足够的堆空间（上限）然后在处理期间终止字符串是否有任何问题？即如果我将'\0' 粘贴到分配的内存的中间，（a.）free()是否仍然正常工作，并且（b.）'\0' 之后的空间是否变得无关紧要？添加 '\0' 后，内存是否会被返回，还是会一直占用空间直到free()被调用？为了节省一些前期编程时间，在调用 malloc 之前计算必要的空间，将这个悬挂空间留在那里通常是不好的编程风格吗？

为了给出一些上下文，假设我想删除连续的重复项，如下所示：

输入“你好哦哦哦！！” --> 输出“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;
}
4

11 回答 11

51

如果我将 '\0' 粘贴到分配的内存中间，是否

(a.) free() 仍然可以正常工作，并且

是的。

(b.) '\0' 之后的空格是否变得无关紧要？添加 '\0' 后，内存是否会立即返回，还是会一直占用空间，直到调用 free()？

要看。通常，当您分配大量堆空间时，系统首先分配虚拟地址空间 - 当您写入页面时，会分配一些实际的物理内存来支持它（并且当您的操作系统具有虚拟内存时，这些物理内存可能稍后会被换出到磁盘支持）。众所周知，虚拟地址空间的浪费分配和实际物理/交换内存之间的这种区别允许稀疏数组在此类操作系统上具有合理的内存效率。

现在，这种虚拟寻址和分页的粒度是内存页面大小——可能是 4k、8k、16k...？大多数操作系统都有一个函数，你可以调用它来找出页面大小。因此，如果您正在执行大量小分配，那么四舍五入到页面大小是浪费的，并且如果您的地址空间相对于您真正需要使用的内存量是有限的，那么取决于上述方式的虚拟寻址不会扩展（例如，具有 32 位寻址的 4GB RAM）。另一方面，如果你有一个 64 位进程运行，比如 32GB 的 RAM，并且执行的此类字符串分配相对较少，那么你就有大量的虚拟地址空间可供使用，并且不会舍入到页面大小' t 很多。

但是 - 请注意在整个缓冲区中写入然后在某个较早的时间点终止它（在这种情况下，一次写入的内存将具有后备内存并可能最终进入交换）与拥有一个您只在其中写入的大缓冲区之间的区别到第一位然后终止（在这种情况下，后备内存仅分配给已用空间，向上舍入到页面大小）。

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

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

同样，这取决于您要处理多少这样的分配。如果有很多相对于您的虚拟地址空间/RAM - 您想明确地让内存库知道并非所有最初请求的内存实际上都需要使用realloc()，或者您甚至可以strdup()根据实际情况更紧密地分配一个新块。需求（然后free()是原始的） - 取决于您的 malloc/free 库实现可能会更好或更差，但很少有应用程序会受到任何差异的显着影响。

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

您评论另一个答案：

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

如果性能是您的首要任务，那么是的 - 您想要配置文件。如果您不受 CPU 限制，那么作为一般规则，采用“预处理”命中并进行适当大小的分配 - 碎片和混乱更少。与此相反，如果您必须为某些功能编写特殊的预处理模式 - 这是错误和代码维护的额外“表面”。asprintf()（在实现你自己的from时通常需要这种权衡决定snprintf()，但至少你可以相信snprintf()它会按照记录的方式行事，而不必亲自维护它）。

于 2012-04-16T09:30:28.443 回答
35

添加 '\0' 后，内存是否会立即返回，还是会一直占用空间，直到调用 free()？

没有什么神奇的\0。realloc如果你想“缩小”分配的内存，你必须打电话。否则，内存只会坐在那里，直到您调用free。

如果我将 '\0' 粘贴到分配内存的中间，（a.） free() 是否仍然可以正常工作

无论您在该内存中 free做什么，只要将malloc. 当然，如果你在外面写，所有的赌注都没有了。

于 2012-04-16T08:27:35.167 回答
11

\0只是从另一个角度来看的另一个角色malloc，free他们不在乎您在内存中放入了什么数据。因此free，无论您\0在中间添加还是根本不添加，它仍然有效\0。\0分配的额外空间仍然存在，一旦添加到内存中，它就不会返回给进程。我个人更愿意只分配所需的内存量，而不是分配在某个上限，因为那样只会浪费资源。

于 2012-04-16T08:30:18.130 回答
7

这\0是将字符数组解释为字符串的纯粹约定 - 它独立于内存管理。也就是说，如果你想取回你的钱，你应该打电话给realloc. 该字符串不关心内存（这是许多安全问题的根源）。

于 2012-04-16T08:29:28.990 回答
7

一旦通过调用 malloc() 从堆中获取内存，内存就可以使用了。插入 \0 就像插入任何其他字符一样。在您释放它或操作系统将其收回之前，该内存将一直由您拥有。

于 2012-04-16T08:29:49.960 回答
5

malloc 只是分配一块内存..它由你来使用，但是你想要并从初始指针位置调用 free ......在中间插入 '\0' 没有任何后果......

具体来说 malloc 不知道你想要什么类型的内存（它只返回一个 void 指针）..

让我们假设您希望分配 10 字节的内存，从 0x10 到 0x19 ..

char * ptr = (char *)malloc(sizeof(char) * 10);

在第 5 个位置 (0x14) 插入空值不会释放 0x15 以后的内存...

但是，从 0x10 中释放会释放整个 10 个字节的块。

于 2012-04-16T08:29:27.643 回答
4

  1. free()仍然可以在内存中使用 NUL 字节

  2. 空间将一直浪费，直到free()被调用，或者除非您随后缩小分配

于 2012-04-16T08:28:02.960 回答
3

一般来说，记忆就是记忆。它不在乎你在里面写了什么。但是它有一个种族，或者如果你更喜欢一种风格（malloc、new、VirtualAlloc、HeapAlloc 等）。这意味着分配一块内存的一方还必须提供释放它的方法。如果您的 API 包含在 DLL 中，那么它应该提供某种免费功能。这当然会给调用者带来负担，对吧？那么为什么不把所有的负担都放在来电者身上呢？处理动态分配内存的最佳方法是不要自己分配它。让调用者分配它并将其传递给您。他知道他分配了什么味道，并且他有责任在他用完它时释放它。

调用者如何知道要分配多少？像许多 Windows API 一样，您的函数在调用时返回所需的字节数，例如使用 NULL 指针，然后在提供非 NULL 指针时执行该工作（如果适合您的情况，请使用 IsBadWritePtr 来仔细检查可访问性）。

这也可以更有效率。内存分配成本很高。太多的内存分配会导致堆碎片，然后分配成本会更高。这就是为什么在内核模式中我们使用所谓的“后备列表”。为了尽量减少完成的内存分配次数，我们使用 NT 内核为驱动程序编写者提供的服务重用我们已经分配和“释放”的块。如果您将内存分配的责任转嫁给调用者，那么他可能会从堆栈（_alloca）中向您传递廉价的内存，或者一遍又一遍地向您传递相同的内存而没有任何额外的分配。你当然不在乎，但你确实允许你的调用者负责优化内存处理。

于 2012-04-18T03:04:46.640 回答
1

详细说明 C 中 NULL 终止符的使用：您不能分配“C 字符串”，您可以分配一个 char 数组并在其中存储一个字符串，但 malloc 和 free 只是将其视为请求长度的数组。

AC 字符串不是数据类型，而是使用 char 数组的约定，其中空字符 '\0' 被视为字符串终止符。这是一种传递字符串的方法，而无需将长度值作为单独的参数传递。其他一些编程语言具有显式的字符串类型，可以将长度与字符数据一起存储，以允许在单个参数中传递字符串。

将其参数记录为“C 字符串”的函数会传递 char 数组，但如果没有空终止符，则无法知道该数组有多大，因此如果不存在，事情就会变得非常糟糕。

您会注意到期望 char 数组不一定被视为字符串的函数将始终需要传递缓冲区长度参数。例如，如果要处理零字节为有效值的字符数据，则不能使用 '\0' 作为终止符。

于 2012-04-18T00:39:24.910 回答
1

你可以做一些 MS Windows API 所做的事情，你（调用者）传递一个指针和你分配的内存大小。如果大小不够，系统会告诉您要分配多少字节。如果足够，则使用内存，结果是使用的字节数。

因此，关于如何有效使用内存的决定留给了调用者。他们可以分配一个固定的 255 字节（在 Windows 中使用路径时很常见）并使用函数调用的结果来了解是否需要更多字节（由于 MAX_PATH 为 255 而没有绕过 Win32 API 的路径不是这种情况）或者大多数字节数可以忽略...调用者也可以传递零作为内存大小，并被告知确切需要分配多少 - 在处理方面效率不高，但在空间方面可能更有效。

于 2012-04-18T03:29:21.780 回答
1

您当然可以预先分配到上限，并使用全部或更少。只要确保您实际使用全部或更少。

两次通过也很好。

你问了关于权衡的正确问题。

你如何决定？

最初使用两遍，因为：

1. you'll know you aren't wasting memory.
2. you're going to profile to find out where
   you need to optimize for speed anyway.
3. upperbounds are hard to get right before
   you've written and tested and modified and
   used and updated the code in response to new
   requirements for a while.
4. simplest thing that could possibly work.

您也可以稍微收紧代码。越短通常越好。代码利用已知事实的次数越多，我就越觉得它按照它所说的去做。

char* copyWithoutDuplicateChains(const char* str)
    {
    if (str == NULL) return NULL;

    const char* s = str;
    char prev = *s;               // [prev][s+1]...
    unsigned int outlen = 1;      // first character counted

    // Determine length necessary by mimicking processing

    while (*s)
        { while (*++s == prev);  // skip duplicates
          ++outlen;              // new character encountered
          prev = *s;             // restart chain
        }

    // Construct output

    char* outstr = (char*)malloc(outlen);
    s = str;
    *outstr++ = *s;               // first character copied
    while (*s)
        { while (*++s == prev);   // skip duplicates
          *outstr++ = *s;         // copy new character
        }

    // done

    return outstr;
    }
于 2012-04-23T01:53:16.727 回答