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.