总是建议使用std::vector而不是realloc公平吗?

10

来自Bjarne Stroustrup's FAQ:

如果你感觉需要使用realloc() - 很多人都这样认为 - 那么请考虑使用标准库的vector。

我想先声明一下,std::vector有很多优点,个人而言我总是会选择使用它而不是用C内存分配写动态数组。

但是std::vector随着其增长会导致内存碎片化,因为C++没有类似于realloc的函数(编辑 为了澄清,我知道std::vector的存储是连续的且不会被碎片化,我的意思是由于分配和释放引起的内存空间碎片化,而realloc可以通过扩展现有分配来避免这种情况)。所以总是推荐使用std::vector合理吗?如果小心处理,你不能编写与std::vector完全相同但使用C分配函数的代码吗?这样做可以使其具有增长内存但无需移动其地址并复制现有元素的可能性,从而在碎片化和性能方面达到甚至更好的效果吗?

而且相关的(奖励问题!),为什么C ++没有等效于realloc?在一个如此注重性能的语言中省略这个似乎很奇怪。Bjarne的FAQ中有一个标题完全相同的部分(减去强调),但答案并没有解决“为什么”的问题。这只是一种意外的遗漏吗?与new/delete的工作方式存在一些根本性的不兼容性吗?实践中它是否真的提供了看似的好处?
编辑:好的,我忽略了realloc的C恶心性 - std :: vector不能使用realloc进行重写,因为它仅适用于POD,不会抛出错误等等。也许编写一个专门处理这种恶心情况的POD-only容器对于某些情况来说是一个好主意。无论如何,更有趣的问题变成了:std :: vector是否会从C ++等效的realloc中受益,这在这里已经得到了(或多或少)回答:

std::vector在增加容量时是否必须移动对象?或者分配器可以“重新分配”?

遗憾的是,答案似乎是“是的,但标准委员会没有投票通过”。希望能够实现。


1
“片段内存”指的是地址空间的其余部分,而不是它自己的内存——每当它分配一个新块并释放旧块时,它都会导致碎片化。realloc有能力扩展现有块,这肯定比那好得多吧? - Ben Hymers
1
@Ben:在这个上下文中,“碎片化”意味着通过分配一个块然后释放另一个块来留下堆中的空隙,这可能会减少堆中可用块的数量。当然,向量使用的内存是单个连续块,因为这是其规范所要求的。 - Mike Seymour
1
你尝试在 Stack Overflow 上搜索是否有现成的答案了吗?那里已经有好几个类似的问题被回答过了。如果它们不能满足你的需求,你可以引用其中一个或两个并解释原因。 - n. m.
1
您可能会对 https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md 感兴趣。 - user541686
显示剩余8条评论
4个回答

10

new/new[]delete/delete[]通常是在C库分配函数(如malloc/realloc/free)之上构建的,可能还有一个额外的层用于小对象优化,它使用一个malloc区域快速满足许多小new请求。这种层叠意味着早期C++库作者支持newdelete时付出的实现努力非常少。

然而,要在C++中利用realloc中的原地调整大小功能,需要对realloc库函数进行侵入式更改,以便如果需要移动到新的内存区域,则C++库代码有机会复制构造/析构正在移动的对象。可以这样做:

  • realloc实现移动操作之后发生的回调,请求C++库执行实际的数据移动而不是进行memcpy()风格的逐字节复制,或者

  • 作为一种额外的就地调整大小或失败而不移动函数,以便C++库代码可以尝试该函数,然后在删除原始对象和释放原始内存之前回退到malloc和适当/安全的复制。

由于大多数C库的realloc函数缺乏任何此类钩子/查询功能,因此C++标准和标准库不需要它。正如Mehrdad指出的那样,this answer记录了SGI对此问题的认识。

鉴于这些天C ++的广泛使用,把一个malloc/realloc/free实现提供这样的钩子/查询放入C ++库中是有意义的,以便C ++库作者可以自由地利用realloc。这将成为未来标准中值得考虑的候选项目。
通过非常小心的设计,您不能编写类似std::vector但使用C分配函数的程序,它具有增长内存的可能性而无需移动其地址和复制现有元素,使其在碎片化和性能方面与原始的方法一样好或更好。
如上所述,如果不更改realloc API,则无法通过任何小心翼翼的方式进行对象的复制构造/析构。

