Boost logo

Boost :

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-11 11:20:41


Den 10-10-2017 kl. 23:23 skrev Ion Gaztañaga via Boost:
> On 10/10/2017 10:08, Thorsten Ottosen via Boost wrote:
>> If we have - as free space and x as elements, then
>>
>>
>>   -----xxxxxxxxxxxxx---------
>>
>>   ^^^^^ front free capacity
>>   ^^^^^^^^^^^^^^^^^^ front capacity
>>        ^^^^^^^^^^^^^ size
>>                     ^^^^^^^^^ back free capacity
>>        ^^^^^^^^^^^^^^^^^^^^^^ back capacity (a.k.a capacity)
>
> Ok, I see it. So capacity() is an alias for back_capacity(). That might
> work for if a user only calls push_back in generic code but any generic
> code that checks for capacity() == size() would be broken.

why? If the vector is full, capacity() == size(). If the devector's
right hand size is full, size() == back_capacity().

>> The limit where new memory is acquired for insert can be found easily
>> enough.
>>
>> Basically we can't both generalize vector behavior and get the segment
>> size in one function. So pick one or none. Two of them allow generic
>> code to compile.
>
> I think the following is coherent, maybe not optimal in moves if only
> push_back is used:
>
>   -----xxxxxxxxxxxxx---------
>
>   ^^^^^---------------------- front free capacity
>   ^^^^^^^^^^^^^^^^^^--------- front capacity
>   -----^^^^^^^^^^^^^--------- size
>   ------------------^^^^^^^^^ back free capacity
>   -----^^^^^^^^^^^^^^^^^^^^^^ back capacity
>   ^^^^^^^^^^^^^^^^^^^^^^^^^^^ capacity
>
> front/back_free_capacity indicates the number of push_front/backs until
> data movement (and maybe allocation) is needed.
>
> front/back_capacity is front/back_free_capacity + size. If size ==
> front/back_capacity, then data movement (and maybe allocation) will happen
>
> capacity == size means that any insertion will lead to reallocation.

That's the alternative, but that is the one that breaks generic code,
isn't it?.

With my scheme above, if you absolutely must know if insertion
reallocates, you can use front_free_capacity() + back_free_capacity() ==
0. I don't know if that needs a special function though (it could be
called full() ).

>> (*) If push_back/push_front steals memory from the other end, we
>> should be cautious about when this is done (potentially high constant
>> factors as mentioned in the analysis you found). But it is more than
>> that: it may mean that push_back/push_front cannot give the strong
>> exception-safety guarantee. Are you really given that away for
>> Boost.Container's vector? (I hope not).
>
> Sorry about the bad news, push_back has no strong safety in
> boost::container::vector, as by design, move_if_noexcept is not used.
> It's mentioned in the documentation.

Ah, yes. Only when the type is well-behaved (non-movable, only copyable
or no-throw movable) we guarantee that, right?

kind regards

Thorsten


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk