Re: [boost] double_ended - request formal review

Subject: Re: [boost] double_ended - request formal review
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2016-07-26 12:14:23

On 7/24/2016 8:44 AM, Benedek Thaler wrote:
> On Thu, Jul 21, 2016 at 4:59 PM, Mathias Gaunard <
> mathias.gaunard_at_[hidden]> wrote:
>
>> On 15 July 2016 at 16:51, Benedek Thaler <thalerbenedek_at_[hidden]> wrote:
>>
>>
>> devector is an interesting variant of vector, but it gives the illusion
>> that is could be used as a queue.
>> However given the implementation, it seems elements removed from either end
>> will never be reclaimed.
>>
>> I suggest documenting that limitation or having a threshold above which
>> memory is actually freed.
>>
>>
> Thanks for the feedback, Mathias. You are right. This implementation detail
> is a consequence of honoring reserve calls:
>
> devector<int> d;
> d.push_back(1);
> d.reserve_front(100);
> d.reserve_back(100);
>
> The reserve back has to keep the front capacity untouched or it breaks the
> promise of it. This also applies to a series of push_front/pop_backs, for
> example.
>
> I'll document this behavior. During the review, we'll see if we need more
> radical changes, e.g: changing the guarantees of reserve calls.
>

I haven't looked at the code but from your description it seems like 
there is an implicit connection between reserve_front and reserve_back.

I would expect this to be explicit and there to be 3 reserve methods.

reserve_front( size )
reserve_back( size )
reserve( front_size, back_size )

And that the implementation only maintain stability until a realloc 
occurs from any source (push/insert/reserve/whatever).

If a realloc occurs it should be free to reposition the elements in the 
already allocated memory block by rotating them forward or back.

It should also be free to change the available capacity at either end.

If the user needs fine grained control they can use the reserve methods 
to control reallocation.