Re: Vector reallocation
From: James Dennett (jdennett_at_acm.org)
Date: 07/26/04
- Next message: Alwyn: "Re: Need another pair of eyes to figure this one out"
- Previous message: Ben Cottrell: "Re: 2 .cpp files"
- In reply to: newbiecpp: "Vector reallocation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 26 Jul 2004 14:43:57 -0700
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 algorithm isn't specified by the C++ standard, so implementations
could vary.
As it happens, the performance (complexity) guarantees of the standard
essentially mandate (at least) exponential growth, so the many area of
difference is in the ratio: some std::vector implementations double
when they need to expand, some multiply their size by 1.5. Exponential
growth has the somewhat counter-intuitive property that when adding n
items to a vector, the number of copies needed grows only proportionally
to n: even though the number of copies at each expansion increases,
expansions become proportionally less common, so the two factors cancel
out nicely.
-- James
- Next message: Alwyn: "Re: Need another pair of eyes to figure this one out"
- Previous message: Ben Cottrell: "Re: 2 .cpp files"
- In reply to: newbiecpp: "Vector reallocation"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
