Boost logo

Boost :

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-10-10 21:23:38


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.

> 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.

> (*) 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.

A programmer that can tell the difference with std::vector needs to use
throwing moves, catch the exception (if uncatched, the program will
terminate and any guarantee is bogus) and do something with it that is
based on strong exception safety. And vectors with potentially throwing
moves will be really slow.

I think vector's strong safety was a consequence from the C++03's copy
semantics, and backwards compatibility had to be maintained in C++11 for
types that define move constructors and assignments. If designed today,
I doubt std::vector would offer strong exception safety for push_back.


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