矢量重新分配 [英] Vector reallocation
问题描述
当您将一个元素插入向量时，如果内部存储器已经使用了
，那么该向量如何分配额外的内存？它只分配一个
单位来满足插入，或者分配一块内存？我guss
向量将分配一块内存。如果这是真的，矢量使用什么算法
？向量如何确定
创建的内存块有多大？
感谢advace！
When you insert an element into a vector, if the internal memory is already
used, how does the vector allocate additional memory? It just allocates one
unit to satisfy the insert, or allocates a chunk of memory? I guss the
vector will allocate a chunk of memory. If this is true, what algorithm
does the vector use? How does vectors decide how big the chunk of memory to
create?
Thanks in advace!
推荐答案
newbiecpp写道：
newbiecpp wrote:
当你将一个元素插入一个向量时，如果已经使用了内部存储器，那么该向量如何分配额外的内存？它只分配一个
单元来满足插入，或者分配一块内存？我guss
向量将分配一块内存。如果这是真的，矢量使用什么算法呢？向量如何决定要创建的内存块有多大？
When you insert an element into a vector, if the internal memory is already
used, how does the vector allocate additional memory? It just allocates one
unit to satisfy the insert, or allocates a chunk of memory? I guss the
vector will allocate a chunk of memory. If this is true, what algorithm
does the vector use? How does vectors decide how big the chunk of memory to
create?
向量分配一个块以保留所有元素的整个序列
（以及更多，如果你想扩展它）使用其分配器
模板参数（当然，你主要使用默认分配器）。它通常使用简单的new []
。大小取决于
要保留的元素数量，或者基于预留'
成员的参数（如果你调用它）。
如果存储空间已经有足够的空间，则不会发生重新分配，但
元素会被向下移动。一个职位通过任务op，
IIRC。
Victor
The vector allocates a chunk to keep the entire sequence of all elements
(and a bit more, in case you want to extend it) using its "Allocator"
template argument (you mostly use the default allocator, of course). It
uses straightforward "new[]", usually. The size is decided based on the
number of elements to keep or based on the argument for the ''reserve''
member (if you called it).
If the storage already has enough room, no reallocation happens, but the
elements are "shifted down" one position by means of the assignment op,
IIRC.
Victor
在星期一， 2004年7月26日19:52:46 GMT，newbiecpp< ne ******* @ yahoo.com>写道：
On Mon, 26 Jul 2004 19:52:46 GMT, newbiecpp <ne*******@yahoo.com> wrote:
当你将一个元素插入一个向量时，如果已经使用了内部存储器，那么该向量如何分配额外的内存？它只是分配一个
单元来满足插入，或者分配一块内存？我guss
向量将分配一块内存。如果这是真的，矢量使用什么算法呢？向量如何决定创建内存的大小有多大？
感谢advace！
When you insert an element into a vector, if the internal memory is
already
used, how does the vector allocate additional memory? It just allocates
one
unit to satisfy the insert, or allocates a chunk of memory? I guss the
vector will allocate a chunk of memory. If this is true, what algorithm
does the vector use? How does vectors decide how big the chunk of
memory to
create?
Thanks in advace!
典型策略是将分配的内存加倍。这意味着随着向量变大，
重新分配变得越来越少。在任何情况下，
重新分配必须是现有内存大小的某个倍数。
无法满足矢量的效率要求
添加固定数量的内存。
John
Typical strategy is to double the allocated memory. This means that
reallocations get rarer as the vector gets bigger. In any case the
reallocation must be some multiple of the size of the existing memory. It
is not possible to satisfy the efficiency requirements of a vector by
adding a fixed amount of memory.
John
John Harrison写道：
John Harrison wrote:
...
当你将一个元素插入一个向量时，如果内部存储器已经
使用了，矢量如何分配额外的内存？它只是分配一个
单元来满足插入，或者分配一块内存？我guss
向量将分配一块内存。如果这是真的，矢量使用什么算法呢？向量如何决定创建内存的大小有多大？
感谢advace！
When you insert an element into a vector, if the internal memory is
already
used, how does the vector allocate additional memory? It just allocates
one
unit to satisfy the insert, or allocates a chunk of memory? I guss the
vector will allocate a chunk of memory. If this is true, what algorithm
does the vector use? How does vectors decide how big the chunk of
memory to
create?
Thanks in advace!
典型的策略是加倍分配的内存。这意味着随着向量变大，重新分配变得越来越少。在任何情况下，
重新分配必须是现有内存大小的某个倍数。通过添加固定数量的内存，无法满足矢量的效率要求。
...
Typical strategy is to double the allocated memory. This means that
reallocations get rarer as the vector gets bigger. In any case the
reallocation must be some multiple of the size of the existing memory. It
is not possible to satisfy the efficiency requirements of a vector by
adding a fixed amount of memory.
...
带有_doubling_记忆的策略有一定的缺陷（IIRC，Andrew
Koenig前段时间写了一篇关于此事的文章）。将
容量乘以任何高于（1 + sqrt（5））/ 2的值可能会导致典型实现中的低效内存使用量。 AFAIK，现代
版本的STL倾向于使用1.6作为乘数值。
-
祝你好运，
Andrey Tarasevich
The strategy with _doubling_ the memory has certain flaws (IIRC, Andrew
Koenig wrote an article about this some time ago). Multiplying the
capacity by any value above (1 + sqrt(5))/2 might lead to extremely
inefficient memory usage in typical implementation. AFAIK, modern
version of STL tend to use 1.6 as a multiplier value.
--
Best regards,
Andrey Tarasevich
这篇关于矢量重新分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
