Vector reallocation

[newbiecpp]

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!

[Victor Bazarov]

newbiecpp wrote:

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?

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

[John Harrison]

On Mon, 26 Jul 2004 19:52:46 GMT, newbiecpp <ne*******@yahoo.com> wrote:

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.

John

[Andrey Tarasevich]

John Harrison wrote:

...

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.
...

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

[red floyd]

Andrey Tarasevich wrote:

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.

So in essence, it uses a Fibonacci allocation. (The ratio of
Fib(n)/Fib(n-1) approaches the (1+sqrt(5))/2) as n approaches infinity).

[Victor Bazarov]

"red floyd" <no*****@here.dude> wrote...

Andrey Tarasevich wrote:

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.

So in essence, it uses a Fibonacci allocation. (The ratio of
Fib(n)/Fib(n-1) approaches the (1+sqrt(5))/2) as n approaches infinity).

In essence it doesn't. It has to use something below it. And it
is not a "Fibonacci allocation". It's rather a "golden section"
allocation, wouldn't you agree? The ratio was known to ancients
way before Fibonacci defined his sequence.

V

[John Harrison]

>

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.

Any chance of a link, or an indication of where that article might have
been published?

john

[John Harrison]

>

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.

When you say 'typical implementation' are you talking about implementation
of the heap or implementation of vector?

john

[Andrey Tarasevich]

John Harrison wrote:

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.

Any chance of a link, or an indication of where that article might have
been published?

Take a look at this thread in comp.lang.c++.moderated

http://www.google.com/groups?thl=0,1...anet.com#link1

It gives a pretty exhaustive explanation by itself. It also mentions the
article, but somehow I can't find more precise info about it in the
thread (although I seem to remember that someone actually mentioned the
name and the issue of the magazine where it was published).

--
Best regards,
Andrey Tarasevich

[John Harrison]

"John Harrison" <jo*************@hotmail.com> wrote in message
news:opsbr76ymf212331@andronicus...

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.

Any chance of a link, or an indication of where that article might have
been published?

john

Answering my own questions again, but here is a link

http://groups.google.com/groups?q=g:...rldnet.att.net

It's a clever argument but I would have to be convinced its an issue in the
real world.

john