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-05 17:02:02

Den 04-10-2017 kl. 23:28 skrev Ion Gaztañaga via Boost:
> On 04/10/2017 11:45, Thorsten Ottosen via Boost wrote:
>> Can they share some of the implementation, or are we left with a
>> double (or triple) implementation effort?
> They can obviously share implementation. That's the case with
> vector/small_vector/static_vector.

Ok, great.

>>> According to the usual STL rules, size_type shall come from the
>>> allocator, which knows what type can represent the number of elements
>>> that can be allocated.
>> I have no problems with STL rules, but it as you point out, even
>> Boost.Container deviates from several of those.
> Yes, but only when they are "clearly bad rules (TM)" ;-)

I don't have any strong position about the size_type but thought it nice
to have a small size of the container on 64 system.

I do sometimes wonder if breaking the strong guarantee is a smart move.

It seems to me that we can end up with non-trivial objects where the
invariant is broken. So in principle we can't even reliably destroy them
if the destructor relies on the invariant.

I guess I really dislike that we are allowed to write move operations
that are not noexcept (like swap).

>>> 4) unsafe_uninitialized_tag: I don’t like these non-safe
>>> constructors, which are  the cases?. With reserve-only constructors +
>>> unsafe emplace back a user can achieve nearly the same performance.
>>> For POD types (like the socket example mentioned in the
>>> documentation), I would suggest something like Boost.Container’s
>>> “default_init_t”. Instead of “unsafe_uninitialized_resize_front” I
>>> suggest resize_front(size_type, default_init_t)
>> I didn't know about these default_init_t when we started in 2015. They
>> have a good design IMO. But unfortunately they don't get rid of double
>> initialization for non-trivial types. So maybe both
>> resize_front( size_type, default_init_t )
>> resize_front( size_type, uninitialized_t )
>> would be an idea.
> I understand the idea to avoid zero initialization for buffers, but
> what's the use case for types with non-trivial constructors? The
> documentation shows a socket example, and that's covered ith
> default_init_t.

Well, I don't know if my compiler is wrong, but vc 2017 says:

         class IntClass
             int i;
             IntClass() : i(0) {}
             IntClass( int i ) : i( i )

is trivially copyable (hence we can copy arrays of it as fast as arrays
of ints). But it will be initialized with zero if I use default_init_t,

If so, I'm just saying that it may be nice/beneficial to be able to
avoid double initialization also for IntClass (perhaps not relevant to
sockets, but certainly to serialization).

I do agree that reserve + unchecked_emplace_back() should be working
well for types that are /not/ trivially copyable (also better in terms
of exception-safety). The unitialized_resize idea is probably before we
had emplace and so at that time there was no efficient/easy way to
construct an object inplace.

About the naming of unsafe_emplace_back: I prefer your suggestion with
the unchecked_ prefix. Other ideas would be

nongrowing_emplace_back // seems wrong, since the size does change

>>> 5) reserve() / resize(): I think they have no sensible meaning in the
>>> container (capacity() could be useful, depending on the reallocation
>>> strategy). We should not treat back insertion as the “default”
>>> insertion. IMHO the API of devector should be symmetrical.
>> Symmetry is good, but what about generic code?
> Generic code can't rely on reserve, only vector implements it in the
> STL. But if reserve() and resize() are unbiased to back insertion maybe
> they could make sense. reserve() allocates a new buffer if capacity() is
> not enough and moves existing elements to the middle. Resize could do
> the same and fill with elements on both ends.

If reserve is not an alias for reserve_back, the I think we must remove it.

I was thinking along generic code along the line

template< class BacKInsertionContiguousContainer >
void foo( BacKInsertionContiguousContainer& cont )
    cont.reserve( source.size() );
    for( ... )
       cont.push_back( ... );


why should that not work with both devector and vector?

> stable_insert can maintain stability with a middle insertion but there
> is no equivalent operation for erasures. I just can't imagine a use case
> that tan take advantage of stable_insert (it needs more or less a
> positional insertion, but not absolute, instead of front/back insertion)
> but it will surely exist.

Yeah, I don't have a use case at hand either. Somehow you would want to
insert a segments somewhere among the other segments. Then why not allow
the segments themselves to be rearranged? (potentially almost trivial to
implement). So I guess we could expose a complete container interface to
the segments, but it is perhaps premature until we have a good use case.

>> This is tricky. I think the best is to treat both ends independently.
>> If you start moving things around, you can break the O(1) amortized
>> guarantee by interleaving push_front/push_back.
> What do you mean by "treat both ends independtly"?

I mean that buffer extensions at either end should never affect each
other. That is, a push_back can never remove free capacity from the
front, a push_front can never remove free capacity from the back.

kind regards


Boost list run by bdawes at, gregod at, cpdaniel at, john at