Boost logo

Boost :

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-10-18 14:18:23

El 18/10/2017 a las 15:18, Thorsten Ottosen via Boost escribió:
> Den 18-10-2017 kl. 15:10 skrev Joaquin M López Muñoz via Boost:
>> El 18/10/2017 a las 13:48, Thorsten Ottosen via Boost escribió:
>>> Den 18-10-2017 kl. 11:36 skrev Joaquin M López Muñoz via Boost:
>>>> El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
>>>>> Maybe this is lost to me in the details, but given code that works
>>>>> for vector:
>>>>>   vector<int> v;
>>>>>   ...
>>>>>   v.reserve( v.size() + N );
>>>>> which guarantees no exceptions and no reallocations, how would
>>>>> that work with your policy?
>>> Yes, sorry for being unclear, I'm talking about the guarantee given
>>> to push_back() and insert() of N elements after the call to reserve().
>> OK, now I get it. Well, my position is that reserve should be
>> replaced by
>> some mechanism for explicitly controlling free space at each end.
>> Then the user
>> can rely on the guarantee that she can do as many as
>> [back|front]_free_capacity() push_[back|front] ops without rellocation.
> and what about insert()? Do we then say if you want to avoid
> reallocations, you must allocate twice the needed memory?
> For vector we do not reallocate on insert().
> (I'm not saying that is the wrong answer, I would just like to know
> that the answer is).

My proposed policy consumes back free capacity if we have a right
insertion (past the
middle of the devector) and front free capacity in the case of a left
insertion (before
the middle of the devector). If you want to guarantee N no-reallocation
insertions at
any position so, yes, both front and back free capacity has to be >=N.

For the benefit of the readers, allow me to paste here the policy

* Fix the growing factor to G.
* The right balancing factor B is defined as the ratio between back free
capacity and total
free capacity. Let's say this is 50% at the start, that is, we have
* Right insertions and left insertions shift to the right and left,
respectively (as before).
* When reallocation is needed, calculate the new balance factor as a
function of
front and back space consumption just prior to reallocation. Pseudocode

 Â  struct free_space
 Â  {
 Â Â Â  std::size_t back,front
 Â  };

 Â  free_space new_space(free_space original,free_space remaining)
 Â  {
 Â Â Â  float balance=(float)std::max(original.back-remaining.back,0)/
 Â Â Â  std::size_t
 Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  new_free_space=new_space-size();
 Â Â Â  return {balance*new_free_space,(1-balance)*new_free_space};
 Â  }

Joaquín M López Muñoz

Boost list run by bdawes at, gregod at, cpdaniel at, john at