Re: [boost] [devector] optimum growing/insertion policy

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-16 17:38:32

Den 15-10-2017 kl. 14:09 skrev Joaquin M López Muñoz via Boost:
> Hi,

> * Maintain a counter right_ of right insertions that gets incremented 
> when a
> right insertion occurs and *decremented* when an erasure is issued past the
> middle of the devector.

So to implement this with a custom Resizing policy, the policy would 
need be stored via compressed_pair as a member and additionally provide 
a hook:

   right_event( int elements )

where elements can be both positive and negative and which is called 
from push_back and insert as needed. By default this could be an empty 
function.

> * Right insertions trigger right shifting except when there's no back 
> free capacity,
> in which case a reallocation is performed.
> * Left insertions trigger left shifting except when there's no front 
> free capacity,
> in which case a reallocation is performed.
> * Reallocation reserves space for G*size() elements: of the resulting 
> G*size()-size()
> free space, a fraction right_/size() is devoted to back free capacity, 

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? Is it going to depend on no left insertions ever to 
have been made for v?

kind regards

-Thorsten