优秀的回答!谢谢你! - Ben Hymers
2
@phresnel:你没有理解我的观点-在你提供的源代码的第42行,你会看到调用了malloc,证明实现确实使用了C库堆管理,这意味着realloc可以尝试原地增长内存区域,但是我的回答解释了,在“必须移动”的情况下,任何实际使用realloc都无法与C ++对象的适当复制构造/销毁协调,因为接口不提供预移动钩子或仅在可以原地执行调整大小的选项。 - Tony Delroy
1
@BenHymers:我确实是指 malloc/realloc/free - 它们都是相关的函数,事实上 realloc 可以用于初始内存分配和释放,因此如果 C++ 库希望,它可以仅使用 realloc 而不使用 mallocfree,即使从未尝试将任何现有分配调整为除 0 字节之外的任何其他大小(一个 free)。但这会导致代码更加混乱。简而言之:realloc(0, n) === malloc(n)realloc(p, 0) === free(p) - Tony Delroy
1
@phresnel:小对象优化并非强制性的,纯粹是实现库的选择。特别是对于像Linux这样的系统,GNU有自由调整C库例程以很好地处理小对象,因此没有太多的动力在其上添加C++库优化。历史上,这更与第三方C++编译器在不同质量的C库上移植到操作系统有关。在C中,往往会分配较少但较大的内存,并且生命周期较长,因此库通常不会进行过多的调整。 - Tony Delroy
1
@TonyDelroy - 就我所知,我认为realloc可以用作向量调整大小期间分配的基本机制,但它必须仅针对可平凡复制类型进行专门化(类似于曾经称为POD类型的内容)。这实际上并不那么不寻常:大多数标准库实现已经为可平凡复制类型专门化了容器,以便可以使用memcpy复制元素 - 除了其他专门化,如如果析构函数是平凡的,则跳过销毁等。 - BeeOnRope
显示剩余19条评论

2

Direct comparison

                        |  std::vector     | C memory functions
------------------------+------------------+------------------------
default capacity        | undefined        | undefined
default grow            | towards capacity | undefined
deterministic capacity  | available        | no
deterministic grow      | available        | no
deterministic mem.-move | available        | no
non-POD types           | yes              | f***ing no (*)
no-throw                | no               | yes

deterministic mem.-move是从deterministic capacity/grow推导出来的。当reallocstd::vector不得不将其存储的元素移动到新的内存位置时,就会发生这种情况。

我认为,在考虑任何类型的移动(智能)引用时,内存移动方面的(可用的)确定性是双重重要的。

注意:在这方面,我使用“确定性”一词与我的源代码生命周期相关,即其跨不同版本的不同库以及具有不同编译标志等的生命周期。


它像realloc一样会使内存碎片化:

类模板vector概述[vector.overview]

向量的元素被连续存储,这意味着如果v是一个vector<T,Allocator>,其中T是除bool之外的某种类型,则对于所有0<= n < v.size(),都遵循恒等式&v[n] == &v[0] + n

换句话说,所使用的内存是连续的。

它与realloc的一个重大区别是,realloc实际上可以在没有明确指示的情况下增加已分配的内存部分,但不需要这样做(man 3 realloc):

man 3 realloc

realloc()函数将指针ptr所指向的内存块的大小更改为size字节。范围从该区域开始到旧大小和新大小的最小值的范围内的内容将保持不变。如果新大小大于旧大小,则添加的内存将不会初始化。如果ptr为空,则对于所有大小值,调用等效于malloc(size);如果size等于零,并且ptr不为空,则调用等效于free(ptr)。除非ptr为空,否则它必须由先前的malloc()calloc()realloc()调用返回。如果指向的区域被移动,则执行free(ptr)

因此,它可以增加大小,但不一定要这样做。

std::vector不仅携带size,还携带capacity。如果您预先知道需要一个大的vector,但是现在无法初始化所有内容,则可以像这样增加向量的容量:

std::vector<T> vec(32);
vec.reserve(1024);
// vec has size 32, but reserved a memory region of 1024 elements

因此,与realloc不同的是,使用std::vector可以确定重新分配发生的时机。
回答您的问题:因为有了std::vector,所以不需要使用realloc。而且,对于非POD类型,不允许使用mallocfreerealloc函数;对非POD类型直接使用这些函数会导致未定义的行为。

