|
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;
public:
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,
right?
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
nonreallocating_emplace_back
nonallocating_emplace_back
nonexpanding_emplace_back
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
Thorsten
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk