 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Dhruv Matani
Guest
|
 Posted: Mon Oct 25, 2004 6:21 pm Post subject: should std::vector<> exponential growth rate be followed str |
 |
|
Hello,
I recently had a discussion about whether the exponential growth policy
for std::vector<> should be followed strictly no matter what.
The case I'm looking at is something like this:
const int init_sz = 1.2 * 1024 * 1024 * 1024; // 1.2GB.
std::vector<char> cv(init_sz);
cv.push_back('a');
Now, what a 'typical' vector implementation would do is:
Allocate space for init_sz chars, and default construct them.
When the push_back function is called, something along these lines happens
inside the vector:
Assume that the growth factor is 2.
1. Allocate space(memory) having size cv.capacity() * 2.
2. Copy the old contents into the newly allocated memory block.
3. Deallocate the old block.
Now, in this case, the vector had an old capacity of init_sz, and
2*init_sz would be such that init_sz+2*init_sz is > 3GB. Linux(32-bit)
supports a max of 3GB segments for the application's data, so clearly the
allocator would not be able to provide the required memory. What I'm now
thinking about is should the standard be permissive and allow the vector
to start growing slowly now, say increase the size by 10 elements to
prevent bad_alloc from being thrown?
What my argument is that an implementations should be allowed to deviate
slightly from the standard to prevent useless exception like the above
from being thrown. It should be clear that from the user's point of view,
what he sees is that he already has 1.2GB of data, and he is trying to add
1-byte to that! Why for any reason should that fail? Assume that the user
is in no position to use reserve. Obviously if that is considered, then
the whole post is useless ;-)
Reagrds,
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
 |
Ron Natalie
Guest
|
| Posted: Mon Oct 25, 2004 7:50 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
Dhruv Matani wrote:
| Quote: | Hello,
I recently had a discussion about whether the exponential growth policy
for std::vector<> should be followed strictly no matter what.
|
The standard doesn't mandate any particular policy other than that
the amortized cost for extending the array size be constant.
If you want to roll off the expansion as the memory gets closer
to some known limit, that would be legitimate.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dave Harris
Guest
|
| Posted: Mon Oct 25, 2004 10:36 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
[email]dhruvbird (AT) gmx (DOT) net[/email] ("Dhruv Matani") wrote (abridged):
| Quote: | Now, in this case, the vector had an old capacity of init_sz, and
2*init_sz would be such that init_sz+2*init_sz is > 3GB. Linux(32-bit)
supports a max of 3GB segments for the application's data, so clearly
the allocator would not be able to provide the required memory. What
I'm now thinking about is should the standard be permissive and
allow the vector to start growing slowly now, say increase the size
by 10 elements to prevent bad_alloc from being thrown?
|
But than adding N elements would mean copying the 1.2Gb already in the
vector N/10 times. That would be terribly slow.
std::vector has a max_size() member, which in your case should reflect the
3Gb limit. It would be reasonable for a vector to grow to min( max_size(),
capacity()*2 ). And it would be conforming, too - no conforming program
could tell the difference.
Incidently, many implementations use a factor of 1.5 rather than 2, so
they don't grow quite as quickly. 1.2Gb + 1.5*1.2Gb = 3Gb, so you are in
luck, as long as you don't have anything else consuming memory :-)
-- Dave Harris, Nottingham, UK
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
chris
Guest
|
| Posted: Tue Oct 26, 2004 9:18 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
Dhruv Matani wrote:
| Quote: | Hello,
I recently had a discussion about whether the exponential growth policy
for std::vector<> should be followed strictly no matter what.
The case I'm looking at is something like this:
const int init_sz = 1.2 * 1024 * 1024 * 1024; // 1.2GB.
std::vector<char> cv(init_sz);
cv.push_back('a');
...
Assume that the growth factor is 2.
...
What my argument is that an implementations should be allowed to deviate
slightly from the standard to prevent useless exception like the above
from being thrown. It should be clear that from the user's point of view,
what he sees is that he already has 1.2GB of data, and he is trying to add
1-byte to that! Why for any reason should that fail? Assume that the user
is in no position to use reserve. Obviously if that is considered, then
the whole post is useless 
If your only aim is to remain standards compliant, then one option would |
be to reduce what you claim the minimum growth factor will be in tight
memory situations, say to 1.05. If you can't extend the vector by at
least 5% then is it really worth doing it? In this way you could perform
better in low memory situations but still be standard compliant.
If you wanted to be really sick, you could claim that your minimum
growth factor is 1+5*10^(-20), which would mean that on a system with a
64-bit address space you would still never have to expand by more than
1, but I believe you could still claim to be standards compliant ;)
Chris
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dhruv Matani
Guest
|
| Posted: Wed Oct 27, 2004 3:43 am Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
On Tue, 26 Oct 2004 21:18:18 +0000, chris wrote:
| Quote: | Dhruv Matani wrote:
Hello,
I recently had a discussion about whether the exponential growth policy
for std::vector<> should be followed strictly no matter what.
The case I'm looking at is something like this:
const int init_sz = 1.2 * 1024 * 1024 * 1024; // 1.2GB.
std::vector<char> cv(init_sz);
cv.push_back('a');
..
Assume that the growth factor is 2.
..
What my argument is that an implementations should be allowed to deviate
slightly from the standard to prevent useless exception like the above
from being thrown. It should be clear that from the user's point of view,
what he sees is that he already has 1.2GB of data, and he is trying to add
1-byte to that! Why for any reason should that fail? Assume that the user
is in no position to use reserve. Obviously if that is considered, then
the whole post is useless
If your only aim is to remain standards compliant, then one option would
be to reduce what you claim the minimum growth factor will be in tight
memory situations, say to 1.05. If you can't extend the vector by at
least 5% then is it really worth doing it? In this way you could perform
better in low memory situations but still be standard compliant.
If you wanted to be really sick, you could claim that your minimum
growth factor is 1+5*10^(-20), which would mean that on a system with a
64-bit address space you would still never have to expand by more than
1, but I believe you could still claim to be standards compliant
|
Yes, but it would obviously be a nonsense implementation as you have
mentioned. I'm looking more at making it allowable by the standard in
such low memory situations to deviate from the exponential growth
policy.
Reagrds,
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dhruv Matani
Guest
|
| Posted: Fri Oct 29, 2004 5:55 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
On Mon, 25 Oct 2004 22:36:44 +0000, Dave Harris wrote:
| Quote: | dhruvbird (AT) gmx (DOT) net ("Dhruv Matani") wrote (abridged):
Now, in this case, the vector had an old capacity of init_sz, and
2*init_sz would be such that init_sz+2*init_sz is > 3GB. Linux(32-bit)
supports a max of 3GB segments for the application's data, so clearly
the allocator would not be able to provide the required memory. What
I'm now thinking about is should the standard be permissive and
allow the vector to start growing slowly now, say increase the size
by 10 elements to prevent bad_alloc from being thrown?
But than adding N elements would mean copying the 1.2Gb already in the
vector N/10 times. That would be terribly slow.
std::vector has a max_size() member, which in your case should reflect the
3Gb limit. It would be reasonable for a vector to grow to min( max_size(),
capacity()*2 ). And it would be conforming, too - no conforming program
could tell the difference.
Incidently, many implementations use a factor of 1.5 rather than 2, so
they don't grow quite as quickly. 1.2Gb + 1.5*1.2Gb = 3Gb, so you are in
luck, as long as you don't have anything else consuming memory 
|
Yes, but practically it is not the case, so when the user just wanted to
add 1 more entry and the vector fails is much worse IMHO to copy 1.2Gb in
large amount of time and have the operation succeed.
Regards,
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dave Harris
Guest
|
| Posted: Wed Nov 03, 2004 7:28 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
[email]dhruvbird (AT) gmx (DOT) net[/email] ("Dhruv Matani") wrote (abridged):
| Quote: | Yes, but practically it is not the case, so when the user just wanted to
add 1 more entry and the vector fails is much worse IMHO to copy 1.2Gb
in large amount of time and have the operation succeed.
|
What I had in mind was that the vector would not fail, but would instead
grow to the largest capacity which would succeed. (Probably it would need
to attempt to grow, catch the bad_alloc and then try again with a smaller
size, rather than use max_size().) I suggest that would be better than
growing by exactly 10 elements.
I think that would be conforming; I don't think the standard need change
to permit it. The notion of "amortised constant time" is a bit wooly
anyway if subsequent growths are going to fail.
I suppose there may be pathological cases where some other process is
releasing memory at the same rate the vector is growing, so the too-slow
growth might continue indefinitely. Perhaps the vector needs a minimum
growth rate and must fail if that is not reached - but it could be very
low.
In practice, programs which /nearly/ run out of memory usually /do/ run
out of memory, given just a bit more time. So we are probably just
postponing the inevitable and the real fix is to get more memory. As such
it probably isn't worth much extra complexity in std::vector.
Whether a timely fail is better than a delayed success is deep question.
For the C++ standard, "time is the essence of the contract" and a late
answer is a wrong one. I think a variation like, "Push_back() takes
amortised constant time unless memory is nearly full" would be too vague
to be useful.
-- Dave Harris, Nottingham, UK
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Tom Widmer
Guest
|
| Posted: Thu Nov 04, 2004 10:29 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
On Wed, 27 Oct 2004 03:43:46 GMT, [email]dhruvbird (AT) gmx (DOT) net[/email] ("Dhruv Matani")
wrote:
| Quote: | Yes, but it would obviously be a nonsense implementation as you have
mentioned. I'm looking more at making it allowable by the standard in
such low memory situations to deviate from the exponential growth
policy.
|
And the standard already allows that, since it doesn't specify
"exponential growth", but rather amortized constant time push_back.
However, I don't think a 1GB+ std::vector is a very good idea in any
case. If you use malloc, then you get access to realloc, or you should
perhaps be using a custom allocator, or redesigning your algorithm,
perhaps to allow a segmented container of some kind, or to use less
RAM.
Tom
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dhruv Matani
Guest
|
| Posted: Fri Nov 05, 2004 6:18 am Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
On Thu, 04 Nov 2004 22:29:30 +0000, Tom Widmer wrote:
| Quote: | On Wed, 27 Oct 2004 03:43:46 GMT, [email]dhruvbird (AT) gmx (DOT) net[/email] ("Dhruv Matani")
wrote:
Yes, but it would obviously be a nonsense implementation as you have
mentioned. I'm looking more at making it allowable by the standard in
such low memory situations to deviate from the exponential growth
policy.
And the standard already allows that, since it doesn't specify
"exponential growth", but rather amortized constant time push_back.
However, I don't think a 1GB+ std::vector is a very good idea in any
case. If you use malloc, then you get access to realloc, or you should
perhaps be using a custom allocator, or redesigning your algorithm,
perhaps to allow a segmented container of some kind, or to use less
RAM.
|
Yes, but in certain cases, it becomes necessary for using such big
vectors. Like in my case, I want to use it as a replacement for
std::multimap<>, because:
1. The locality of the nodes is destroyed by the re-balancing algorithm,
and
2. Every insertion involves touching a lot of data, so places where data
is coming in at a very fast rate, this is unacceptable.
So, I would rather use a vector and then sort it after all the insertions
are over.(because the application/use happens to be ammenable to that
change).
Here, I know in advance the maximum size of the vector, but in other cases
I might not. Now, given that fact that I have say 2GB of Phy. mem. I
should not be consrtained by the exponential growth policy.
Also, as others have mentioned, the underlying implementation could use
1.5 as the factor, but then, again that would cause a lot of copies
unnecessarily. Esp. for a heavy copying object.
But, then again looking at Dave Harris' reply, I'm not quite convinced
about the way I'm using vector?
Maybe?
Reards,
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dhruv Matani
Guest
|
| Posted: Fri Nov 05, 2004 7:00 am Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
On Wed, 03 Nov 2004 19:28:54 +0000, Dave Harris wrote:
| Quote: | dhruvbird (AT) gmx (DOT) net ("Dhruv Matani") wrote (abridged):
Yes, but practically it is not the case, so when the user just wanted to
add 1 more entry and the vector fails is much worse IMHO to copy 1.2Gb
in large amount of time and have the operation succeed.
What I had in mind was that the vector would not fail, but would instead
grow to the largest capacity which would succeed. (Probably it would need
to attempt to grow, catch the bad_alloc and then try again with a smaller
size, rather than use max_size().) I suggest that would be better than
growing by exactly 10 elements.
I think that would be conforming; I don't think the standard need change
to permit it. The notion of "amortised constant time" is a bit wooly
anyway if subsequent growths are going to fail.
I suppose there may be pathological cases where some other process is
releasing memory at the same rate the vector is growing, so the too-slow
growth might continue indefinitely. Perhaps the vector needs a minimum
growth rate and must fail if that is not reached - but it could be very
low.
|
Ok, something like the silly window syndrome?
| Quote: |
In practice, programs which /nearly/ run out of memory usually /do/ run
out of memory, given just a bit more time. So we are probably just
postponing the inevitable and the real fix is to get more memory. As such
it probably isn't worth much extra complexity in std::vector.
|
Yes, that's also true. And the extra complexity is probably not called for
anyway.
But, there are a few (maybe very few) cases where this does not happen.
Now singling those cases where the program actually crashes from those
where it does not would be very difficult for the vector to tell, and
could definitely not foretell the future!
| Quote: |
Whether a timely fail is better than a delayed success is deep question.
For the C++ standard, "time is the essence of the contract" and a late
answer is a wrong one. I think a variation like, "Push_back() takes
amortised constant time unless memory is nearly full" would be too vague
to be useful.
|
I guess what has let the cat out of the bag is the description of
vector<>::max_size(), which says that it denotes not the maximum
practical capacity, but the theoretical maximum.
Regards,
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Michael Karcher
Guest
|
| Posted: Fri Nov 05, 2004 3:52 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
"Dhruv Matani" <dhruvbird (AT) gmx (DOT) net> wrote:
| Quote: | case. If you use malloc, then you get access to realloc, or you should
perhaps be using a custom allocator, or redesigning your algorithm,
perhaps to allow a segmented container of some kind, or to use less
RAM.
[I don't use multimap because...]
2. Every insertion involves touching a lot of data, so places where data
is coming in at a very fast rate, this is unacceptable.
|
If data is coming in at a very fast rate, why don't you use a deque (a
segmented container, as you were told).
Michael Karcher
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
johnchx
Guest
|
| Posted: Fri Nov 05, 2004 3:52 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
[email]dhruvbird (AT) gmx (DOT) net[/email] ("Dhruv Matani") wrote
| Quote: | 2. Every insertion involves touching a lot of data, so places where data
is coming in at a very fast rate, this is unacceptable.
|
If you need *consistently* fast push_back() times -- to keep up with a
fast input source, for instance -- then vector's amortized-constant
time probably won't be good enough. Amortized-constant time is fine
if you don't mind the application grinding to a halt from time to time
while reallocation is performed, but it sounds like you may not be
able to afford it.
| Quote: | Here, I know in advance the maximum size of the vector, but in other cases
I might not.
|
Your best bet is probably to use vector only if you know the maximum
size in advance. If you can reserve() sufficient space up-front, you
don't have to worry about re-allocation. If you can't, and you can't
afford long copy times while receiving input, you'll probably be
better off with a deque.
| Quote: | Now, given that fact that I have say 2GB of Phy. mem. I
should not be consrtained by the exponential growth policy.
|
Physical memory is probably irrelevant. The real constraint is more
likely to be the amount of unfragmented space available in the portion
of the virtual address space of the process which is earmarked for
heap allocation. If you don't absolutely need the entire data
structure to be in a single continguous chunk of address space, you'll
get better results (fewer bad_alloc exceptions, no copies, no
reallocation delays) from a deque.
Of course, it's not hard to implement your "reallocation fallback"
policy with a wrapper function like this:
template < class T, class A >
void modified_push_back ( std::vector<T,A>& v, const T& t )
{
try {
v.push_back(t);
}
catch (std::bad_alloc&) {
std::vector<T,A> v2;
v2.reserve(v.capacity() + 1 ); // or whatever
std::copy( v.begin(), v.end(), std::back_inserter(v2) );
v.swap(v2);
}
}
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dhruv Matani
Guest
|
| Posted: Sat Nov 06, 2004 6:39 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
On Fri, 05 Nov 2004 15:52:42 +0000, johnchx wrote:
| Quote: | dhruvbird (AT) gmx (DOT) net ("Dhruv Matani") wrote
2. Every insertion involves touching a lot of data, so places where data
is coming in at a very fast rate, this is unacceptable.
If you need *consistently* fast push_back() times -- to keep up with a
fast input source, for instance -- then vector's amortized-constant
time probably won't be good enough. Amortized-constant time is fine
if you don't mind the application grinding to a halt from time to time
while reallocation is performed, but it sounds like you may not be
able to afford it.
|
You're probably right, but before going one way or the other I would like
to profile and see for myself what the actual situation would be like
practically. I would tend to agree with your observation as of now though.
| Quote: |
Here, I know in advance the maximum size of the vector, but in other cases
I might not.
Your best bet is probably to use vector only if you know the maximum
size in advance. If you can reserve() sufficient space up-front, you
don't have to worry about re-allocation. If you can't, and you can't
afford long copy times while receiving input, you'll probably be
better off with a deque.
|
Yes, even Michael Karcher has mentioned that, and it seems like a nice
prospect. Again, iteration would suffer here. And believe me, iteration is
quite slow compared to vector's, but I have to first concretely apply both
the containers and time and then make any non-naive observations.
| Quote: |
Now, given that fact that I have say 2GB of Phy. mem. I
should not be consrtained by the exponential growth policy.
Physical memory is probably irrelevant. The real constraint is more
likely to be the amount of unfragmented space available in the portion
of the virtual address space of the process which is earmarked for
heap allocation. If you don't absolutely need the entire data
structure to be in a single continguous chunk of address space, you'll
get better results (fewer bad_alloc exceptions, no copies, no
reallocation delays) from a deque.
|
Yes.
| Quote: |
Of course, it's not hard to implement your "reallocation fallback"
policy with a wrapper function like this:
template < class T, class A
void modified_push_back ( std::vector
{
try {
v.push_back(t);
}
catch (std::bad_alloc&) {
std::vector<T,A> v2;
v2.reserve(v.capacity() + 1 ); // or whatever
std::copy( v.begin(), v.end(), std::back_inserter(v2) );
v.swap(v2);
}
|
I don't think this would work for the simple reason that a vector
implementation is not required to allocate ONLY n bytes(memory for n
objects) after a reserve(n)
command. The guarantee is that at least n objects can be inserted(assuming
that it is empty initially) without reallocation. The vector can do this
internally:
vector<T>::reserve(int n)
{
int new_size = std::max(this->capacity()*2, n);
// Normal stuff.
}
And we would be back to square one.
Regards,
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
Dhruv Matani
Guest
|
| Posted: Sun Nov 07, 2004 5:30 pm Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
On Sat, 06 Nov 2004 18:39:21 +0000, Dhruv Matani wrote:
[snip]...
| Quote: | Of course, it's not hard to implement your "reallocation fallback"
policy with a wrapper function like this:
template < class T, class A
void modified_push_back ( std::vector
{
try {
v.push_back(t);
}
catch (std::bad_alloc&) {
std::vector<T,A> v2; _________[0]
v2.reserve(v.capacity() + 1 ); // or whatever
std::copy( v.begin(), v.end(), std::back_inserter(v2) );
v.swap(v2);
}
I don't think this would work for the simple reason that a vector
implementation is not required to allocate ONLY n bytes(memory for n
objects) after a reserve(n)
command. The guarantee is that at least n objects can be inserted(assuming
that it is empty initially) without reallocation. The vector can do this
internally:
vector<T>::reserve(int n)
{
int new_size = std::max(this->capacity()*2, n);
// Normal stuff.
}
And we would be back to square one.
|
Ah! Sorry, I did not see [0]. I was under the impression that you are
reserving space in the original vector.
Yes, this would work!
Regards,
-Dhruv.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
johnchx
Guest
|
| Posted: Mon Nov 08, 2004 2:03 am Post subject: Re: should std::vector<> exponential growth rate be followed |
|
|
[email]dhruvbird (AT) gmx (DOT) net[/email] ("Dhruv Matani") wrote
| Quote: | On Fri, 05 Nov 2004 15:52:42 +0000, johnchx wrote:
Of course, it's not hard to implement your "reallocation fallback"
policy with a wrapper function like this:
template < class T, class A
void modified_push_back ( std::vector
{
try {
v.push_back(t);
}
catch (std::bad_alloc&) {
std::vector<T,A> v2;
v2.reserve(v.capacity() + 1 ); // or whatever
std::copy( v.begin(), v.end(), std::back_inserter(v2) );
v.swap(v2);
}
I don't think this would work for the simple reason that a vector
implementation is not required to allocate ONLY n bytes(memory for n
objects) after a reserve(n)
command. The guarantee is that at least n objects can be inserted(assuming
that it is empty initially) without reallocation. The vector can do this
internally:
vector<T>::reserve(int n)
{
int new_size = std::max(this->capacity()*2, n);
// Normal stuff.
}
|
Maybe you didn't notice that we're calling reserve() on a brand new
vector, whose capacity is zero (or near zero, if the implementation
happens to do a little pre-allocation). Under such conditions,
reasonable implementations -- such as the one you illustrate -- will
allocate memory for n "slots," or perhaps a bit more. It would be a
poor (though formally compliant) implementation that reserved much
more than n slots when its previous capacity() was zero or near-zero.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