1
@BenHymers:但是realloc也可能会留下空洞,对吗? - Sebastian Mach
7
-1 糟糕的回答... 有意义的问题是,C++类型是否可以在内部使用realloc来扩展内存使用,而不是比较原始的reallocvector - Tony Delroy
3
我认为这个问题并不是很有意义,你在试图回答它时写了一些毫无意义的东西。例如:一个人为N个对象重新分配/分配足够的字节给出了与reserve相似的“确定性容量”,你的某些陈述似乎暗示没有“当前大小”变量与分配内存的指针配对。关于vector的增长,没有比realloc更加确定性 - 任何一个都可能因内存耗尽而失败,或者看起来成功然后在实际访问内存时失败。 - Tony Delroy
2
@phresnel 非确定性,但方向正确 :) 我在 Mike Seymour 的回答评论中提到,“如果性能和内存使用模式偶尔比正常情况更好,我会很高兴”。首先提出 realloc 的整个重点是它有扩展现有分配的选项,听起来很不错。还要注意的是,我仅在向量需要分配时讨论此问题,并且一个使用 realloc 的向量仍将分配额外的容量并具有 reserve 方法;只是在分配时会有所不同。 - Ben Hymers
2
这个答案基本上是在创造一个稻草人:一个容器,每次大小变化都使用realloc,而不是使用单独的容量+大小成员来内部跟踪容量。当然,那样做会很糟糕。正确的方法是在其上使用std::vector(对于平凡可复制类型),而不是使用新的/复制/删除循环。因此,有时您仍然会在增长时得到一份副本,但有时您可以避免这种性能损失,只需扩展现有分配。最坏情况相同,平均情况要好得多,尤其是在有大量空闲虚拟地址空间的情况下,最好的情况要好得多。 - Peter Cordes
显示剩余11条评论

2

为什么C++没有realloc,这里不再赘述,可以参考这里

值得一提的是,一个合适的vector实现可以在一定程度上缓解碎片问题,通过选择接近黄金比例的增长因子,详情请见此链接,所以并非完全无解。


我不确定他们的解释有什么帮助,他们没有说明为什么会禁止 C 的 realloc,只是说它会。C 和 C++ 的内存分配不应该交互,所以我不明白为什么会有一个 cplusplusrealloc,它不会干扰 C 的内存分配,但可以与 new/delete 一起使用。 - Ben Hymers
1
@BenHymers:在他们链接的页面上已经解释了。问题在于realloc复制原始内存,这意味着它对C++不起作用,因为C++需要使用复制构造函数。是的,他们本可以添加一个不同的重新分配函数,但他们解释了为什么没有这样做:“这反过来会增加许多分配器实现的复杂性,并使与内存调试工具的交互更加困难。因此,我们决定不采用这种替代方案。” - user541686
1
哈哈,因为会增加复杂性而决定不将某些东西添加到C++中,这让我感到好笑 :) 但是好吧,这是一个解释,说得有道理。 - Ben Hymers
1
@BenHymers:我知道,对吧?我想那时候它还没有现在这么庞大。=P - user541686

1

std::vector在增长时会分段内存,因为C++没有等价的realloc

realloc会以相同的方式分段内存,因为它正在做相同的事情-如果旧块不够大,则分配一个新块并复制内容。

你不能小心地编写一些东西,它的工作方式与使用C分配函数的std::vector完全相同,它具有增加内存而不移动其地址和复制现有元素的可能性,从而使其在碎片化和性能方面至少与std::vector一样好吗?

这正是vector所做的。您可以独立于大小控制容量,仅在超过容量时重新分配。 realloc类似,但没有控制容量的手段-这使得vector在碎片化和性能方面更好。

为什么C ++没有与realloc等效的功能?

因为它具有 std::vector,可以以更灵活的方式执行相同的操作。除了允许您精确控制内存分配的时间和方式外,它还可以与任何可移动类型一起使用,而在使用非平凡类型时,realloc 会出现严重问题。

3
“realloc会以相同的方式使内存碎片化” - 不一定;它可能会扩展现有的内存块,这就是关键 :)当然,对于非平凡类型,基于realloc的容器会失败,我没有考虑到这一点。 - Ben Hymers
1
@BenHymers:“它可能会扩展现有块” - 或者可能不会,而且您无法控制。如果碎片化很重要,则vector提供了使用reserve或自定义分配器来管理它的工具;realloc只是做它该做的事情。如果碎片化不重要,则没有关系。 - Mike Seymour
3
@MikeSeymour...但它也可能会出现这种情况!如果性能和内存使用模式偶尔比正常情况 更好 ,我会很高兴。 vector 给了我一些工具,但它无法让我扩展现有的内存分配。reserve 只有在我事先知道容量时才有帮助。 - Ben Hymers
“点”是,std::vector 有所有这些控制以管理容量和大小,例如 reserve,而 realloc 没有意义。realloc 不是一个容器。我们正在讨论在 realloc 上实现像 vector 这样的容器。显然,这样容器的良好实现也会有 “size” 和 “capacity”,不会盲目地在每添加一个元素时调用 realloc(这可能会导致可怕的性能和碎片化)。 - BeeOnRope
2
现在你有了与“vector”相同的最坏情况性能、功能等内容,但有时你会获得“免费胜利”的好处,即能够将元素保留在原地而不必在扩展时复制它们——这涉及到所有的内存带宽、缓存抖动和 CPU 时间。当然,缺点是它只适用于简单可复制类型(技术上它可以适用于任何“位移可移动”的类型,但 C++ 还没有正式规范这样的概念)。 - BeeOnRope

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接