Re: vector<> can probably never grow to it's maximum size!

[Dhruv Matani <dhruvbird at gmx dot net>]

On Sun, 2004-10-17 at 14:37, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >Hello,
> >	I would like to discuss an issue which deals with vector's memory
> >management. Consider a 16 machine.
> >
> >Here, max_size() would typically be say: ((2^16)-1)/sizeof(_Tp). Now,
> >consider that the current size is max_size()/2. If I want to add say 3
> >more elements, the vector to get space for totally max_size() elements,
> >and will fail because operator new will probably fail because of such a
> >large request. Can't we have the vector settle for a slightly smaller
> >return from the allocator at the expense of not sticking to the standard
> >strictly about the exponential increase policy?
> >  
> >
> If I understand correctly your question, you are right and indeed we are 
> already
> implementing this logic for std::string: see _M_mutate in 
> basic_string.tcc: we
> always check not to exceed max_size and in that case we simply stay with it.

Not exactly. What I was saying was something along these lines:

Hypothetical function which is always called when the
vector.capicity()<required_size.

vector<>::_M_reallocate_memory(new_size, required_size)
// required size is the size immediately required. eg. for push_back it
is 1, and for insert(iterator f, iterator l) it is l-f. new_size ==
old_size*2.
{
  int settle_for_less_memory = 1; // 1-> yes; 0-> no.

  try
  {
    pointer p = get_allocator().allocate(new_size,
settle_for_less_memory);
  }
  catch(std::bad_alloc&)
  {
// Ok, we did not get how much we asked for. But the allocate(n, hint)
is implemented such that if the allocator could not allocate the
required memory, it gives us whatever little it can, and sets
settle_for_less_memory to the number of objects that it actually has
allocated space for. This magic should go into the allocator.

    if (settle_for_less_memory < required size)
      throw;
  }

// Continue normal operator.
}

I would also like to point out a very interesting thread on comp.l.c+.m.
Gaby's comments are very enlightening.
http://groups.google.co.in/groups?hl=en&lr=&safe=off&threadm=fl7k3gwylo.fsf%40sel.cmla.ens-cachan.fr&rnum=1&prev=/groups%3Fq%3Drealloc%2Bin%2Bc%252B%252B%26hl%3Den%26lr%3D%26safe%3Doff%26selm%3Dfl7k3gwylo.fsf%2540sel.cmla.ens-cachan.fr%26rnum%3D1


> 
> BUT BUT BUT
> 
> Be warned that in the std::vector case things are slightly more tricky than
> computing min(max_size, new_size), since max_size == size_type(-1) /
> sizeof(value_type) and when sizeof(value_type) == 1, max_size is already
> at maximum rapresentable unsigned value, therefore, you cannot really
> exceed it with new_size...
> 
> Also, I want you to audit *all* the varios places in std::vector where 
> we grow,
> since someone pointed out time ago that there are inconsistencies. Also, 
> I want
> to see nice testcases, with custom allocators.
> 
> Paolo.
-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs